Discussion :

[timbrochier]

Bonjour,
une question simple pour une réponse (j'espere) simple :

- J'ai une arraylist "Pop" contennant des objets "individu", individu est une classe et chaque individu a ses caractéristiques, par exemple vivant ou mort.

--> je veux savoir le nombre d'individu vivant dans la liste pop, avec la méthode la plus rapide possible.
j'ai déja pensé à faire une boucle avec un compteur, mais existe t'il une méthode plus rapide?

merci d'avance,
Timothée.

[herve91]

à part gérer deux listes, une contenant les individus vivants et l'autre les individus morts, il n'y a pas plus rapide que de faire une boucle.

[iohack]

Je ne connais pas le fonctionnement interne de l'ArrayList, mais le parcours à l'aide d'un Itérator ne serait pas plus rapide qu'une boucle faisant des "get" successifs ??

[adiGuba]

Salut,

Je ne connais pas le fonctionnement interne de l'ArrayList, mais le parcours à l'aide d'un Itérator ne serait pas plus rapide qu'une boucle faisant des "get" successifs ??

Non : les ArrayList utilise en interne un tableau, et l'accès via get() est ainsi très rapide. (l'Itérator d'ArrayList appelle en réalité la méthode get()).

Ce bout de code le montre très bien :

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
        List<String> list = new ArrayList<String>();
        long start, end;
        int MAX = 10000000;
 
        // On rempli la liste
        for (int i=0; i<MAX; i++) {
            list.add(" Hello World ");
        }
 
 
        // Parcours via la boucle for-each (utilise l'Iterator)
        start = System.currentTimeMillis();
        for (String s : list) {
            if ("".equals(s)) {
                System.out.println("Empty");
            }
        }
        end = System.currentTimeMillis();
        System.out.println("Avec for-each   : " + (end-start) + " ms");
 
        // Parcours via l'Iterator :
        start = System.currentTimeMillis();
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if ("".equals(s)) {
                System.out.println("Empty");
            }
        }
        end = System.currentTimeMillis();
        System.out.println("Avec iterator   : " + (end-start) + " ms");
 
 
 
 
 
        // Parcours via les index 
        start = System.currentTimeMillis();
        final int sz = list.size();
        for (int i=0; i<sz; i++) {
            String s = list.get(i);
            if ("".equals(s)) {
                System.out.println("Empty");
            }
        }
        end = System.currentTimeMillis();
        System.out.println("Avec index (get): " + (end-start) + " ms");

Ce qui donne chez moi :

Code :

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

1
2
3
Avec for-each   : 719 ms
Avec iterator   : 750 ms
Avec index (get): 484 ms

L'accès via index est donc un peu plus rapide...


Toutefois il faut toujours priviliégier l'accès via Iterator, qui garantit des performances corrects (même si elle ne sont pas forcément optimale). En effet selon l'implémentation de Collection qu'on utilise, l'accès via get() peut être très pénalisant, comme c'est le cas par exemple avec les LinkedList.

Lorsqu'on fait un accès avec get() sur une LinkedList, on parcours en réalité tous les éléments qui précède l'élément que l'on veut obtenir. Ainsi pour obtenir l'index 100 on parcours les 99 éléments le précédent... ce qui peut être très pénalisant avec des listes de tailles importantes.


Ainsi le code ci-dessus avec une LinkedList à la place de l'ArrayList donne les résultats suivant :

Code :

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

1
2
3
Avec for-each   : 641 ms
Avec iterator   : 594 ms
...

Mais après quelques minutes j'ai eu la flèmme d'attendre la fin du parcours via index...



Donc il faut toujours priviliégier l'Iterator...
Toutefois si on veut des performances optimales, on peut utiliser l'interface marqueur RandomAccess pour savoir si le parcours par index est plus rapide que par l'itérateur pour une collection :

Code :

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

1
2
3
4
5
if (list instanceof RandomAccess) {
    // Parcours par index via get()
} else {
    // Parcours via l'itérateur
}

a++

[Kikito]

Moi qui n'utilisait que des for/each sur les ArrayList depuis la 1.5 je suis déçu, je pensais pas qu'il y avait un tel écart de performance avec l'accès par get.

Ca doit être la vérification des ConcurrentModificationException qui doit prendre du temps mais là ça fait vraiment un écart conséquent ( en remplacant par des nanotime j'ai quasiment un écrat du simple au double chez moi )

[adiGuba]

Moi qui n'utilisait que des for/each sur les ArrayList depuis la 1.5 je suis déçu, je pensais pas qu'il y avait un tel écart de performance avec l'accès par get.

Heu... la différence est vraiment infine !
Chez moi j'ai environ 220 ms de différence pour 10000000 éléments, ce qui revient à une différence unitaire de 0,000022 ms...

Pa contre l'accès via get() peut être bien pire que ca sur une LinkedList (je n'avais pas arrêté mon test de tout à l'heure et il n'est toujours pas fini... je viens de le killer... )

a++

[tnodev]

Bonjour,
une question simple pour une réponse (j'espere) simple :

- J'ai une arraylist "Pop" contennant des objets "individu", individu est une classe et chaque individu a ses caractéristiques, par exemple vivant ou mort.

--> je veux savoir le nombre d'individu vivant dans la liste pop, avec la méthode la plus rapide possible.
j'ai déja pensé à faire une boucle avec un compteur, mais existe t'il une méthode plus rapide?

merci d'avance,
Timothée.

Salut
voic mon humble contribution...

Tu peux créer une IndividuList qui hérite de ArrayList contenant deux compteurs. Tu surcharges la méthode add, en ajoutant un test sur ton individu qui va incréménter le compteur adéquat (comme Sheila... )
Ensuite tu récupéres tes compteurs...
Je pense que cette méthode écrase toutes les autres d'un point de vu performance non ?
Utile si l'on veut gagner 0.003 ms

[timbrochier]

je connaissait pas les itérators, effectivement ça va beaucoup me servir je pense puisque je manipule des listes assez importantes, et j'ai des temps de calculs de l'ordre de quelques jours, alors grapiller des millisedonces a gauche a droite ça peut faire gagner des heures!

merci pour votre aide précieuse,

timothée