¿Cuál es más eficiente, un ciclo para cada uno o un iterador?

¿Cuál es la forma más eficiente de atravesar una colección?

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a) {
  integer.toString();
}

o

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   integer.toString();
}

Tenga en cuenta que este no es un duplicado exacto de esto , esto , esto o esto , aunque una de las respuestas a la última pregunta se acerca. La razón por la que esto no es un engaño, es que la mayoría de estos son bucles de comparación donde se llama get(i)dentro del bucle, en lugar de usar el iterador.

Como se sugiere en Meta , publicaré mi respuesta a esta pregunta.

Si solo está deambulando por la colección para leer todos los valores, entonces no hay diferencia entre usar un iterador o la nueva sintaxis de bucle, ya que la nueva sintaxis solo usa el iterador bajo el agua.

Sin embargo, si quiere decir por bucle el viejo bucle "c-style":

for(int i=0; i<list.size(); i++) {
   Object o = list.get(i);
}

Entonces, el nuevo for loop, o iterador, puede ser mucho más eficiente, dependiendo de la estructura de datos subyacente. La razón de esto es que para algunas estructuras de datos, get(i)es una operación O (n), lo que hace que el bucle sea una operación O (n ² ). Una lista vinculada tradicional es un ejemplo de dicha estructura de datos. Todos los iteradores tienen como requisito fundamental que next()debería ser una operación O (1), haciendo que el bucle O (n).

Para verificar que el nuevo iterador utiliza el iterador bajo el agua para la sintaxis de bucle, compare los códigos de byte generados a partir de los siguientes dos fragmentos de código Java. Primero el bucle for:

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a)
{
  integer.toString();
}
// Byte code
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 3
 GOTO L2
L3
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 2 
 ALOAD 2
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L2
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L3

Y segundo, el iterador:

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();)
{
  Integer integer = (Integer) iterator.next();
  integer.toString();
}
// Bytecode:
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 2
 GOTO L7
L8
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 3
 ALOAD 3
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L7
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L8

Como puede ver, el código de byte generado es efectivamente idéntico, por lo que no hay penalización de rendimiento al usar cualquiera de los formularios. Por lo tanto, debe elegir la forma de bucle que sea más estéticamente atractiva para usted, para la mayoría de las personas que será el bucle para cada, ya que tiene menos código repetitivo.

La diferencia no está en el rendimiento, sino en la capacidad. Al usar una referencia directamente, tiene más poder sobre el uso explícito de un tipo de iterador (por ejemplo, List.iterator () vs. List.listIterator (), aunque en la mayoría de los casos devuelven la misma implementación). También tiene la capacidad de hacer referencia al iterador en su bucle. Esto le permite hacer cosas como eliminar elementos de su colección sin obtener una ConcurrentModificationException.

p.ej

Esto esta bien:

Set<Object> set = new HashSet<Object>();
// add some items to the set

Iterator<Object> setIterator = set.iterator();
while(setIterator.hasNext()){
     Object o = setIterator.next();
     if(o meets some condition){
          setIterator.remove();
     }
}

Esto no es así, ya que arrojará una excepción de modificación concurrente:

Set<Object> set = new HashSet<Object>();
// add some items to the set

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}

Para ampliar la propia respuesta de Paul, ha demostrado que el bytecode es el mismo en ese compilador en particular (¿presumiblemente el javac de Sun?) Pero no se garantiza que diferentes compiladores generen el mismo bytecode, ¿verdad? Para ver cuál es la diferencia real entre los dos, vayamos directamente a la fuente y verifiquemos la Especificación del lenguaje Java, específicamente 14.14.2, "La declaración mejorada para" :

La fordeclaración mejorada es equivalente a una fordeclaración básica de la forma:

for (I #i = Expression.iterator(); #i.hasNext(); ) {
    VariableModifiers(opt) Type Identifier = #i.next();    
    Statement 
}

En otras palabras, JLS exige que los dos sean equivalentes. En teoría, eso podría significar diferencias marginales en el código de bytes, pero en realidad se requiere el bucle mejorado para:

• Invocar el .iterator()método
• Utilizar .hasNext()
• Haga que la variable local esté disponible a través de .next()

En otras palabras, a todos los efectos prácticos, el código de bytes será idéntico o casi idéntico. Es difícil imaginar una implementación del compilador que resulte en una diferencia significativa entre los dos.

El foreachunderhood está creandoiterator , llamando a hasNext () y llamando a next () para obtener el valor; El problema con el rendimiento solo se produce si está utilizando algo que implementa RandomomAccess.

for (Iterator<CustomObj> iter = customList.iterator(); iter.hasNext()){
   CustomObj custObj = iter.next();
   ....
}

Los problemas de rendimiento con el bucle basado en iterador se deben a que es:

