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

206

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.

Paul Wagland
quelle
Ich würde denken, dass es keinen Unterschied macht, da sein Java und der Vorlagenmechanismus kaum mehr als syntaktischer Zucker sind
Hassan Syed
Mögliches Duplikat: stackoverflow.com/questions/89891/…
OMG Ponys
2
@OMG Ponys: Ich glaube nicht, dass dies ein Duplikat ist, da dies die Schleife nicht mit dem Iterator vergleicht, sondern fragt, warum die Sammlungen Iteratoren zurückgeben, anstatt die Iteratoren direkt in der Klasse selbst zu haben.
Paul Wagland

Antworten:

263

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 2 ) -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.

Paul Wagland
quelle
4
Ich glaube, er hat das Gegenteil gesagt, dass foo.get (i) viel weniger effizient sein kann. Denken Sie an LinkedList. Wenn Sie ein foo.get (i) in der Mitte einer LinkedList ausführen, müssen alle vorherigen Knoten durchlaufen werden, um zu i zu gelangen. Ein Iterator hingegen behält die zugrunde liegende Datenstruktur im Griff und ermöglicht es Ihnen, nacheinander über die Knoten zu gehen.
Michael Krauklis
1
Keine große Sache, aber eine for(int i; i < list.size(); i++) {Stilschleife muss auch list.size()am Ende jeder Iteration ausgewertet werden. Wenn sie verwendet wird, ist es manchmal effizienter, das Ergebnis von list.size()first zwischenzuspeichern.
Brett Ryan
3
Tatsächlich gilt die ursprüngliche Anweisung auch für den Fall von ArrayList und allen anderen, die die RandomAccess-Schnittstelle implementieren. Die "C-artige" Schleife ist schneller als die Iterator-basierte. docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html
andresp
4
Ein Grund, die alte Schleife im C-Stil anstelle des Iterator-Ansatzes zu verwenden, unabhängig davon, ob es sich um die foreach- oder die desugar'd-Version handelt, ist Müll. Viele Datenstrukturen instanziieren einen neuen Iterator, wenn .iterator () aufgerufen wird. Auf sie kann jedoch mithilfe der C-Schleife ohne Zuordnung zugegriffen werden. Dies kann in bestimmten Hochleistungsumgebungen wichtig sein, in denen versucht wird, (a) das Auftreffen auf den Allokator oder (b) die Speicherbereinigung zu vermeiden.
Dan
3
Genau wie bei einem anderen Kommentar ist bei ArrayLists die for (int i = 0 ....) - Schleife etwa 2x schneller als die Verwendung des Iterators oder des for (:) -Ansatzes, sodass sie wirklich von der zugrunde liegenden Struktur abhängt. Nebenbei bemerkt ist das Iterieren von HashSets auch sehr teuer (viel mehr als eine Array-Liste). Vermeiden Sie daher solche wie die Pest (wenn Sie können).
Leo
106

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);
     }
}
Michael Krauklis
quelle
12
Dies ist sehr richtig, obwohl es die Frage, die ich mit +1 beantwortet habe, nicht direkt beantwortet, um informativ zu sein und die logische Folgefrage zu beantworten.
Paul Wagland
1
Ja, wir können mit foreach-Schleife auf Sammlungselemente zugreifen, aber wir können sie nicht entfernen, aber wir können Elemente mit Iterator entfernen.
Akash5288
22

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.

Cowan
quelle
Eigentlich war der Test, den ich gemacht habe, mit dem Eclipse-Compiler, aber Ihr allgemeiner Punkt bleibt bestehen. +1
Paul Wagland
3

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.

denis_lor
quelle
1

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.

Geben Sie hier die Bildbeschreibung ein

Birchlabs
quelle
0

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.)

exzentrischerCoder
quelle
1
Ihre Aussage über den Unterschied ist nicht wahr, die für jede Schleife verwendet auch einen Iterator unter Wasser und hat daher das gleiche Verhalten.
Paul Wagland
@Pault Wagland, ich habe meine Antwort geändert. Vielen Dank, dass Sie auf den Fehler hingewiesen haben
exzentrischer
Ihre Updates sind immer noch nicht korrekt. Die beiden Codefragmente, die Sie haben, werden von der Sprache als identisch definiert. Wenn es einen Unterschied im Verhalten gibt, liegt ein Fehler in der Implementierung vor. Der einzige Unterschied besteht darin, ob Sie Zugriff auf den Iterator haben oder nicht.
Paul Wagland
@Paul Wagland Auch wenn Sie die Standardimplementierung von für jede Schleife verwenden, die einen Iterator verwendet, wird dennoch eine Ausnahme ausgelöst, wenn Sie versuchen, die Methode remove () bei gleichzeitigen Vorgängen zu verwenden. Überprüfen Sie die folgenden für weitere Informationen hier
eccentricCoder
1
Mit dem für jede Schleife erhalten Sie keinen Zugriff auf den Iterator, sodass Sie remove nicht aufrufen können. Aber das ist nebensächlich, in Ihrer Antwort behaupten Sie, dass einer threadsicher ist, während der andere nicht. Entsprechend der Sprachspezifikation sind sie gleichwertig, sodass beide nur so threadsicher sind wie die zugrunde liegenden Sammlungen.
Paul Wagland
-8

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.

Chandan
quelle
Bitte fügen Sie einige anschauliche Beispiele hinzu, um Ihre Aussagen zu unterstützen.
Rajesh Pitty
@Chandan Sorry, aber was du geschrieben hast ist falsch. Zum Beispiel: std :: vector ist ebenfalls eine Sammlung, deren Zugriff jedoch O (1) kostet. Eine traditionelle for-Schleife über einen Vektor ist also nur O (n). Ich denke, Sie möchten sagen, wenn der Zugriff auf den darunter liegenden Container Zugriffskosten von O (n) hat, also für std :: list, dann gibt es eine Komplexität von O (n ^ 2). Die Verwendung von Iteratoren in diesem Fall reduziert die Kosten auf O (n), da Iteratoren den direkten Zugriff auf Elemente ermöglichen.
Kaiser
Wenn Sie die Zeitdifferenzberechnung durchführen, stellen Sie sicher, dass beide Sätze sortiert (oder zufällig verteilt, unsortiert) sind, und führen Sie den Test für jeden Satz zweimal aus und berechnen Sie jeweils nur den zweiten Lauf. Überprüfen Sie Ihre Zeitangaben erneut (dies ist eine lange Erklärung, warum Sie den Test zweimal ausführen müssen). Sie müssen (möglicherweise mit Code) demonstrieren, wie dies wahr ist. Ansonsten sind meines Wissens beide hinsichtlich der Leistung identisch, aber nicht hinsichtlich der Leistungsfähigkeit.
Ydobonebi