¿Cuál es más eficiente, un bucle for-each o un iterador?

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

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

o

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

Tenga en cuenta que esto no es un duplicado exacto de esto , esto , esto o aquello , aunque se aproxima una de las respuestas a la última pregunta. La razón de que esto no sea una tontería, es que la mayoría de ellos están comparando bucles en los que llama get(i) dentro del bucle, en lugar de usar el iterador.

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

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

Sin embargo, si te refieres al loop del viejo bucle “c-style”:

 for(int i=0; i 

Entonces, el nuevo bucle for, 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), que hace que el bucle sea una operación O (n 2 ). Una lista vinculada tradicional es un ejemplo de dicha estructura de datos. Todos los iteradores tienen como requisito fundamental que next() sea ​​una operación O (1), formando el ciclo O (n).

Para verificar que el iterador se usa bajo el agua con la nueva syntax de bucle for, compare los códigos de byte generados a partir de los siguientes dos fragmentos de Java. Primero el ciclo for:

 List a = new ArrayList(); 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 a = new ArrayList(); 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 bytes generado es efectivamente idéntico, por lo que no hay ninguna penalización de rendimiento al usar cualquiera de las formas. Por lo tanto, debe elegir la forma de bucle que le resulte más atractiva desde el punto de vista estético, para la mayoría de las personas será el bucle for-each, ya que tiene menos código repetitivo.

La diferencia no está en el rendimiento, sino en la capacidad. Cuando se utiliza una referencia directamente, se 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 ciclo. Esto le permite hacer cosas como eliminar elementos de su colección sin obtener una ConcurrentModificationException.

p.ej

Esto esta bien:

 Set set = new HashSet(); // add some items to the set Iterator setIterator = set.iterator(); while(setIterator.hasNext()){ Object o = setIterator.next(); if(o meets some condition){ setIterator.remove(); } } 

Esto no es así, ya que lanzará una excepción de modificación simultánea:

 Set set = new HashSet(); // add some items to the set for(Object o : set){ if(o meets some condition){ set.remove(o); } } 

Para ampliar la respuesta de Paul, él ha demostrado que el bytecode es el mismo en ese comstackdor en particular (¿presumiblemente el javac de Sun?) Pero no se garantiza que los comstackdores diferentes generen el mismo bytecode, ¿verdad? Para ver cuál es la diferencia real entre los dos, vamos directamente a la fuente y verificamos la Especificación del lenguaje Java, específicamente 14.14.2, “La statement mejorada para” :

El enunciado mejorado for es equivalente a una statement básica for el formulario:

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

En otras palabras, el JLS requiere que los dos sean equivalentes. En teoría, eso podría significar diferencias marginales en el bytecode, pero en realidad el bucle for mejorado se requiere para:

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

Entonces, en otras palabras, para todos los propósitos prácticos, el bytecode será idéntico, o casi idéntico. Es difícil imaginar cualquier implementación del comstackdor que daría lugar a una diferencia significativa entre los dos.

Es posible que necesite usar iteradores si necesita modificar la colección en su ciclo. El primer enfoque arrojará una excepción.

 for (String i : list) { System.out.println(i); list.remove(i); // throws exception } Iterator it=list.iterator(); while (it.hasNext()){ System.out.println(it.next()); it.remove(); // valid here } 

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 for funcionan de manera similar cuando su motivo es simplemente atravesar una colección para leer sus elementos.

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

Por ejemplo:

 List messages= new ArrayList<>(); //using for-each loop for(String msg: messages){ System.out.println(msg); } //using iterator Iterator it = messages.iterator(); while(it.hasNext()){ String msg = it.next(); System.out.println(msg); } 

Y para-cada bucle se puede usar solo en los objetos que implementan la interfaz del iterador.

Ahora volvamos al caso de for loop e iterator.

La diferencia se produce cuando intentas modificar una colección. En este caso, iterator es más eficiente debido a su propiedad fail-fast . 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 ConcurrentModificationException .

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

foreach usa iteradores bajo el capó de todos modos. Realmente es solo azúcar sintáctico.

Considere el siguiente progtwig:

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

Vamos a comstackrlo con javac Whatever.java ,
Y lea el bytecode desensamblado 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 

Vemos que foreach comstack en un progtwig que:

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

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

Podría imaginarse fácilmente que un iterable que representa una consulta desplazable de una base de datos podría hacer algo dramático en .hasNext() (como ponerse en contacto con la base de datos o cerrar un cursor porque ha llegado al final del conjunto de resultados).

Entonces, a pesar de que podemos probar que no pasa nada en el cuerpo del bucle … es más costoso (¿irresoluble?) Probar que no ocurre nada significativo / consecuente cuando iteramos. El comstackdor tiene que dejar este cuerpo de bucle vacío en el progtwig.

Lo mejor que podríamos esperar sería una advertencia del comstackdor. Es interesante que javac -Xlint:all Whatever.java no nos advierta sobre este cuerpo de bucle vacío. IntelliJ IDEA sí lo hace. Es cierto que he configurado IntelliJ para usar el comstackdor de Eclipse, pero esa puede no ser la razón.

enter image description here

El underhood de foreach está creando el iterator , 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 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. asignando un objeto incluso si la lista está vacía ( Iterator iter = customList.iterator(); );
  2. iter.hasNext() durante cada iteración del ciclo hay una llamada virtual invokeInterface (revisa todas las clases, luego realiza la búsqueda de tablas de métodos antes del salto).
  3. la implementación del iterador tiene que hacer al menos 2 búsquedas de campos para hacer que la hasNext() a hasNext() calcule el valor: # 1 obtiene el recuento actual y # 2 obtiene el recuento total
  4. dentro del bucle del cuerpo, hay otra llamada virtual de iter.next (entonces: iter.next todas las clases y realice la búsqueda de tabla de métodos antes del salto) y también tiene que hacer la búsqueda de campos: # 1 obtener el índice y # 2 obtener el referencia a la matriz para hacer la compensación en ella (en cada iteración).

Una posible optimización es cambiar a una index 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. un método virtual invokeInterface llama a customList.size() en la creación inicial del ciclo for para obtener el tamaño
  2. el método get llama a customList.get(x) durante body for loop, que es una búsqueda de campo para la matriz y luego puede hacer la compensación en la matriz

Redujimos una tonelada de llamadas a métodos, búsquedas de campo. Esto no quiere hacer con LinkedList o con algo que no sea un obj de colección RandomAccess ; de lo contrario, customList.get(x) se convertirá en algo que tiene que atravesar LinkedList en cada iteración.

Esto es perfecto cuando sabes que es cualquier colección de listas basada en RandomAccess .

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