Quel est le plus efficace, une boucle pour chaque, ou un itérateur?

Quelle est la manière la plus efficace de parcourir une collection?

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

ou

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

Veuillez noter que ce n'est pas un double exact de ceci , ceci , ceci ou ceci , bien qu'une des réponses à la dernière question soit proche. La raison pour laquelle ce n'est pas dupe, c'est que la plupart d'entre elles comparent des boucles où vous appelez get(i)à l'intérieur de la boucle, plutôt que d'utiliser l'itérateur.

Comme suggéré sur Meta, je posterai ma réponse à cette question.

Si vous vous promenez dans la collection pour lire toutes les valeurs, il n'y a aucune différence entre l'utilisation d'un itérateur ou la nouvelle syntaxe de boucle for, car la nouvelle syntaxe utilise simplement l'itérateur sous l'eau.

Si toutefois, vous entendez par boucle l'ancienne boucle "de style c":

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

La nouvelle boucle for, ou itérateur, peut alors être beaucoup plus efficace, selon la structure de données sous-jacente. La raison en est que pour certaines structures de données, il get(i)s'agit d'une opération O (n), qui fait de la boucle une opération O (n ² ). Une liste chaînée traditionnelle est un exemple d'une telle structure de données. Tous les itérateurs ont comme exigence fondamentale qui next()devrait être une opération O (1), ce qui rend la boucle O (n).

Pour vérifier que l'itérateur est utilisé sous l'eau par la nouvelle syntaxe de boucle for, comparez les bytecodes générés à partir des deux extraits de code Java suivants. D'abord la boucle for:

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

Et deuxièmement, l'itérateur:

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

Comme vous pouvez le voir, le code d'octet généré est effectivement identique, il n'y a donc aucune pénalité de performance à utiliser l'un ou l'autre formulaire. Par conséquent, vous devez choisir la forme de boucle la plus attrayante pour vous, pour la plupart des personnes qui seront la boucle pour chaque, car elle a moins de code passe-partout.

La différence n'est pas dans les performances, mais dans les capacités. Lorsque vous utilisez directement une référence, vous avez plus de pouvoir sur l'utilisation explicite d'un type d'itérateur (par exemple, List.iterator () par rapport à List.listIterator (), bien que dans la plupart des cas, ils renvoient la même implémentation). Vous avez également la possibilité de référencer l'itérateur dans votre boucle. Cela vous permet de supprimer des éléments de votre collection sans obtenir une exception ConcurrentModificationException.

par exemple

C'est acceptable:

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();
     }
}

Ce n'est pas le cas, car cela lèvera une exception de modification simultanée:

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

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

Pour développer la réponse de Paul, il a démontré que le bytecode est le même sur ce compilateur particulier (vraisemblablement le javac de Sun?) Mais différents compilateurs ne sont pas garantis pour générer le même bytecode, non? Pour voir quelle est la différence réelle entre les deux, allons directement à la source et vérifions les spécifications du langage Java, en particulier 14.14.2, "La déclaration améliorée pour" :

L' forinstruction améliorée équivaut à une forinstruction de base du formulaire:

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

En d'autres termes, le JLS exige que les deux soient équivalents. En théorie, cela pourrait signifier des différences marginales dans le bytecode, mais en réalité, la boucle for améliorée est nécessaire pour:

• Appeler la .iterator()méthode
• Utilisation .hasNext()
• Rendre la variable locale disponible via .next()

En d'autres termes, à toutes fins pratiques, le bytecode sera identique ou presque identique. Il est difficile d'envisager une implémentation de compilateur qui entraînerait une différence significative entre les deux.

Le foreachunderhood crée leiterator , appelant hasNext () et appelant next () pour obtenir la valeur; Le problème avec les performances ne survient que si vous utilisez quelque chose qui implémente RandomomAccess.

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

Les problèmes de performances avec la boucle basée sur l'itérateur sont dus au fait que:

1. allouer un objet même si la liste est vide ( Iterator<CustomObj> iter = customList.iterator(););
2. iter.hasNext() à chaque itération de la boucle, il y a un appel virtuel invokeInterface (parcourez toutes les classes, puis recherchez la table des méthodes avant le saut).
3. l'implémentation de l'itérateur doit faire au moins 2 recherches de champs afin que hasNext()la valeur de l'appel soit la valeur: # 1 get current count et # 2 get total count
4. à l'intérieur de la boucle de corps, il y a un autre appel virtuel invokeInterface iter.next(donc: parcourez toutes les classes et effectuez la recherche de table de méthode avant le saut) et doit également faire la recherche de champs: # 1 obtenir l'index et # 2 obtenir la référence à la tableau pour y faire l'offset (à chaque itération).

