¿Por qué iterar sobre una Lista sería más rápido que indexarlo?

125

Al leer la documentación de Java para la lista ADT , dice:

La interfaz de Lista proporciona cuatro métodos para el acceso posicional (indexado) a los elementos de la lista. Las listas (como las matrices Java) están basadas en cero. Tenga en cuenta que estas operaciones pueden ejecutarse en un tiempo proporcional al valor del índice para algunas implementaciones (la clase LinkedList, por ejemplo). Por lo tanto, iterar sobre los elementos en una lista generalmente es preferible a indexarlo si la persona que llama no conoce la implementación.

¿Qué significa esto exactamente? No entiendo la conclusión que se extrae.

nomel7
fuente
12
Otro ejemplo que puede ayudarlo a comprender el caso general de esto es el artículo de Joel Spolsky "Volver a lo básico" : busque "el algoritmo de Shlemiel el pintor".
un CVn

Respuestas:

211

En una lista vinculada, cada elemento tiene un puntero al siguiente elemento:

head -> item1 -> item2 -> item3 -> etc.

Para acceder item3, puede ver claramente que necesita caminar desde la cabeza a través de cada nodo hasta llegar al elemento 3, ya que no puede saltar directamente.

Por lo tanto, si quisiera imprimir el valor de cada elemento, si escribo esto:

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

lo que pasa es esto:

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

Esto es terriblemente ineficiente porque cada vez que está indexando se reinicia desde el principio de la lista y revisa cada elemento. ¡Esto significa que su complejidad es efectivamente O(N^2)solo para recorrer la lista!

Si en cambio hice esto:

for(String s: list) {
    System.out.println(s);
}

entonces lo que pasa es esto:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

todo en un solo recorrido, que es O(N).

Ahora, ir a la otra puesta en práctica de Listla cual está ArrayList, que uno está respaldado por una simple matriz. En ese caso, los dos recorridos anteriores son equivalentes, ya que una matriz es contigua, por lo que permite saltos aleatorios a posiciones arbitrarias.

Tudor
fuente
29
Aviso menor: LinkedList buscará desde el final de la lista si el índice está en la mitad posterior de la lista, pero eso realmente no cambia la ineficiencia fundamental. Lo hace solo un poco menos problemático.
Joachim Sauer
8
Esto es terriblemente ineficiente . Para los enlaces de LinkedList más grandes, para los más pequeños, puede funcionar más rápido, REVERSE_THRESHOLDestá configurado en 18 java.util.Collections, es extraño ver una respuesta tan votada sin el comentario.
bestsss
1
@DanDiplo, si la estructura está vinculada, sí, es verdad. Sin embargo, el uso de estructuras LinkedS es un pequeño misterio. Casi siempre tienen un rendimiento mucho peor que los respaldados por matriz (huella de memoria adicional, localidad poco amigable y terrible para gc). La lista estándar en C # está respaldada por una matriz.
bestsss
3
Aviso menor: si desea verificar qué tipo de iteración se debe usar (indexado frente a iterador / foreach), siempre puede probar si una lista implementa RandomAccess (una interfaz de marcador):List l = unknownList(); if (l instanceof RandomAccess) /* do indexed loop */ else /* use iterator/foreach */
afk5min
1
@ KK_07k11A0585: En realidad, el bucle for mejorado en su primer ejemplo se compila en un iterador como en el segundo ejemplo, por lo que son equivalentes.
Tudor
35

La respuesta está implícita aquí:

Tenga en cuenta que estas operaciones pueden ejecutarse en un tiempo proporcional al valor del índice para algunas implementaciones (la clase LinkedList, por ejemplo)

Una lista vinculada no tiene un índice inherente; la llamada .get(x)requerirá la implementación de la lista para encontrar la primera entrada y llamar .next()x-1 veces (para un O (n) o acceso de tiempo lineal), donde una lista respaldada por una matriz puede indexarse backingarray[x]en O (1) o tiempo constante.

Si miras el JavaDocLinkedList , verás el comentario

Todas las operaciones funcionan como podría esperarse para una lista doblemente vinculada. Las operaciones que se indexan en la lista atravesarán la lista desde el principio o el final, lo que esté más cerca del índice especificado.

