Pourquoi est itérer plus préférable que l'accès aléatoire

Question

The following page états

L'interface List fournit quatre méthodes pour position (indexée) accès à la liste des éléments. Les listes (comme les tableaux Java) sont basées sur zéro. 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). Ainsi, itérer sur les éléments d'une liste est généralement préférable à en l'indexant si l'appelant ne connaît pas l'implémentation.

Qu'est-ce que cela signifie? Est-ce que cela veut dire que je préférerais

ListIterator<Integer> iterator = list.listIterator(0); 
iterator.next() 
iterator.next() 

sur

list.get(1) 

Si oui, pourquoi? Si l'implémentation de la liste sous-jacente est Array, get sera exécutée à temps constant. Mais en utilisant l'itérateur c'est O(n). Qu'est-ce que j'oublie ici?

Veulent-ils dire que je devrais utiliser list.listIterator(1); au lieu de list.get(1)?

Answer 1

Non, mais vous devriez préférer

for (Integer value : list) { 
    // do something with value 
} 

(ou une boucle en utilisant explicitement l'itérateur de la liste) sur

for (int i = 0; i < list.size(); i++) { 
    Integer value = list.get(i); 
    // do something with value 
} 

Si la liste est une liste chaînée, la première est O (N), alors que le second est O (N^2). En effet, à chaque itération, il doit parcourir la liste (depuis le début ou la fin, en fonction de la valeur de i) jusqu'à atteindre la position i. Cela ne se produit pas lorsque vous utilisez un Iterator ou une boucle foreach.

Une autre bonne raison est que, dans le cas de listes simultanées, l'Iterator peut être cohérent (à savoir, itérer sur un instantané cohérent de la liste effectuée lors de la création de l'itérateur). Cela ne peut pas être le cas avec une itération utilisant les indices de la liste.

Answer 2

Je suis presque certain qu'il est ce qui implique que à boucle à travers tous les éléments d'une liste il est préférable de itérer plutôt que, par exemple:

// possibly slow depending on List implementation used 
for (int i = 0; i < list.size(); ++i) 
{ 
    Foo bar = list.get(i); 
} 

Dans le cas d'un LinkedList où l'accès aléatoire est pas O (1), chaque fois que vous appelez list.get(i) vous devez itérer depuis le début tout le chemin à i ce qui est inutile.

---

Votre exemple de pur accès aléatoire (plutôt que boucle à travers tout) est:

1. Dans le cas d'un LinkedList, plus bavard (mais essentiellement ce que get(i)-t sous le capot)

2. Dans le cas d'un ArrayList, en fait plus lentement que get(i)

Answer 3

Ce que le Javadoc parle est cette situation:

for (int i = 0; i < list.size(); i++) { 
    Object o = list.get(i); 
} 

Si la mise en œuvre de list est un ArrayList alors vous avez raison, l'accès au tableau sous-jacent sera constante de temps pour chaque élément particulier (O(n) pour toute la liste). Cependant, que faire si c'est un LinkedList? Pour accéder à l'élément n dans une liste chaînée, vous devez itérer [0, 1, ... n - 2, n - 1] avant d'arriver à l'élément n. Ceci est maintenant très inefficace si vous faites cela pour chaque élément du tableau.

Par conséquent, une meilleure approche est d'écrire la boucle en utilisant un itérateur:

// uses the iterator under the hood. 
for (Object o : list) { 

} 

Dans ce cas, le ArrayList itérateur juste marcher le long du réseau, donc aussi vite que la première boucle, et pour la LinkedList il garde la trace de la position dans la liste afin que vous ne devez pas marcher toute la liste pour arriver à l'élément suivant.