1. asignar un objeto incluso si la lista está vacía ( Iterator<CustomObj> iter = customList.iterator(););
2. iter.hasNext() Durante cada iteración del bucle hay una llamada virtual invokeInterface (revise todas las clases, luego realice la búsqueda de la tabla de métodos antes del salto).
3. la implementación del iterador tiene que hacer al menos 2 campos de búsqueda para hacer que la hasNext()cifra sea el valor: # 1 obtiene el conteo actual y # 2 obtiene el conteo total
4. dentro del bucle del cuerpo, hay otra llamada virtual invokeInterface iter.next(así que: revisa todas las clases y realiza una búsqueda en la tabla de métodos antes del salto) y también tiene que hacer la búsqueda de campos: # 1 obtiene el índice y # 2 obtiene la referencia a la matriz para hacer el desplazamiento en él (en cada iteración).

Una posible optimización es cambiar a unaindex iteration con la búsqueda de tamaño en caché:

for(int x = 0, size = customList.size(); x < size; x++){
  CustomObj custObj = customList.get(x);
  ...
}

Aquí tenemos:

1. una llamada al método virtual invokeInterface customList.size()en la creación inicial del bucle for para obtener el tamaño
2. la llamada al método get customList.get(x)durante el ciclo for body, que es una búsqueda de campo en la matriz y luego puede hacer el desplazamiento en la matriz

Redujimos un montón de llamadas a métodos, búsquedas de campo. Esto no quiere hacer con LinkedListo con algo que no sea un RandomAccessobj de colección, de lo contrario customList.get(x)se convertirá en algo que tiene que atravesarlo LinkedListen cada iteración.

Esto es perfecto cuando sabes que es una RandomAccesscolección de listas basada.

foreachusa iteradores debajo del capó de todos modos. Realmente es solo azúcar sintáctico.

Considere el siguiente programa:

import java.util.List;
import java.util.ArrayList;

public class Whatever {
    private final List<Integer> list = new ArrayList<>();
    public void main() {
        for(Integer i : list) {
        }
    }
}

Vamos a compilarlo javac Whatever.java,
y leer el bytecode desmontado de main(), usando javap -c Whatever:

public void main();
  Code:
     0: aload_0
     1: getfield      #4                  // Field list:Ljava/util/List;
     4: invokeinterface #5,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
     9: astore_1
    10: aload_1
    11: invokeinterface #6,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z
    16: ifeq          32
    19: aload_1
    20: invokeinterface #7,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
    25: checkcast     #8                  // class java/lang/Integer
    28: astore_2
    29: goto          10
    32: return

Podemos ver que se foreachcompila en un programa que:

• Crea un iterador usando List.iterator()
• If Iterator.hasNext(): invoca Iterator.next()y continúa el bucle

En cuanto a "¿por qué este bucle inútil no se optimiza a partir del código compilado? Podemos ver que no hace nada con el elemento de la lista": bueno, es posible que codifique su iterable de modo que .iterator()tenga efectos secundarios , o eso .hasNext()tiene efectos secundarios o consecuencias significativas.

Podrías imaginar fácilmente que un iterable que representa una consulta desplazable desde una base de datos podría hacer algo dramático .hasNext()(como contactar con la base de datos o cerrar un cursor porque has llegado al final del conjunto de resultados).

Entonces, aunque podemos probar que no sucede nada en el cuerpo del bucle ... es más costoso (¿intratable?) Probar que no sucede nada significativo / consecuente cuando iteramos. El compilador tiene que dejar este cuerpo de bucle vacío en el programa.

Lo mejor que podríamos esperar sería una advertencia del compilador . Es interesante que javac -Xlint:all Whatever.javano no nos advierten acerca de este cuerpo del bucle vacío. Sin embargo, IntelliJ IDEA lo hace. Es cierto que he configurado IntelliJ para usar Eclipse Compiler, pero esa puede no ser la razón.

Iterator es una interfaz en el marco de colecciones de Java que proporciona métodos para recorrer o iterar sobre una colección.

Tanto el iterador como el bucle actúan de manera similar cuando su motivo es atravesar una colección para leer sus elementos.

for-each es solo una forma de iterar sobre la Colección.

Por ejemplo:

List<String> messages= new ArrayList<>();

//using for-each loop
for(String msg: messages){
    System.out.println(msg);
}

//using iterator 
Iterator<String> it = messages.iterator();
while(it.hasNext()){
    String msg = it.next();
    System.out.println(msg);
}

Y for-each loop puede usarse solo en objetos que implementan la interfaz iteradora.

Ahora volvamos al caso de for loop e iterator.

La diferencia se produce cuando intenta modificar una colección. En este caso, el iterador es más eficiente debido a su propiedad de falla rápida . es decir. comprueba cualquier modificación en la estructura de la colección subyacente antes de iterar sobre el siguiente elemento. Si se encuentran modificaciones, arrojará la excepción ConcurrentModificationException .

(Nota: esta funcionalidad de iterador solo es aplicable en el caso de las clases de colección en el paquete java.util. No es aplicable para las colecciones concurrentes ya que son a prueba de fallas por naturaleza)

Debemos evitar usar el bucle for tradicional mientras trabajamos con Colecciones. La razón simple que daré es que la complejidad del ciclo for es del orden O (sqr (n)) y la complejidad de Iterator o incluso el ciclo for mejorado es solo O (n). Por lo tanto, ofrece una diferencia de rendimiento. Simplemente tome una lista de unos 1000 elementos e imprímala de ambas maneras. y también imprime la diferencia horaria para la ejecución. Puedes ver la diferencia.