Was ist effizienter, eine für jede Schleife oder ein Iterator?

Welches ist der effizienteste Weg, um eine Sammlung zu durchlaufen?

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

oder

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

Bitte beachten Sie, dass dies kein genaues Duplikat von diesem , diesem , diesem oder jenem ist , obwohl eine der Antworten auf die letzte Frage nahe kommt. Der Grund dafür, dass dies kein Betrug ist, ist, dass die meisten von ihnen Schleifen vergleichen, bei denen Sie get(i)innerhalb der Schleife aufrufen , anstatt den Iterator zu verwenden.

Wie auf Meta vorgeschlagen, werde ich meine Antwort auf diese Frage veröffentlichen.

Wenn Sie nur durch die Sammlung wandern, um alle Werte zu lesen, gibt es keinen Unterschied zwischen der Verwendung eines Iterators oder der neuen for-Schleifensyntax, da die neue Syntax nur den Iterator unter Wasser verwendet.

Wenn Sie jedoch mit Schleife die alte "c-style" Schleife meinen:

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

Dann kann die neue for-Schleife oder der neue Iterator abhängig von der zugrunde liegenden Datenstruktur viel effizienter sein. Der Grund dafür ist, dass es sich bei einigen Datenstrukturen get(i)um eine O (n) -Operation handelt, wodurch die Schleife zu einer O (n ² ) -Operation wird. Eine herkömmliche verknüpfte Liste ist ein Beispiel für eine solche Datenstruktur. Alle Iteratoren haben als Grundanforderung next()eine O (1) -Operation, wodurch die Schleife O (n) wird.

Vergleichen Sie die generierten Bytecodes aus den folgenden beiden Java-Snippets, um zu überprüfen, ob der Iterator von der neuen for-Schleifensyntax unter Wasser verwendet wird. Zuerst die for-Schleife:

List<Integer>  a = new ArrayList<Integer>();
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

Und zweitens der Iterator:

List<Integer>  a = new ArrayList<Integer>();
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

Wie Sie sehen können, ist der generierte Bytecode praktisch identisch, sodass die Verwendung beider Formulare keine Leistungseinbußen mit sich bringt. Daher sollten Sie die Form der Schleife wählen, die für Sie am ästhetischsten ist, für die meisten Personen, die für jede Schleife die richtige sind, da diese weniger Code für das Boilerplate enthält.

Der Unterschied liegt nicht in der Leistung, sondern in der Leistungsfähigkeit. Wenn Sie eine Referenz direkt verwenden, haben Sie mehr Macht über die explizite Verwendung eines Iteratortyps (z. B. List.iterator () vs. List.listIterator (), obwohl in den meisten Fällen dieselbe Implementierung zurückgegeben wird). Sie haben auch die Möglichkeit, auf den Iterator in Ihrer Schleife zu verweisen. Auf diese Weise können Sie beispielsweise Elemente aus Ihrer Sammlung entfernen, ohne eine ConcurrentModificationException zu erhalten.

z.B

Das ist in Ordnung:

Set<Object> set = new HashSet<Object>();
// add some items to the set

Iterator<Object> setIterator = set.iterator();
while(setIterator.hasNext()){
     Object o = setIterator.next();
     if(o meets some condition){
          setIterator.remove();
     }
}

Dies ist nicht der Fall, da eine gleichzeitige Änderungsausnahme ausgelöst wird:

Set<Object> set = new HashSet<Object>();
// add some items to the set

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}

Um Pauls eigene Antwort zu erweitern, hat er gezeigt, dass der Bytecode auf diesem bestimmten Compiler (vermutlich Suns Javac?) Der gleiche ist, aber es ist nicht garantiert , dass verschiedene Compiler denselben Bytecode generieren, oder? Um zu sehen, was der tatsächliche Unterschied zwischen den beiden ist, gehen wir direkt zur Quelle und überprüfen die Java-Sprachspezifikation, insbesondere 14.14.2, "Die erweiterte for-Anweisung" :

Die erweiterte forAnweisung entspricht einer grundlegenden forAnweisung des Formulars:

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

Mit anderen Worten, das JLS verlangt, dass beide gleichwertig sind. Theoretisch könnte dies marginale Unterschiede im Bytecode bedeuten, aber in Wirklichkeit ist die erweiterte for-Schleife erforderlich, um:

• Rufen Sie die .iterator()Methode auf
• Verwenden .hasNext()
• Stellen Sie die lokale Variable über zur Verfügung .next()

Mit anderen Worten, für alle praktischen Zwecke ist der Bytecode identisch oder nahezu identisch. Es ist schwer, sich eine Compiler-Implementierung vorzustellen, die zu einem signifikanten Unterschied zwischen den beiden führen würde.

Die foreachUnterwelt erstellt dasiterator , ruft hasNext () auf und ruft next () auf, um den Wert zu erhalten. Das Problem mit der Leistung tritt nur auf, wenn Sie etwas verwenden, das den RandomomAccess implementiert.

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

Leistungsprobleme mit der iteratorbasierten Schleife sind folgende:

1. Zuweisen eines Objekts, auch wenn die Liste leer ist ( Iterator<CustomObj> iter = customList.iterator(););
2. iter.hasNext() Während jeder Iteration der Schleife gibt es einen virtuellen Aufruf von invokeInterface (gehen Sie alle Klassen durch und suchen Sie dann vor dem Sprung nach Methodentabellen).
3. Die Implementierung des Iterators muss mindestens 2 Felder nachschlagen, damit hasNext()die Aufrufzahl den Wert erhält: # 1 erhält die aktuelle Anzahl und # 2 erhält die Gesamtanzahl
4. Innerhalb der Body-Schleife gibt es einen weiteren virtuellen Aufruf von invokeInterface iter.next(also: Alle Klassen durchgehen und vor dem Sprung nach Methoden suchen). Außerdem muss nach Feldern gesucht werden: # 1 erhält den Index und # 2 erhält den Verweis auf die Array, um den Offset zu machen (in jeder Iteration).

