¿Hay algún resultado de prueba de rendimiento disponible al comparar el bucle tradicional frente al iterador al atravesar un ArrayList, HashMap y otras colecciones?Rendimiento del bucle tradicional frente a iterador/foreach en Java
O simplemente ¿por qué debería usar Iterator en el ciclo o viceversa?
Asumiendo que esto es lo que quería decir:
// traditional for loop
for (int i = 0; i < collection.size(); i++) {
T obj = collection.get(i);
// snip
}
// using iterator
Iterator<T> iter = collection.iterator();
while (iter.hasNext()) {
T obj = iter.next();
// snip
}
// using iterator internally (confirm it yourself using javap -c)
for (T obj : collection) {
// snip
}
iterador es más rápido para las colecciones que no tienen acceso al azar (por ejemplo TreeSet, HashMap, LinkedList). Para arrays y ArrayLists, las diferencias de rendimiento deben ser insignificantes.
Editar: Creo que el micro-benchmarking es la raíz de casi el mal, al igual que la optimización temprana. Pero, de nuevo, creo que es bueno sentir las implicaciones de cosas tan triviales. Por lo tanto me he encontrado a small test:
resultados son similares para todos, pero "para con el contador" con LinkedList. Los otros cinco tomaron menos de 20 milisegundos para iterar en toda la lista. El uso de list.get(i) en una lista vinculada 100,000 veces tomó más de 2 minutos (!) En completarse (60,000 veces más lento). ¡Guauu! :) Por lo tanto, es mejor utilizar un iterador (que se utiliza explícita o implícitamente para cada uno), especialmente si no sabes de qué tipo y tamaño de lista se trata.
El resultado de su LinkedList muestra lo que sucede cuando pasa de O (n) a O (n^2) (o más) –
* Los otros cinco tomaron menos de 20 milisegundos para iterar en toda la lista * parece que el JVM murió optimización de código iniciada ... La diferencia entre la iteración de LinkedList y ArrayList es significativa (a favor de ArrayList) – bestsss
@bestsss no, ciertamente no lo hizo. He generado 100.000 cadenas aleatorias (en realidad UUID) y he resumido sus longitudes impresas en stdout después del ciclo. Por supuesto, los UUID tienen la misma longitud, lo que hace que la salida sea predecible, pero el compilador no es tan inteligente. Lo creas o no, pero una CPU moderna puede hacer eso en 20 ms. Para dar otra perspectiva: mi CPU tiene 4.000 BogoMips por núcleo. Así que estamos hablando de miles de millones de instrucciones por s o millones por ms. Por lo tanto, es factible iterar más de 100.000 cadenas con varios millones de instrucciones. Las CPU son más rápidas de lo que la mayoría de los desarrolladores piensan :) – sfussenegger
Usa JAD o JD-GUI contra tu código generado, y verás que no hay diferencia real. La ventaja del nuevo formulario de iterador es que se ve más limpio en su base de código.
Editar: Veo por las otras respuestas que en realidad quiso decir la diferencia entre usar get (i) versus un iterador. Tomé la pregunta original para significar la diferencia entre las formas antiguas y las nuevas de usar el iterador.
Usar get (i) y mantener su propio contador, especialmente para las clases List no es una buena idea, por las razones mencionadas en la respuesta aceptada.
El rendimiento es similar en la mayoría de los casos.
Sin embargo, cada vez que un código recibe una lista, y los bucles en él, no es conocido caso:
el iterador es mucho mejor para todas las implementaciones de lista que no implementan acceso aleatorio (ejemplo: Lista enlazada).
La razón es que para estas listas, acceder a un elemento por índice no es una operación de tiempo constante.
Así que también puede considerar el iterador como más robusto (a los detalles de implementación).
Como siempre, el rendimiento no se debe ocultar los problemas de legibilidad.
El bucle foreach java5 es un gran éxito en ese aspecto :-)
Gracias, pero ¿qué pasa con ArrayList? – Harish
ArrayList implementa RandomAccess, por lo tanto, list.get (i) es rápido. las diferencias de rendimiento deberían ser prácticamente insignificantes. – sfussenegger
Nota: Si bien no sé si LinkedList en el JDK está escrito de esa manera, sería trivial escribir una implementación de LinkedList donde un bucle for tradicional funcionaría tan rápido como el acceso aleatorio. Todo lo que se necesitaría sería mantener un puntero interno al último elemento al que se solicita el acceso aleatorio. Esto parece una implementación tan trivial que aceleraría tantas piezas de código que no puedo imaginar que no estén ahí. – tster
Una de las mejores razones para utilizar un iterador sobre la i ++ sintaxis es que no todas las estructuras de datos apoyarán acceso aleatorio y mucho menos tiene que funcionar bien. También debería programar en la lista o en la interfaz de recopilación para que, si luego decidió que otra estructura de datos sería más eficiente, podría canjearla sin una cirugía masiva. En ese caso (el caso de la codificación de una interfaz), no necesariamente conocerá los detalles de la implementación y probablemente sea más prudente posponer eso a la estructura de datos en sí misma.
Una de las razones por las que he aprendido a usar el para cada uno es que simplifica los bucles anidados, especialmente en más de 2 bucles dimensionales. Todos los i's, j's yk's que puedes terminar manipulando pueden ser confusos muy rápidamente.
La primera razón para usar un iterador es corrección obvia. Si utiliza un índice manual, puede haber errores muy inocuos que solo puede ver si observa con atención: ¿comenzó en 1 o en 0? ¿Terminaste al length - 1? ¿Usaste < o <=? Si usa un iterador, es mucho más fácil ver que realmente está iterando todo el conjunto. "Di lo que haces, haz lo que dices".
El segundo motivo es el acceso uniforme a diferentes estructuras de datos. Se puede acceder a una matriz de manera eficiente a través de un índice, pero una lista vinculada se recorre mejor al recordar el último elemento al que se accedió (de lo contrario obtendrá un "Shlemiel the painter"). Un hashmap es aún más complicado. Al proporcionar una interfaz uniforme a partir de estas y otras estructuras de datos (por ejemplo, también puede hacer recorridos de árbol), obtiene una corrección obvia de nuevo. La lógica de desplazamiento debe implementarse solo una vez, y el código que la utiliza puede decir "de manera concisa lo que hace y hacer lo que dice".
+1 a lo que dijo sfussenegger. Para su información, si usa un iterador explícito o uno implícito (es decir, para cada uno) no hará una diferencia en el rendimiento porque compilan con el mismo código de bytes.
No se compilan con el mismo código de bytes. El ciclo forEach itera sobre un iterable y obtiene un iterador que itera a través de la lista. Para la lista enlazada, el método get (i) comienza desde el primer nodo, atraviesa todo el camino y devuelve el objeto. Entonces, si usa i = 1 a 5 cada vez que comienza desde el principio. ver mi respuesta a continuación. – mickeymoon
Mi respuesta fue comparar forEach para usar explícitamente un Iterator, no comparándolo con un bucle for tradicional usando variables de índice. http://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html#jls-14.14.2 – erturne
no creo que
for (T obj : collection) {
calcula .size() cada vez a través del bucle y por lo tanto es más rápido que
for (int i = 0; i < collection.size(); i++) {
Remedio fácil con 'for (int i = 0, l = colección. size(); i
el primero obtiene el iterador de colecciones llamando al método collection.iterator() y luego itera llamando al método next() y hasNext() del iterador. – mickeymoon
Sí, hay que hacer una diferencia en las colecciones que son no acceso aleatorio basado como LinkedList. Una lista vinculada internamente se implementa mediante nodos que apuntan a la siguiente (comenzando en un nodo principal).
El método get (i) en una lista vinculada comienza desde el nodo principal y navega a través de los enlaces hasta el i-ésimo nodo. Cuando itera en la lista vinculada utilizando un bucle for tradicional, comienza de nuevo desde el nodo principal cada vez, por lo tanto, el recorrido global se convierte en tiempo cuadrático.
for(int i = 0; i< list.size(); i++) {
list.get(i); //this starts everytime from the head node instead of previous node
}
Mientras que la para cada iteración de bucle sobre el iterador obtenido a partir de la lista enlazada y llama a su método next(). El iterador mantiene los estados del último acceso y por lo tanto no comienza desde la cabeza en todo momento.
for(Object item: list) {
//item element is obtained from the iterator's next method.
}
observan que la razón de un bucle for es más lento con una lista enlazada, es que cada llamada a 'get (i)' repite desde la cabeza de la lista I '' tiempos.Estoy seguro de que es intuitivamente obvio para todos los demás aquí, pero me tomó un minuto averiguar por qué. –