Prestazioni del ciclo for tradizionale vs Iterator/foreach in Java

Question

Sono disponibili risultati di test delle prestazioni nel confronto tra loop tradizionale e Iterator mentre si attraversano ArrayList, HashMap e altre raccolte?

O semplicemente perché dovrei usare Iterator per loop o viceversa?

Answer 1

Supponendo che questo è quello che volevi dire:

// traditional for loop 
for (int i = 0; i < collection.size(); i++) { 
    T obj = collection.get(i); 
    // snip 
} 

// using iterator 
Iterator<T> iter = collection.iterator(); 
while (iter.hasNext()) { 
    T obj = iter.next(); 
    // snip 
} 

// using iterator internally (confirm it yourself using javap -c) 
for (T obj : collection) { 
    // snip 
} 

Iterator è più veloce per le collezioni che non hanno accesso casuale (ad esempio TreeSet, HashMap, LinkedList). Per le matrici e le liste di array, le differenze di prestazioni dovrebbero essere trascurabili.

Edit: Credo che il micro-benchmarking sia la radice del male, proprio come l'ottimizzazione iniziale. Ma ripeto, penso sia bello avere un sentimento per le implicazioni di cose così banali. Quindi Ho eseguito a small test:

• iterazioni su una LinkedList e un ArrayList respecively
• con 100.000 stringhe "casuali"
• riassumendo la loro lunghezza (solo qualcosa per evitare che il compilatore ottimizza via l'intero anello)
• utilizzando tutti gli stili 3 ciclo (iteratore, per ciascuno, per con il contatore)

risultati sono simili per tutti, ma "per con il contatore" con LinkedList. Tutti gli altri cinque hanno impiegato meno di 20 millisecondi per scorrere l'intera lista. Utilizzo di list.get(i) su una lista collegata 100.000 volte ha impiegato più di 2 minuti (!) Per completare (60.000 volte più lento). Wow! :) Quindi è meglio usare un iteratore (usando esplicitamente o implicitamente per ciascuno), specialmente se non si conosce il tipo e la dimensione della lista con cui si sta trattando.

Answer 2

Utilizzare JAD o JD-GUI in base al codice generato e si vedrà che non vi è alcuna differenza reale. Il vantaggio della nuova forma di iteratore è che sembra più pulito nella base di codice.

Modifica: vedo dalle altre risposte che in realtà si intende la differenza tra l'utilizzo di get (i) rispetto a un iteratore. Ho preso la domanda iniziale per indicare la differenza tra il vecchio e il nuovo modo di usare l'iteratore.

L'utilizzo di get (i) e la gestione del proprio contatore, in particolare per le classi List non è una buona idea, per i motivi indicati nella risposta accettata.

Answer 3

Le prestazioni sono simili nella maggior parte dei casi.

Tuttavia, ogni volta che un codice riceve un elenco, e loop in esso, non è noto caso:
Iterator è il modo migliore per tutte le implementazioni Lista che non implementano RandomAccess (esempio: LinkedList).

Il motivo è che per questi elenchi, l'accesso a un elemento per indice non è un'operazione a tempo costante.

Quindi è possibile considerare l'Iterator più solido (per i dettagli di implementazione).

---

Come sempre, le prestazioni non devono essere nascoste problemi di leggibilità.
Il ciclo java5 foreach è un grande successo su questo aspetto :-)

Answer 4

Uno dei migliori motivi per utilizzare un iteratore su l'i ++ sintassi è che non tutte le strutture di dati supportano l'accesso casuale e tanto meno lo hanno buone prestazioni. Dovresti anche programmare l'elenco o l'interfaccia di raccolta in modo che se in seguito decidessi che un'altra struttura di dati sarebbe più efficiente, potresti essere in grado di sostituirla senza un intervento chirurgico massiccio. In quel caso (il caso della codifica su un'interfaccia) non si conoscono necessariamente i dettagli dell'implementazione ed è probabilmente più saggio rimandarlo alla struttura dati stessa.

Answer 5

Uno dei motivi per cui ho imparato ad attenervisi è che semplifica i cicli annidati, in particolare su cicli di dimensioni 2+. Tutti gli i, i j e i k che potresti finire per manipolare possono creare confusione molto rapidamente.

Answer 6

Il primo motivo per utilizzare un iteratore è ovvia correttezza. Se usi un indice manuale, potrebbero esserci degli errori off-by-one molto innocui che puoi vedere solo se guardi da vicino: hai iniziato da 1 o da 0? Hai finito allo length - 1? Hai usato < o <=? Se si utilizza un iteratore, è molto più facile vedere che sta davvero iterando l'intero array. "Dì quello che fai, fai quello che dici."

Il secondo motivo è l'accesso uniforme a diverse strutture di dati. È possibile accedere in modo efficiente a un array tramite un indice, ma è meglio attraversare un elenco collegato ricordando l'ultimo elemento a cui si accede (altrimenti si ottiene "Shlemiel the painter"). Una hashmap è ancora più complicata. Fornendo un'interfaccia uniforme da queste e da altre strutture di dati (ad es. Puoi anche fare attraversamenti di alberi), ottieni di nuovo un'ovvia correttezza. La logica di attraversamento deve essere implementata una sola volta e il codice che la utilizza può concisamente "dire quello che fa e fare ciò che dice".

Answer 7

+1 a quanto detto sfussenegger. Cordiali saluti, se si utilizza un iteratore esplicito o implicito (vale a dire per ciascuno) non farà una differenza di prestazioni perché compilano lo stesso codice byte.

Answer 8

Non credo che

for (T obj : collection) { 

calcola .size() ogni volta attraverso il ciclo ed è quindi più veloce di

for (int i = 0; i < collection.size(); i++) { 

Answer 9

Sì, lo fa fare la differenza su collezioni che sono accesso non casuale basato come LinkedList. Una lista collegata internamente è implementata da nodi che puntano al successivo (partendo da un nodo principale).

Il metodo get (i) in un elenco collegato inizia dal nodo principale e naviga attraverso i collegamenti fino al nodo iesimo. Quando si esegue iterazione sull'elenco collegato utilizzando un ciclo for tradizionale, si ricomincia dal nodo principale ogni volta, quindi l'attraversamento complessivo diventa il tempo quadratico.

for(int i = 0; i< list.size(); i++) { 
    list.get(i); //this starts everytime from the head node instead of previous node 
} 

Mentre per ogni itera sulla iteratore ottenuto dalla lista concatenata e chiede il suo metodo next(). L'iteratore mantiene gli stati dell'ultimo accesso e quindi non inizia da capo ogni volta.