Performance List.Iterator vs Tableau

Version imprimable

Bonjour a toutes et a tous,

Je me pose actuellement une question existentielle sur les performances de mon programme.

Je ne suis moi même pas un débutant mais je pense que les bonnes pratiques s'acquièrent au plus tôt au mieux donc autant en faire profiter les débutants.

Voila 2 bouts de code qui font exactement la même chose: vérifier que toutes les pieces jointes sont presentes.

Version Tableau

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
        List lstPieces = client.getListPiecesJointes();
        List lstCat = client.getListCategoriesPiecesJointes();
 
        PieceJointe[] pieces = (PieceJointe[])lstPieces.toArray(new PieceJointe[lstPieces.size()]);
        CategoriePJ[] categories = (CategoriePJ[]) lstCat.toArray(new CategoriePJ[lstCat.size()]);
 
        boolean allPiecesFound = true;
        for (int i = 0; i < categories.length; i++) {
            boolean pieceFound = false;
            for (int j = 0; j < pieces.length; j++) {
                if (pieces[j].getCategoriePJ().getCode().equals(categories[i].getCode()))
                    pieceFound = true;
            }
            if (!pieceFound)
                allPiecesFound = false;
        }

Version Iterator

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
        List lstPieces = client.getListPiecesJointes();
        List lstCat = client.getListCategoriesPiecesJointes();
 
        for (Iterator<CategoriePJ> itCat = lstCat.iterator(); itCat.hasNext(); ) {
            CategoriePJ categorie = itCat.next();
            boolean pieceFound = false;
            for (Iterator<PieceJointe> itPiece = lstPieces.iterator(); itPiece.hasNext(); ) {
                PieceJointe piece = itPiece.next();
                if (piece.getCategoriePJ().getCode().equals(categorie.getCode()))
                    pieceFound = true;
            }
            if (!pieceFound)
                allPiecesFound = false;
        }

La question : quelle solution présente les meilleurs performances ?

Et puisque nous somme dans la section Débuter du forum Java... je souhaiterai que les réponses soit argumentées afin qu'on puisse comprendre pourquoi telle ou telle solution est la meilleur et ainsi se renseigner sur les mécanismes des List en Java.

Merci d'avance pour vos réponses.

Bonne journée a toutes et a tous.
Cordialement.
Scarz.

23/03/2009, 13h33
_skip

Une List est quelque chose d'abstrait.
Tu as différentes implémentations de List par exemple LinkedList, ArrayList et ils fonctionnent déjà passablement différemment.
23/03/2009, 13h37
adiGuba
Salut,

Citation:

Envoyé par Scarz

La question : quelle solution présente les meilleurs performances ?

Aucune idée : surtout que cela peut fortement dépendre du type exact de la liste...

En général l'Iterator représente le meilleur compromis ! De plus avec Java 5 et la boucle for étendu sa syntaxe est vraiment très propre.
Ceci :
Code:

