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

que es indexar un sitio web (5)

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

La interfaz de la Lista proporciona cuatro métodos para el acceso posicional (indexado) a los elementos de la lista. 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 esto exactamente? No entiendo la conclusión que se dibuja.

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

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

Para acceder al item3 , puedes ver claramente que necesitas caminar desde la cabeza a través de cada nodo hasta llegar al elemento 3, ya que no puedes 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 sucede 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 indexa, 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, hice esto:

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

entonces lo que sucede es esto:

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

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

Ahora, yendo a la otra implementación de List que es ArrayList , esa está respaldada 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.

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

Shlemiel consigue un trabajo como pintor callejero, pintando las líneas de puntos en el medio de la carretera. El primer día saca una lata de pintura a la carretera y termina a 300 yardas de la carretera. "¡Eso es bastante 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 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 hiciste diez veces tanto 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 hacer que sea más fácil entender lo que sucede internamente y por qué es tan ineficiente.

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; .get(x) requerirá que la implementación de la lista encuentre la primera entrada y llame a .next() x-1 veces (para un O (n) o acceso en tiempo lineal), donde una lista respaldada por una matriz solo puede indexar en backingarray[x] en O (1) o tiempo constante.

Si miras JavaDoc for LinkedList , verás el comentario

Todas las operaciones funcionan como se podría esperar para 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 para ArrayList tiene el correspondiente

Implementación de arreglos redimensionables de la interfaz de la 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 más o menos equivalente a Vector, excepto que no está sincronizada).
Las isEmpty size , isEmpty , get , set , listIterator y listIterator 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 comparado con el de la implementación LinkedList .

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

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

Asi que

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

Si bien la respuesta aceptada es sin duda correcta, ¿podría señalar un defecto menor? 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, ambos cruces anteriores son equivalentes , ya que una matriz es contigua por lo que permite saltos aleatorios en posiciones arbitrarias.

Esto no es del todo cierto. La verdad es esa

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

fuente: Diseñando para el rendimiento, el documento de Android de Google

Tenga en cuenta que el ciclo manuscrito 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 te importa el rendimiento, usa 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 de desarrollo en Android, ambos recorridos de ArrayLists no son necesariamente equivalentes . Solo comida para pensar.