Quale è più efficiente, un ciclo for-each o un iteratore?

Qual è il modo più efficace per attraversare una collezione?

List a = new ArrayList(); for (Integer integer : a) { integer.toString(); } 

o

 List a = new ArrayList(); for (Iterator iterator = a.iterator(); iterator.hasNext();) { Integer integer = (Integer) iterator.next(); integer.toString(); } 

Si noti che questo non è un duplicato esatto di questo , questo , questo o questo , anche se una delle risposte all’ultima domanda si avvicina. La ragione per cui questo non è un problema, è che la maggior parte di questi sta confrontando i loop in cui chiamate get(i) all’interno del ciclo, piuttosto che usare l’iteratore.

Come suggerito su Meta , invierò la mia risposta a questa domanda.

Se stai semplicemente vagando per la collezione per leggere tutti i valori, allora non c’è differenza tra l’uso di un iteratore o la nuova syntax del ciclo for, poiché la nuova syntax usa l’iteratore sott’acqua.

Se tuttavia, intendete per ciclo il vecchio ciclo “c-style”:

 for(int i=0; i 

Quindi il nuovo ciclo for, o iterator, può essere molto più efficiente, a seconda della struttura dati sottostante. La ragione di ciò è che per alcune strutture dati, get(i) è un'operazione O (n), che rende il ciclo un'operazione O (n 2 ). Una lista collegata tradizionale è un esempio di tale struttura di dati. Tutti gli iteratori hanno come requisito fondamentale che next() dovrebbe essere un'operazione O (1), rendendo il ciclo O (n).

Per verificare che l'iteratore sia utilizzato sott'acqua dalla nuova syntax del ciclo for, confrontare i bytecode generati dai seguenti due snippet Java. Prima il ciclo for:

 List a = new ArrayList(); for (Integer integer : a) { integer.toString(); } // Byte code ALOAD 1 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator; ASTORE 3 GOTO L2 L3 ALOAD 3 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object; CHECKCAST java/lang/Integer ASTORE 2 ALOAD 2 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String; POP L2 ALOAD 3 INVOKEINTERFACE java/util/Iterator.hasNext()Z IFNE L3 

E in secondo luogo, l'iteratore:

 List a = new ArrayList(); for (Iterator iterator = a.iterator(); iterator.hasNext();) { Integer integer = (Integer) iterator.next(); integer.toString(); } // Bytecode: ALOAD 1 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator; ASTORE 2 GOTO L7 L8 ALOAD 2 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object; CHECKCAST java/lang/Integer ASTORE 3 ALOAD 3 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String; POP L7 ALOAD 2 INVOKEINTERFACE java/util/Iterator.hasNext()Z IFNE L8 

Come potete vedere, il codice byte generato è effettivamente identico, quindi non vi è alcuna penalità di prestazioni per l'utilizzo di entrambi i moduli. Pertanto, dovresti scegliere la forma di loop che ti è più esteticamente attraente, per la maggior parte delle persone che sarà il ciclo for-each, in quanto ha meno codice boilerplate.

La differenza non è nelle prestazioni, ma nella capacità. Quando si utilizza direttamente un riferimento, si ha più potere sull’uso esplicito di un tipo di iteratore (ad es. List.iterator () vs. List.listIterator (), sebbene nella maggior parte dei casi restituiscano la stessa implementazione). Hai anche la possibilità di fare riferimento a Iterator nel tuo ciclo. Questo ti permette di fare cose come rimuovere oggetti dalla tua collezione senza ottenere una ConcurrentModificationException.

per esempio

Questo va bene:

 Set set = new HashSet(); // add some items to the set Iterator setIterator = set.iterator(); while(setIterator.hasNext()){ Object o = setIterator.next(); if(o meets some condition){ setIterator.remove(); } } 

Questo non è, poiché genererà un’eccezione di modifica simultanea:

 Set set = new HashSet(); // add some items to the set for(Object o : set){ if(o meets some condition){ set.remove(o); } } 

Per espandere la risposta di Paul, ha dimostrato che il bytecode è lo stesso su quel particolare compilatore (presumibilmente il javac di Sun?) Ma non è garantito che diversi compilatori generino lo stesso bytecode, giusto? Per vedere quale sia la differenza effettiva tra i due, andiamo direttamente al sorgente e controlliamo la specifica del linguaggio Java, in particolare 14.14.2, “L’istruzione avanzata per” :

L’istruzione for enhanced è equivalente a una dichiarazione di base del modulo:

 for (I #i = Expression.iterator(); #i.hasNext(); ) { VariableModifiers(opt) Type Identifier = #i.next(); Statement } 

In altre parole, è richiesto dal JLS che i due siano equivalenti. In teoria ciò potrebbe significare differenze marginali nel bytecode, ma in realtà è necessario il ciclo avanzato per:

  • Richiama il metodo .iterator()
  • Usa .hasNext()
  • Rendi disponibile la variabile locale tramite .next()

Quindi, in altre parole, per tutti gli scopi pratici il bytecode sarà identico o quasi identico. È difficile prevedere un’implementazione del compilatore che possa comportare una differenza significativa tra i due.

Potrebbe essere necessario utilizzare gli iteratori se è necessario modificare la raccolta nel ciclo. Il primo approccio farà eccezione.

 for (String i : list) { System.out.println(i); list.remove(i); // throws exception } Iterator it=list.iterator(); while (it.hasNext()){ System.out.println(it.next()); it.remove(); // valid here } 

Iterator è un’interfaccia nel framework Collections di Java che fornisce metodi per attraversare o iterare su una raccolta.

Sia l’iteratore che il ciclo agiscono in modo simile quando il tuo motivo è semplicemente attraversare una raccolta per leggere i suoi elementi.

for-each è solo un modo per scorrere la collezione.

Per esempio:

 List messages= new ArrayList<>(); //using for-each loop for(String msg: messages){ System.out.println(msg); } //using iterator Iterator it = messages.iterator(); while(it.hasNext()){ String msg = it.next(); System.out.println(msg); } 

E per ogni ciclo può essere utilizzato solo su oggetti che implementano l’interfaccia iteratore.

Ora torniamo al caso di for loop e iterator.

La differenza arriva quando provi a modificare una collezione. In questo caso, iteratore è più efficiente a causa della sua proprietà fail-fast . vale a dire. controlla eventuali modifiche nella struttura della raccolta sottostante prima di iterare sull’elemento successivo. Se sono state trovate modifiche, verrà lanciata ConcurrentModificationException .

(Nota: questa funzionalità di iteratore è applicabile solo nel caso di classi di raccolta nel pacchetto java.util. Non è applicabile per le raccolte simultanee poiché sono di natura fail-safe)

foreach usa comunque gli iteratori sotto il cofano. È davvero solo zucchero sintattico.

Considera il seguente programma:

 import java.util.List; import java.util.ArrayList; public class Whatever { private final List list = new ArrayList<>(); public void main() { for(Integer i : list) { } } } 

Compiliamolo con javac Whatever.java ,
E leggi il bytecode smontato di main() , usando javap -c Whatever :

 public void main(); Code: 0: aload_0 1: getfield #4 // Field list:Ljava/util/List; 4: invokeinterface #5, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator; 9: astore_1 10: aload_1 11: invokeinterface #6, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z 16: ifeq 32 19: aload_1 20: invokeinterface #7, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object; 25: checkcast #8 // class java/lang/Integer 28: astore_2 29: goto 10 32: return 

Possiamo vedere che foreach compila fino a un programma che:

  • Crea iteratore usando List.iterator()
  • Se Iterator.hasNext() : richiama Iterator.next() e continua il ciclo

Per quanto riguarda “perché questo loop inutile non viene ottimizzato dal codice compilato? Possiamo vedere che non fa nulla con l’elemento della lista”: beh, è ​​ansible codificare il tuo iterable in modo tale che .iterator() ha effetti collaterali, o così .hasNext() ha effetti collaterali o conseguenze significative.

Potresti facilmente immaginare che un iterabile che rappresenta una query scorrevole da un database possa fare qualcosa di drammatico su .hasNext() (come contattare il database, o chiudere un cursore perché hai raggiunto la fine del set di risultati).

Quindi, anche se possiamo provare che nulla accade nel corpo del loop … è più costoso (intrattabile?) Dimostrare che non accade nulla di significativo / consequenziale quando iteriamo. Il compilatore deve lasciare questo corpo del ciclo vuoto nel programma.

Il meglio che potremmo sperare sarebbe un avvertimento del compilatore. È interessante javac -Xlint:all Whatever.java che javac -Xlint:all Whatever.java non ci avvisa di questo corpo vuoto. IntelliJ IDEA però. Devo ammettere che ho configurato IntelliJ per usare Eclipse Compiler, ma questo potrebbe non essere il motivo per cui.

inserisci la descrizione dell'immagine qui

Il underhood foreach sta creando l’ iterator , chiamando hasNext () e chiamando next () per ottenere il valore; Il problema con la performance arriva solo se stai usando qualcosa che implementa RandomomAccess.

 for (Iterator iter = customList.iterator(); iter.hasNext()){ CustomObj custObj = iter.next(); .... } 

I problemi di prestazioni con il ciclo basato su iteratore sono perché sono:

  1. allocare un object anche se l’elenco è vuoto ( Iterator iter = customList.iterator(); );
  2. iter.hasNext() durante ogni iterazione del ciclo c’è una chiamata virtuale invokeInterface (passa attraverso tutte le classi, quindi effettua la ricerca della tabella dei metodi prima del salto).
  3. l’implementazione dell’iteratore deve eseguire almeno 2 ricerche di campi per fare in modo che hasNext() chiami il valore: # 1 ottiene il conteggio corrente e # 2 ottiene il conteggio totale
  4. all’interno del loop del corpo, c’è un’altra chiamata virtuale invokeInterface iter.next (quindi: passa attraverso tutte le classi ed effettua la ricerca della tabella dei metodi prima del salto) e deve anche cercare i campi: # 1 ottiene l’indice e # 2 ottiene il fare riferimento alla matrice per eseguire l’offset (in ogni iterazione).

Una potenziale ottimizzazione è quella di passare a index iteration con la ricerca della dimensione cache:

 for(int x = 0, size = customList.size(); x < size; x++){ CustomObj custObj = customList.get(x); ... } 

Qui abbiamo:

  1. una chiamata al metodo virtuale invokeInterface customList.size() sulla creazione iniziale del ciclo for per ottenere la dimensione
  2. il metodo get chiama customList.get(x) durante il body per loop, che è una ricerca di campo per l'array e quindi può eseguire l'offset nell'array

Abbiamo ridotto una tonnellata di chiamate di metodi, ricerche sul campo. Questo non si vuole fare con LinkedList o con qualcosa che non sia una raccolta di RandomAccess , altrimenti customList.get(x) si trasformsrà in qualcosa che deve attraversare la LinkedList ad ogni iterazione.

Questo è perfetto quando sai che si tratta di una raccolta di elenchi basata su RandomAccess .

Evitiamo di usare il ciclo for tradizionale mentre lavoriamo con le collezioni. La semplice ragione che darò è che la complessità del ciclo for è dell’ordine O (sqr (n)) e la complessità di Iterator o anche il ciclo for enhanced è solo O (n). In questo modo si ottiene una differenza di rendimento. Basta prendere un elenco di circa 1000 articoli e stamparlo in entrambi i modi. e anche stampare la differenza di tempo per l’esecuzione. Puoi vedere la differenza.