For-each ou for Iterator ?

Publié dans Java | Marqué avec ,
Share

En Java (comme dans plusieurs langages), il existe plusieurs manières de parcourir une liste d’éléments. Mais entre une boucle for classique, une boucle Iterator et un for-each, il existe quelques différences qu’il est de bon ton de connaître.

ilustration d'une boucle for

Boucle for classique (C-style)

// On an array
for(int i=0; i<myArray.length; i++) {
    int element = myArray[i];
    // do stuff
}

// On a list
for(int i=0; i<myList.size(); i++) {
    MyObject element = myList.get(i);
    // do stuff
}

Tout ce qu’il y a de plus banal et de plus souple. C’est parfait pour un tableau. Par contre, pour une liste (Collection, List, Map, …), ce n’est pas forcément le plus performant, car get(i) a généralement une complexité de O(n) (pour une LinkedList par exemple), donc la boucle est en O(n²). Il vaut mieux utiliser un Iterator car dans ce cas it.next() a, par exigence de spécification, une complexité en O(1). Je dis ça comme si j’avais décortiqué le cœur de Java, mais en fait je l’ai simplement lu sur Stack Overflow. Mais cela parait logique. Si on prend l’exemple d’une liste chaînée en C, pour atteindre le dernier élément, il faut parcourir la liste en entier puisque chaque élément contient un pointeur vers le suivant.
Si vous n’avez jamais entendu parler de complexité algorithmique (sujet passionnant quoiqu’un peu barbant dès qu’il s’agit de passer un examen sur la question), il existait un très bon cours sur le SdZ, mais je ne le retrouve plus. Celui-ci : Théorie – Complexité d’un algorithme a l’air pas mal, quoiqu’un peu trop théorique et avec quelques soucis de mise en page.

Ah au fait, je sais qu’en PHP, pour une boucle de ce type, il valait mieux mettre dans une variable la taille de la liste plutôt que d’utiliser myArray.length à chaque pas de la boucle. Je ne sais pas si c’est toujours le cas, et je ne sais pas si cela est vrai en Java. Le compilateur devrait pouvoir y faire quelque chose… Bref. Il faudrait re-tester ça.

Pour résumer :

  • Classique et simple
  • Très souple : on peut itérer dans tous les sens, commencer où on veut, utiliser plusieurs conditions d’arrêt et même effectuer plusieurs pas d’un coup
  • Parfait pour modifier les éléments d’une liste, attention cependant lors de la suppression d’un élément
  • Attention à la performance pour les listes

Boucle avec un Iterator

for(Iterator<MyObject> it = myList.iterator(); it.hasNext();) {
    MyObject element = it.next();
    // do stuff
}

La syntaxe est un peu étonnante au premier abord, mais on s’y fait vite. Ce type de boucle est plus performant qu’une boucle classique et fournie un véritable accès au contenu d’une liste.
Pour tâche de démystifier la syntaxe :

  • Iterator it = myList.iterator(); : instanciation de l’iterator
  • it.hasNext(); : c’est la condition de sortie « tant qu’il existe un élément suivant »
  • it.next(); : renvoie l’élément courant et place le curseur de l’iterator à l’élément suivant. Un autre appel à it.next() dans le même pas de boucle dépilera un deuxième élément.

Pour résumer :

  • Syntaxe un peu complexe
  • Assez souple : on peut itérer dans tous les sens (en utilisant un ListIterator), utiliser plusieurs conditions d’arrêt et effectuer plusieurs pas d’un coup
  • Parfait pour modifier / supprimer des éléments d’une liste
  • Performant

Boucle foreach

for(MyObject element : myList) {
    // do stuff
}

Voilà du joli sucre syntaxique ! Comme cela est bien expliqué et résumé dans l’article For-each loop : si myList implémente l’interface Iterator (comme toutes les listes et les maps Java par exemple), alors une boucle for Iterator sera utilisée, sinon c’est une boucle for classique qui fera le boulot.
Donc en terme de performance, il n’y a pas de différences avec les deux autres manières d’écrire une boucle. Comme le démontre Paul Wagland dans ce topic Stack Overflow Which is more efficient, a for-each loop, or an iterator?, au final, le même byte code Java est utilisé.
On pourrait être tenter d’utiliser cette syntaxe à tout va, mais attention. Il ne faut pas supprimer un élément d’une liste en utilisant cette syntaxe, au risque de créer une exception. De même, la modification pause problème, mais je n’ai pas encore compris pourquoi. On n’a pas la bonne référence ? Admettons qu’on ait une copie (de la référence ?), cela veut-il dire qu’on peut copier cette « copie » pour l’utiliser plus tard ? Peut-être ais-je trop fait de C++ ces derniers temps…

Pour résumer :

  • Super syntaxe
  • Parfait pour lire les éléments d’une liste. Ne pas supprimer / modifier des éléments avec cette syntaxe.
  • Aussi performant qu’un iterator (c’en est un)

En savoir plus

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*