Pourquoi l'itération sur une liste serait-elle plus rapide que l'indexation à travers elle?

En lisant la documentation Java pour la liste ADT, il est dit:

L'interface Liste fournit quatre méthodes d'accès positionnel (indexé) aux éléments de liste. Les listes (comme les tableaux Java) sont basées sur zéro. Notez que ces opérations peuvent s'exécuter en temps proportionnel à la valeur d'index pour certaines implémentations (la classe LinkedList, par exemple). Ainsi, l'itération sur les éléments d'une liste est généralement préférable à l'indexation à travers celle-ci si l'appelant ne connaît pas l'implémentation.

Qu'est-ce que cela veut dire exactement? Je ne comprends pas la conclusion qui est tirée.

Dans une liste liée, chaque élément a un pointeur vers l'élément suivant:

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

Pour y accéder item3, vous pouvez voir clairement que vous devez marcher de la tête à travers chaque nœud jusqu'à ce que vous atteigniez l'élément 3, car vous ne pouvez pas sauter directement.

Ainsi, si je voulais imprimer la valeur de chaque élément, si j'écris ceci:

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

ce qui se passe est ceci:

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

C'est horriblement inefficace car chaque fois que vous indexez, il redémarre depuis le début de la liste et parcourt chaque élément. Cela signifie que votre complexité est effectivement O(N^2)juste de parcourir la liste!

Si à la place je faisais ceci:

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

alors ce qui se passe est ceci:

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

le tout en un seul parcours, qui est O(N).

Maintenant, passons à l'autre implémentation Listdont ArrayListcelle-ci est soutenue par un simple tableau. Dans ce cas, les deux parcours ci-dessus sont équivalents, puisqu'un tableau est contigu, il permet donc des sauts aléatoires vers des positions arbitraires.

La réponse est implicite ici:

Notez que ces opérations peuvent s'exécuter dans le temps proportionnel à la valeur d'index pour certaines implémentations (la classe LinkedList, par exemple)

Une liste chaînée n'a pas d'index inhérent; l'appel .get(x)nécessitera que l'implémentation de la liste trouve la première entrée et appelle .next()x-1 fois (pour un accès en temps O (n) ou linéaire), où une liste basée sur un tableau peut simplement indexer en backingarray[x]O (1) ou en temps constant.

Si vous regardez le JavaDoc pourLinkedList , vous verrez le commentaire

Toutes les opérations se déroulent comme on pouvait s'y attendre pour une liste à double liaison. Les opérations qui indexent dans la liste parcourent la liste depuis le début ou la fin, selon ce qui est le plus proche de l'index spécifié.

alors que JavaDoc pourArrayList a le correspondant

Implémentation de tableau redimensionnable de l'interface List. Implémente toutes les opérations de liste facultatives et autorise tous les éléments, y compris null. Outre l'implémentation de l'interface List, cette classe fournit des méthodes pour manipuler la taille du tableau utilisé en interne pour stocker la liste. (Cette classe est à peu près équivalente à Vector, sauf qu'elle n'est pas synchronisée.)

Le size, isEmpty, get, set, iterator, et listIteratorexécuter des opérations en temps constant. L'opération d'ajout s'exécute en temps constant amorti, c'est-à-dire que l'ajout de n éléments nécessite un temps O (n). Toutes les autres opérations s'exécutent en temps linéaire (en gros). Le facteur constant est faible par rapport à celui de la LinkedListmise en œuvre.

Une question associée intitulée "Big-O Summary for Java Collections Framework" a une réponse pointant vers cette ressource, "Java Collections JDK6", qui pourrait vous être utile.

Bien que la réponse acceptée soit très certainement correcte, pourrais-je signaler un défaut mineur. Citant Tudor:

Maintenant, passons à l'autre implémentation de List qui est ArrayList, celle-ci est soutenue par un simple tableau. Dans ce cas, les deux parcours ci-dessus sont équivalents , puisqu'un tableau est contigu, il permet donc des sauts aléatoires vers des positions arbitraires.

Ce n'est pas tout à fait vrai. La vérité c'est que

Avec une ArrayList, une boucle comptée manuscrite est environ 3 fois plus rapide

source: Designing for Performance, document Android de Google

Notez que la boucle manuscrite fait référence à l'itération indexée. Je soupçonne que c'est à cause de l'itérateur qui est utilisé avec des boucles for améliorées. Il produit une performance mineure en pénalité dans une structure qui est soutenue par un tableau contigu. Je soupçonne également que cela pourrait être vrai pour la classe Vector.

Ma règle est la suivante: utilisez la boucle for améliorée chaque fois que possible, et si vous vous souciez vraiment des performances, utilisez l'itération indexée uniquement pour ArrayLists ou Vectors. Dans la plupart des cas, vous pouvez même l'ignorer - le compilateur optimise peut-être cela en arrière-plan.

Je tiens simplement à souligner que dans le contexte du développement sous Android, les deux parcours des ArrayLists ne sont pas forcément équivalents . Juste matière à réflexion.

Itérer sur une liste avec un décalage pour la recherche, comme i, est analogue à l'algorithme de Shlemiel le peintre .

Shlemiel obtient un emploi de peintre de rue, peignant les lignes pointillées au milieu de la route. Le premier jour, il prend un pot de peinture sur la route et termine 300 mètres de route. "C'est plutôt bien!" dit son patron, "vous êtes un travailleur rapide!" et lui paie un kopeck.

Le lendemain, Shlemiel ne fait que 150 mètres. "Eh bien, ce n'est pas aussi bon qu'hier, mais vous êtes toujours un travailleur rapide. 150 mètres, c'est respectable," et lui paie un kopeck.

Le lendemain, Shlemiel peint 30 mètres de la route. "Seulement 30!" crie son patron. "C'est inacceptable! Le premier jour, vous avez travaillé dix fois plus! Que se passe-t-il?"

«Je ne peux pas m'en empêcher», dit Shlemiel. "Chaque jour, je m'éloigne de plus en plus du pot de peinture!"

Source .

Cette petite histoire peut permettre de comprendre plus facilement ce qui se passe en interne et pourquoi c'est si inefficace.

Pour trouver le i-ème élément d'un, LinkedListl'implémentation passe par tous les éléments jusqu'au i-ème.

Alors

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