Une optimisation potentielle consiste à passer à unindex iteration avec la recherche de taille en cache:

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

Ici nous avons:

1. un appel de méthode virtuelle invokeInterface customList.size()lors de la création initiale de la boucle for pour obtenir la taille
2. l'appel de méthode get customList.get(x)pendant le corps de la boucle, qui est une recherche de champ dans le tableau et peut ensuite effectuer le décalage dans le tableau

Nous avons réduit une tonne d'appels de méthode, de recherches sur le terrain. Cela vous ne voulez pas faire avec LinkedListou avec quelque chose qui n'est pas un RandomAccessobj de collection, sinon cela customList.get(x)va se transformer en quelque chose qui doit traverser le LinkedListà chaque itération.

C'est parfait lorsque vous savez qu'il s'agit d'une RandomAccesscollection de listes basée.

foreachutilise de toute façon des itérateurs sous le capot. Ce n'est vraiment que du sucre syntaxique.

Considérez le programme suivant:

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) {
        }
    }
}

Compilons-le avec javac Whatever.java,
Et lisons le bytecode démonté de main(), en utilisant 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

Nous pouvons voir que se foreachcompile en un programme qui:

• Crée un itérateur à l'aide List.iterator()
• Si Iterator.hasNext(): invoque Iterator.next()et continue la boucle

Quant à "pourquoi cette boucle inutile n'est-elle pas optimisée à partir du code compilé? Nous pouvons voir qu'elle ne fait rien avec l'élément de liste": eh bien, il vous est possible de coder votre itérable de manière à .iterator()avoir des effets secondaires , ou alors qui .hasNext()a des effets secondaires ou des conséquences significatives.

Vous pourriez facilement imaginer qu'un itérable représentant une requête déroulante à partir d'une base de données pourrait faire quelque chose de dramatique .hasNext()(comme contacter la base de données ou fermer un curseur parce que vous avez atteint la fin de l'ensemble de résultats).

Donc, même si nous pouvons prouver que rien ne se passe dans le corps de la boucle… il est plus coûteux (insoluble?) De prouver que rien de significatif / de conséquent ne se produit lorsque nous itérons. Le compilateur doit laisser ce corps de boucle vide dans le programme.

Le mieux que nous puissions espérer serait un avertissement du compilateur . Il est intéressant que javac -Xlint:all Whatever.javane pas nous mettre en garde contre ce corps de la boucle vide. IntelliJ IDEA le fait cependant. Certes, j'ai configuré IntelliJ pour utiliser Eclipse Compiler, mais ce n'est peut-être pas la raison.

Iterator est une interface dans le cadre des collections Java qui fournit des méthodes pour parcourir ou parcourir une collection.

L'itérateur et la boucle for agissent de manière similaire lorsque votre motif est de simplement parcourir une collection pour lire ses éléments.

for-each n'est qu'une façon de parcourir la Collection.

Par exemple:

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);
}

Et la boucle for-each ne peut être utilisée que sur des objets implémentant l'interface de l'itérateur.

Revenons maintenant au cas de la boucle for et de l'itérateur.

La différence survient lorsque vous essayez de modifier une collection. Dans ce cas, l'itérateur est plus efficace en raison de sa propriété fail-fast . c'est à dire. il vérifie toute modification dans la structure de la collection sous-jacente avant d'itérer sur l'élément suivant. Si des modifications sont trouvées, il lèvera l' exception ConcurrentModificationException .

(Remarque: Cette fonctionnalité de l'itérateur n'est applicable que dans le cas des classes de collection dans le package java.util. Elle n'est pas applicable aux collections simultanées car elles sont de sécurité intrinsèque par nature)

Nous devons éviter d'utiliser la boucle for traditionnelle lors de l'utilisation des collections. La raison simple que je donnerai est que la complexité de la boucle for est de l'ordre O (sqr (n)) et la complexité de l'itérateur ou même la boucle for améliorée est juste O (n). Cela donne donc une différence de performance. Prenez simplement une liste de quelque 1000 articles et imprimez-la dans les deux sens. et également imprimer la différence de temps pour l'exécution. Vous pouvez voir la différence.