Discussion :

[felix79]

Je fais plein de parcours de listes (ArrayList pour la pluspart) et je me demande qu'elle est la methode la plus efficace (en temps), un Iterator ou des get en incrementant un indice de boucle ?

[sinok]

Tout dépend du type de liste qur tu utilises

Pour les ArrayList mieux vaut des get, par contre pour une LinkedList, mieux vaut un iterator par exemple.

[professeur shadoko]

voir doc de l'interface RandomAccess

[yann2]

Tout dépend du type de liste qur tu utilises

Pour les ArrayList mieux vaut des get, par contre pour une LinkedList, mieux vaut un iterator par exemple.

Euh si les mecs de chez Sun savent développer ils ont certainement fait une opération en O(1) pour la méthode next() de l'Iterator d'une ArrayList....

Donc il vaut mieux utiliser iterator() pour le type List. Sachant que le gain en performance en utilisant get() sur un ArrayList est null (ou quasi).
En fait je pense que l'opération next() de l'Iterator d'un ArrayList fait simplement un get() sur cette liste.

[EDIT]
Bon ben maintenant j'en suis sûr !
Extrait de AbstractList.Itr.next() :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
                Object obj = get(cursor);
                lastRet = cursor++;
                return obj;

[/EDIT]

[professeur shadoko]

d'accord avec la remarque de Yann

[sinok]

Mouaip sauf que sur l'arrayList il y a tout de même un une petite différence

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
 
        ArrayList l = new ArrayList();
        for(int i =0; i<7000000; i++) {
            l.add(String.valueOf(i));
        }
 
 
 
 
        long start = System.currentTimeMillis();
        long end = System.currentTimeMillis();
 
 
        for (Iterator iter = l.iterator(); iter.hasNext();) {
            iter.next();
 
        }
        end = System.currentTimeMillis();
 
        System.out.println("temps iter: "+(end-start));
 
        start = System.currentTimeMillis();
        for(int i =0; i<l.size(); i++) {
            l.get(i);
        }
 
        end = System.currentTimeMillis();
        System.out.println("temps for: "+(end-start));

Grosso modo le bout de code précédent me donne le résultat suivant:

temps iter: 375
temps for: 47

(et si l'on inverse les calculs (cad le get avant l'iterator c'en est de même)

[yann2]

Resalut

Un différence de 300 ms pour un parcours de 7 millions d'éléments c'est ce que j'appelle une différence quasi nulle. D'autant plus que si tuveux un jour changer ton type ArrayList en LinkedList, tu seras obliger de changer tous tes parcours de liste....

Différence entre next() et get() = 300ms/7 000 000

[adiGuba]

Salut,

Euh si les mecs de chez Sun savent développer ils ont certainement fait une opération en O(1) pour la méthode next() de l'Iterator d'une ArrayList....

Mais l'utilisation de l'Iterator rajoute une couche d'abstraction supplémentaire qui peut s'avérer un peu plus couteuse... et c'est le cas pour les ArrayLists par exemple.

Toutefois cette différence est vraiment minime et ne se ressent que sur des liste de taille vraiment très importante...

Attention cela ne veut pas dire qu'il faut privilégier l'accès via get(), car il peut se révéler catastrophique selon le type réel de la liste... Avec une LinkedList par exemple l'Iterator est nettement plus performant (et d'un ordre bien plus important encore) !


Donc cela dépend de l'implémentation de la liste, et comme l'as dit professeur shadoko, l'interface RandomAccessList permet d'identifier la meilleure méthode à utiliser...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
if (list instanceof RandomAccessList) {
	/* L'accès via get() dans un for() est potentiellement plus performant */
} else {
	/* L'accès via Iterator est plus performant */
}

a++