¿Por qué iterar sobre una Lista sería más rápido que indexar a través de ella?

Question

Lectura de la Java documentation for the ADT List que dice:

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

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

Answer 1

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

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

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

Por lo tanto, si quería imprimir el valor de cada elemento, si escribo esto:

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

lo que sucede es lo siguiente:

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

Ésta es terriblemente ineficiente porque cada vez 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 atravesar la lista!

Si en cambio lo hice:

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

entonces lo que sucede es lo siguiente:

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

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

Ahora, yendo a la otra implementación de List que es ArrayList, que está respaldado por una matriz simple. En ese caso, ambos cruces anteriores son equivalentes, ya que una matriz es contigua por lo que permite saltos aleatorios en posiciones arbitrarias.

Answer 2

La respuesta está implícita aquí:

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

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

Si nos fijamos en la JavaDoc for LinkedList, verá el comentario

Todas las operaciones realizan como podría esperarse de una lista doblemente enlazada. Las operaciones que indizan 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 for ArrayList tiene la correspondiente

aplicación dimensionable-array de la interfaz Lista. Implementa todas las operaciones de lista opcionales y permite todos los elementos, incluido el nulo. Además de implementar la interfaz de 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 es no sincronizado.)

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

Un related question titled "Big-O Summary for Java Collections Framework" tiene una respuesta que apunta a este recurso, "Java Collections JDK6" que pueden ser útiles.

Answer 3

Para encontrar el elemento i-ésimo de un LinkedList, la implementación pasa por todos los elementos hasta el i-ésimo.

Así

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

Answer 4

Si bien la respuesta aceptada es sin duda correcta, ¿podría señalar un pequeño error? Citando Tudor:

Ahora, ir a la otra puesta en práctica de la lista que es ArrayList, que uno está respaldado por una simple matriz. En ese caso, ambos cruces 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 que

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

source: Designing for Performance, Google's Android doc

nota escrita a mano que el bucle se refiere a la iteración indexada. Sospecho que es debido al iterador que se utiliza con bucles mejorados. Produce un rendimiento menor en la penalización en una estructura que está respaldada por una matriz contigua. También sospecho que esto podría ser cierto para la clase Vector.

Mi regla es usar 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 son no necesariamente equivalentes. Solo comida para pensar.

Answer 5

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

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

Al día siguiente, Shlemiel solo hace 150 yardas. "Bueno, eso no es casi tan bueno como ayer, pero sigues siendo un trabajador rápido. 150 yardas es respetable", 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 que hiciste diez veces ¡tanto trabajo! ¿Qué está pasando?"

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

Source.

Esta pequeña historia puede hacer que sea más fácil entender lo que sucede internamente y por qué es tan ineficiente.