1 2 for (Iterator<CategoriePJ> itCat = lstCat.iterator(); itCat.hasNext(); ) { CategoriePJ categorie = itCat.next();
Peut avantageusement être remplacé par ceci :

Code:

for (CategoriePJ categorie : lstCat) {

Si tu as des problèmes de performances il serait préférable d'en trouver la cause exact plutôt que de chercher des "optimisations" illisibles qui te feront gagner quelques ms de temps en temps...

a++
24/03/2009, 00h17
Alain Defrance
Sans compter que la syntaxe du for étendu s'applique également aux tableaux :
Code:

1 2 3 4 PieceJointe[] pieces = new PiecesJointes[10]; for(PieceJointes currentPieceJointe : pieces) { // pour chaques éléments du tableau }
Les performences diffèrent en fonction de l'implémentation du type conteneur (List, Map, Set).
L'ArrayList est très proche du tableau (comme le Vector moins utilisé de nos jours), car il utilise une Array en interne pour gérer les données, il est donc très éfficace pour récupérer les données par l'index.
La LinkedList est moins performente pour récupérer un index précis (qui est du à la nature même d'une liste chainé), mais meilleurs pour les parcours ...

De toute façon comme le dit adiGuba, ne problème de performence n'est pas ici, et il est souhaitable de privilegier la lisibilité plutot que le gains de quelques petites micro-secondes.

Pour compléter la réponse de Kazou, le vector est une version synchronisée de l'arraylist, pour cette raison il a moins sa place dans les applics ordinaires mais dans un environnement multithread faut pas s'en priver.

Une liste chainée est très performante lors de l'ajout d'élément puisque contrairement à l'arraylist, il n'y a pas besoin de supprimer le tableau en interne pour en réallouer un plus grand lorsque sa capacité devient trop faible.
par contre, accéder à un élément autre que le premier ou le dernier de la liste est moins rapide car la liste ne comporte pas d'index et doit être parcourue. Ainsi accéder à l'élément 49 d'une liste de cent nécessitera 49 sauts.

Sinon en général les tableaux sont plus performants que les listes pour les types primitifs à cause de l'autoboxing. Ainsi un int[] est plus rapide qu'un ArrayList<Integer> lorsqu'il s'agit de stocker des entiers pour des raisons évidentes.

Cependant je rejoins les 2 avis ci-dessus pour dire que les problèmes de performances se situent rarement à cet endroit.
Par exemple si on prend ton code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 PieceJointe[] pieces = (PieceJointe[])lstPieces.toArray(new PieceJointe[lstPieces.size()]); CategoriePJ[] categories = (CategoriePJ[]) lstCat.toArray(new CategoriePJ[lstCat.size()]); boolean allPiecesFound = true; for (int i = 0; i < categories.length; i++) { boolean pieceFound = false; for (int j = 0; j < pieces.length; j++) { if (pieces[j].getCategoriePJ().getCode().equals(categories[i].getCode())) pieceFound = true; } if (!pieceFound) allPiecesFound = false; }
On voit qu'il n'est pas optimal puisque les deux boucles provoquent m*n itération même si dès la première on constate qu'il manque la pièce. Ensuite on peut pousser plus loin en utilisant éventuellement une Hashmap avec le code catégorie PJ en clé et la pièce en valeur.

24/03/2009, 09h29
Alain Defrance

Bonjour,

Citation:

Envoyé par _skip

Une liste chainée est très performante lors de l'ajout d'élément puisque contrairement à l'arraylist, il n'y a pas besoin de supprimer le tableau en interne pour en réallouer un plus grand lorsque sa capacité devient trop faible.

Cette gestion du tableau est certes vrai mais dépend grandement de la capacity de l'arrayList (par défaut à 10), de plus si mes souvenirs sont bon, l'augmentation se fait par x2. C'est à dire que plus on augmente la capacitée, et plus celle-ci augmente rapidement. De ce fait ceci reprétente effectivement une charge, mais ça reste occasionel.

Citation:

Envoyé par _skip

Sinon en général les tableaux sont plus performants que les listes pour les types primitifs à cause de l'autoboxing. Ainsi un int[] est plus rapide qu'un ArrayList<Integer> lorsqu'il s'agit de stocker des entiers pour des raisons évidentes.

En quoi l'auto-boxing intervient dans la performence ? J'ai plutôt l'image des wrapper comme des types gourmand en ressource (et surtout en mémoire). Si mes souvenirs sont bons, boolean -> un bit, un Boolean (rien que la référence prend un octet), et a ceci il faut rajouter l'instance. C'est d'ailleurs pour ces raisons qu'il existe encore des types primitifs en Java. A ajouter à cela, l'utilisation des opérateurs sur des Wrapper implique une auto-unboxing puis un auto-boxing (ce qui est beaucoup plus lourd). Peut-tu expliciter ce que tu veux dire ?
24/03/2009, 10h08
_skip

Citation:

En quoi l'auto-boxing intervient dans la performence ? J'ai plutôt l'image des wrapper comme des types gourmand en ressource (et surtout en mémoire). Si mes souvenirs sont bons, boolean -> un bit, un Boolean (rien que la référence prend un octet), et a ceci il faut rajouter l'instance.

Juste réflexion mais sauf erreur c'est un peu plus compliqué que ça :
un boolean fera plutôt 1 byte, les références feront 4 octets, et le Boolean, compte tenu que les objets ont au minimum un header de 8 bytes + 1 byte valeur + la référence, et sont alignés sur 8 (jvm de sun) ça risque de faire autour des 20 bytes. (estimation).

Citation:

C'est d'ailleurs pour ces raisons qu'il existe encore des types primitifs en Java. A ajouter à cela, l'utilisation des opérateurs sur des Wrapper implique une auto-unboxing puis un auto-boxing (ce qui est beaucoup plus lourd). Peut-tu expliciter ce que tu veux dire ?

Plutôt simplement en fait, les collections en java sont conçues pour référencer des objects et non des types primitifs. L'ajout d'un entier à une collection nécessite donc sa conversion en object, ainsi également l'accès à cette valeur entière implique un unboxing.
En terme d'opérations, c'est beaucoup plus que l'affectation et la lecture de ce même int dans un int[].
24/03/2009, 10h21
Alain Defrance

Citation:

Envoyé par _skip

Plutôt simplement en fait, les collections en java sont conçues pour référencer des objects et non des types primitifs. L'ajout d'un entier à une collection nécessite donc sa conversion en object, ainsi également l'accès à cette valeur entière implique un unboxing.
En terme d'opérations, c'est beaucoup plus que l'affectation et la lecture de ce même int dans un int[].

Je crains que nous soyons d'accord l'un avec l'autre mais que nous ne sommes tout simplement pas compris au début :aie:

tu part d'un List et tu crée un tableau. Quelle que soit ta liste, ca veux dire que t'as une surcharge à cete endroit là et transfert de données vers le tableau. Si t'as une liste en paramètre, utilise l'iterator, si t'as un array en paramètre, utilise l'index, aussi simple :)

Par rapport à la linkedlist mentionnée, si tu passe par l'iterator t'as pas la perte de temps due au saut, puisque l'iterator part toujours du derneir élément utilisé:

(code de sun pour le listiterator de la linkedlist)
Code:

1 2 3 4 5 6 7 8 9 10 public E next() { checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; }
ce code est forcément un peut plus long qu'un accès par index, mais le gain est marginal.

24/03/2009, 14h09
Scarz

OK... bien bien.

Je vous remercie toutes et tous pour vos nombreuses réponses toutes plus constructives les unes que les autres.

Pour répondre à chacun dans les grandes lignes.
Je suis en train de développer des applications web professionnelles qui sont destinées à être lancées sur une même machine (une dizaine d'appli) donc potentiellement un trafic élevé donc quelques millisecondes fois 1000 visiteurs simultané = quelques secondes donc tout est bon à prendre.
Je ne rencontre aucun problème de perf actuellement mais mieux vaut prévenir que guerrir.

Pour répondre à la grande question omniprésente dans tout les posts... j'utilise une ArrayList.

Pour ce qui est du dev (perf des differents codes) je comprend mieux la logique à adopter lors des dev et je retiendrai le dernier post ainsi que la syntaxe étendue des boucles for.

Merci encore pour votre participation.
Bonne et agréable journée a toutes et tous.
Cordialement.
Scarz.
24/03/2009, 15h22
adiGuba

Citation:

Envoyé par Scarz

Je ne rencontre aucun problème de perf actuellement mais mieux vaut prévenir que guerrir.

Oui mais non...
:arrow: il vaut mieux prévenir ce genre de problème en utilisant des tests de montée en charge, plutôt que de perdre du temps à imaginer un potentiel problème de performance là ou il ne se trouve pas...

C'est comme cela qu'on se retrouve avec des codes super-complexes et usine-à-gaz pour pas grand chose, qui au final se révèlent moins performant que la version "non-optimisé" ! Un comble :aie:

Dans ton cas précis la transformation List->tableau peut être relativement couteuse, car elle donne plus de boulot au GC...

A l'inverse, si demain tu as un problème sur une partie bien précis de ton application, tu pourras plus facilement en détecter l'origine et la cause avec un code clair et propre...

a++
24/03/2009, 16h44
tchize_

c'est ce qu'on appelle de l'optimisation hative, a éviter à tout prix :)