Eine mögliche Optimierung besteht darin, zu einerindex iteration Suche mit zwischengespeicherter Größe zu wechseln :

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

Hier haben wir:

1. Ein Aufruf der virtuellen Methode invokeInterface customList.size()beim ersten Erstellen der for-Schleife, um die Größe zu ermitteln
2. Der Aufruf der get-Methode customList.get(x)während der body for-Schleife ist eine Feldsuche für das Array und kann dann den Offset in das Array ausführen

Wir haben eine Menge Methodenaufrufe und Feldsuchen reduziert. Dies möchten Sie nicht mit LinkedListoder mit etwas tun , das kein RandomAccessSammlungsobjekt ist, sonst customList.get(x)wird das zu etwas, das das LinkedListbei jeder Iteration durchlaufen muss.

Dies ist perfekt, wenn Sie wissen, dass es sich um eine beliebige RandomAccessListensammlung handelt.

foreachverwendet sowieso Iteratoren unter der Haube. Es ist wirklich nur syntaktischer Zucker.

Betrachten Sie das folgende Programm:

import java.util.List;
import java.util.ArrayList;

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

Lassen Sie uns kompilieren es mit javac Whatever.java,
und lesen Sie den zerlegten Bytecode main(), mit 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

Wir können sehen, dass foreachsich das zu einem Programm zusammensetzt, das:

• Erstellt einen Iterator mit List.iterator()
• If Iterator.hasNext(): ruft Iterator.next()die Schleife auf und setzt sie fort

Was "Warum wird diese nutzlose Schleife nicht aus dem kompilierten Code heraus optimiert? Wir können sehen, dass sie nichts mit dem Listenelement zu tun hat": Nun, es ist Ihnen möglich, Ihre iterierbare Schleife so zu codieren, dass sie .iterator()Nebenwirkungen hat , oder so, das .hasNext()hat Nebenwirkungen oder bedeutsame Konsequenzen.

Sie können sich leicht vorstellen, dass eine iterable Darstellung einer scrollbaren Abfrage aus einer Datenbank dramatische .hasNext()Auswirkungen hat (z. B. Kontaktaufnahme mit der Datenbank oder Schließen eines Cursors, weil Sie das Ende der Ergebnismenge erreicht haben).

Obwohl wir also beweisen können, dass im Schleifenkörper nichts passiert, ist es teurer (unlösbar?) Zu beweisen, dass beim Iterieren nichts Sinnvolles / Konsequenzielles passiert. Der Compiler muss diesen leeren Schleifenkörper im Programm belassen.

Das Beste, auf das wir hoffen können, ist eine Compiler- Warnung . Es ist interessant, dass javac -Xlint:all Whatever.javauns nicht vor diesem leeren Schleifenkörper gewarnt wird. IntelliJ IDEA tut dies jedoch. Zugegeben, ich habe IntelliJ für die Verwendung von Eclipse Compiler konfiguriert, aber das ist möglicherweise nicht der Grund dafür.

Iterator ist eine Schnittstelle im Java Collections-Framework, die Methoden zum Durchlaufen oder Durchlaufen einer Sammlung bereitstellt.

Sowohl der Iterator als auch die for-Schleife verhalten sich ähnlich, wenn Sie lediglich eine Sammlung durchlaufen möchten, um ihre Elemente zu lesen.

for-each ist nur eine Möglichkeit, die Sammlung zu durchlaufen.

Beispielsweise:

List<String> messages= new ArrayList<>();

//using for-each loop
for(String msg: messages){
    System.out.println(msg);
}

//using iterator 
Iterator<String> it = messages.iterator();
while(it.hasNext()){
    String msg = it.next();
    System.out.println(msg);
}

Und for-each-Schleife kann nur für Objekte verwendet werden, die die Iteratorschnittstelle implementieren.

Nun zurück zum Fall von for-Schleife und Iterator.

Der Unterschied entsteht, wenn Sie versuchen, eine Sammlung zu ändern. In diesem Fall ist der Iterator aufgrund seiner Fail-Fast-Eigenschaft effizienter . dh. Es prüft, ob sich die Struktur der zugrunde liegenden Sammlung geändert hat, bevor das nächste Element durchlaufen wird. Wenn Änderungen gefunden werden, wird die ConcurrentModificationException ausgelöst .

(Hinweis: Diese Funktionalität des Iterators gilt nur für Sammlungsklassen im Paket java.util. Sie gilt nicht für gleichzeitige Sammlungen, da sie von Natur aus ausfallsicher sind.)

Wir sollten vermeiden, traditionelle for-Schleifen zu verwenden, wenn wir mit Sammlungen arbeiten. Der einfache Grund, den ich geben werde, ist, dass die Komplexität der for-Schleife in der Größenordnung von O (sqr (n)) liegt und die Komplexität des Iterators oder sogar der erweiterten for-Schleife nur O (n) beträgt. Es ergibt sich also ein Leistungsunterschied. Nehmen Sie einfach eine Liste mit etwa 1000 Elementen und drucken Sie sie auf beide Arten aus. und drucken Sie auch den Zeitunterschied für die Ausführung. Sie können den Unterschied sehen.