Manipulation d'une arraylist

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.

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

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 ??

Salut,

Citation:

---

Envoyé par 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 ??

---

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:

---

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:

---

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:

---

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:

---

1 2 3 4 5

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

---

a++

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 )

Citation:

---

Envoyé par 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.

---

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

a++

C'est pas tant la différence unitaire mais le ratio entre les deux que je trouve énorme:
Chez moi j'ai :
Avec for-each : 734 ms
Avec iterator : 719 ms
Avec index (get): 375 ms

C'est quasiment le double même si effectivement par itération ça ne fait pas une grosse différence, sur un programme qui parcoure pas mal de listes on peut avoir une différence de performance non négligeable.

Citation:

---

Envoyé par Kikito

sur un programme qui parcoure pas mal de listes on peut avoir une différence de performance non négligeable.

---

Dans ce cas on optimisera selon le cas en vérifiant si la collection implémente l'interface RandomAccess...

a++

Citation:

---

Envoyé par 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.

---

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... :mouarf: )
Ensuite tu récupéres tes compteurs...
Je pense que cette méthode écrase toutes les autres d'un point de vu performance 8-) non ?
Utile si l'on veut gagner 0.003 ms

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