mientras que JavaDoc paraArrayList tiene el correspondiente

Implementación de matriz redimensionable de la interfaz List. Implementa todas las operaciones de lista opcionales y permite todos los elementos, incluido nulo. Además de implementar la interfaz Lista, esta clase proporciona métodos para manipular el tamaño de la matriz que se usa internamente para almacenar la lista. (Esta clase es aproximadamente equivalente a Vector, excepto que no está sincronizada).

El size, isEmpty, get, set, iterator, y listIteratorlas operaciones se ejecutan en tiempo constante. La operación de agregar se ejecuta en tiempo constante amortizado, es decir, agregar n elementos requiere tiempo O (n). Todas las demás operaciones se ejecutan en tiempo lineal (aproximadamente). El factor constante es bajo en comparación con el de la LinkedListimplementación.

Una pregunta relacionada titulada "Big-O Summary for Java Collections Framework" tiene una respuesta que apunta a este recurso, "Java Collections JDK6", que puede resultarle útil.

andersoj
fuente
7

Si bien la respuesta aceptada es ciertamente correcta, podría señalar un pequeño defecto. Citando a Tudor:

Ahora, yendo a la otra implementación de List que es ArrayList, esa está respaldada por una matriz simple. En ese caso, los dos recorridos anteriores son equivalentes , ya que una matriz es contigua, por lo que permite saltos aleatorios a posiciones arbitrarias.

Esto no es del todo cierto. La verdad es esa

Con una ArrayList, un bucle contado escrito a mano es aproximadamente 3 veces más rápido

fuente: Designing for Performance, documento de Android de Google

Tenga en cuenta que el bucle escrito a mano se refiere a la iteración indexada. Sospecho que es por el iterador que se usa con bucles mejorados. Produce un rendimiento menor en penalización en una estructura respaldada por una matriz contigua. También sospecho que esto podría ser cierto para la clase Vector.

Mi regla es, use el bucle for mejorado siempre que sea posible, y si realmente le importa el rendimiento, use la iteración indexada solo para ArrayLists o Vectors. En la mayoría de los casos, incluso puede ignorar esto: el compilador podría estar optimizando esto en segundo plano.

Simplemente quiero señalar que, en el contexto del desarrollo en Android, ambos recorridos de ArrayLists no son necesariamente equivalentes . Solo comida para pensar.

Dhruv Gairola
fuente
Su fuente es solo Anndroid. ¿Esto también es válido para otras JVM?
Matsemann
No estoy completamente seguro de tbh, pero nuevamente, el uso de bucles mejorados debería ser el predeterminado en la mayoría de los casos.
Dhruv Gairola
Para mí tiene sentido, deshacerse de toda la lógica del iterador al acceder a una estructura de datos que utiliza una matriz funciona más rápido. No sé si 3 veces más rápido, pero ciertamente más rápido.
Setzer22
7

Iterar sobre una lista con un desplazamiento para la búsqueda, como i, es análogo al algoritmo del pintor Shlemiel .

Shlemiel consigue un trabajo como pintor callejero, pintando las líneas punteadas en el medio del camino. El primer día saca una lata de pintura al camino y termina 300 yardas del camino. "¡Eso es bastante bueno!" dice su jefe, "eres un trabajador rápido!" y le paga un kopeck.

Al día siguiente, Shlemiel solo logra 150 yardas. "Bueno, eso no es tan bueno como ayer, pero sigues siendo un trabajador rápido. 150 yardas son respetables", y le paga un kopeck.

Al día siguiente, Shlemiel pinta 30 yardas de la carretera. "¡Solo 30!" grita su jefe. "¡Eso es inaceptable! ¡El primer día hiciste diez veces más trabajo! ¿Qué está pasando?"

"No puedo evitarlo", dice Shlemiel. "¡Cada día me alejo más y más de la lata de pintura!"

Fuente .

Esta pequeña historia puede facilitar la comprensión de lo que está sucediendo internamente y por qué es tan ineficiente.

alex
fuente
4

Para encontrar el elemento i-th de a, LinkedListla implementación pasa por todos los elementos hasta el i-th.

Entonces

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}
esej
fuente