Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
ArrayList et capacité initiale
Bonjour,
je me pose une question sur la meilleure stratégie à adopter pour l'initialisation de la capacité d'une ArrayList.
Par exemple si je sais que ma liste va contenir de 0 à 300 éléments, mais que ce nombre d'éléments est très variable selon les situations, est-ce que je dois plutot initialiser mon ArrayList à 300 ou dois-je choisir un plus petit nombre ?
Bonjour,
Pourquoi l'initialiser à une taille ? Tu n'es pas obligé et tu peux laisser java se charger de mettre à jour la taille directement (en général il fonctionne par "tranche" de 10).
Lorsque la taille de l'ArrayList devient insuffisante, la taille initiale est agrandie de 50%.
A toi de voir selon ton application.
Si la liste est extrêmement sollicitée, autant déclarer la taille max dès le début. Par contre, si la gestion de la mémoire est critique et que les objets dans la liste sont gigantesques, il faut une gestion plus fine de l'espace alloué pour le tableau et pourquoi pas créer son propre ArrayList.
Mais dans la plupart des cas, il est inutile de s'occuper de ce genre de détails. Les problèmes de performances sont ailleurs, très souvent localisés entre la chaise et le clavier, un truc appelé "programmeur"
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Que la force de la puissance soit avec le courage de ta sagesse.
Si tu sais que ta List va contenir 300 éléments, il est préférable d'initialiser la taille directement à 300 pour éviter les réallocations de mémoire qui sont gourmandes.Pourquoi l'initialiser à une taille ? Tu n'es pas obligé et tu peux laisser java se charger de mettre à jour la taille directement (en général il fonctionne par "tranche" de 10).
Le problème est que parfois le nombre d'éléments d'une liste peut-être très variable, d'où ma question...
Personnellement, je n'initialiserais pas la taille. C'est le genre de paramètre qui ne sert qu'à de l'optimisation. Si tu veux optimiser, fais des tests comparatifs, en situation proche de la production, et tu pourras ainsi apporter la réponse à ta question dans ton propre contexte.
En matière de performances, il est toujours dangeureux de vouloir s'appuyer sur des principes généraux...
Nous sommes justement dans une phase d'optimisationC'est le genre de paramètre qui ne sert qu'à de l'optimisation.
Le mieux est surement de défnir la taille pour les listes dont on connait la taille et qui ne varient pas beaucoup. Pour le reste, c'est vrai qu'il faudrait des tests plus poussés, je vais donc laisser la valeur par défaut.
Merci pour vos réponses.
Globalement, tout à été dis.. mais je veux qd même confirmer:
Si tu ne crée ton ArrayList sans spécifier la taille; il créera un tableau d'une taille de 10; ensuite, à chaque fois que tu rajouteras un élément qui dépassera la taille disponible il recréera un tableau en calculant sa nouvelle capacité ainsi:
Il recopiera ensuite tous les éléments de l'ancien vers le nouveau tableau.
Code : Sélectionner tout - Visualiser dans une fenêtre à part int newCapacity = (oldCapacity * 3)/2 ;
Donc, si tu y rajoutes bcp d'éléments, il perdra inutilement son temps en recopiage de données, donc vaut mieux que tu déclares, si tu sais, une capacité initiale (et pas forcement 300, ou qu'importe ta taille maximum)..
Pour 300 éléments je ne sais pas si cela fera une grande différence. par contre si tu en as plusieurs (centaines) d'arrayList ainsi, ca deviendrait plus intéressant.. (faudra alors choisir entre la mémoire et la performance..)
Voilà... maintenant (bien que je suis assez sur de moi), je peux tjs me tromper
L'ArrayList va devoir faire 8 agrandissements successifs pour arriver à une taille de 300. Ensuite, si rien n'est fait, l'ArrayList conservera sa taille même s'il est vidé. Il faut donc utiliser "trimToSize" si la notion d'utilisation mémoire est critique, tout en sachant que le prochain ajout demandera un nouvel agrandissement.Envoyé par nabodix
Ce qu'il faut faire est donc ultra-spécifique à l'application : il faut bencher les différentes méthodes possibles.
N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
Que la force de la puissance soit avec le courage de ta sagesse.
et un petit millier d'opérations de recopiage..
(je m'excuse pour cette remarque complètement superflue/inutile)
Et surtout fausse !!!et un petit millier d'opérations de recopiage..
(je m'excuse pour cette remarque complètement superflue/inutile
Les opérations de récopiages n'ont lieu qu'en deux occasions :
- Lors d'une opération d'agrandissement de la capacité (donc 8 recopiages).
- Lors de la suppression d'un élément autre que le dernier (les éléments suivant doivent être décalé d'une case).
Bref on est bien loin des milliers d'opérations...
a++
Je suis d'accord qu'il faudra que tu ne recopie que 8 fois ton tableau (en fait, c'est 9, mais c'est un détail). ([EDIT]: ce sera 9 qu'à partir du 301ième élément seulement.. sorry)
Mais quand tu recopie un tableau, il faut bien déplacer tout ses éléments, non? (bien qu'il utilise pour cela System.arrayCopy, qui est peut-etre optimisé..).
Ce qui fait qd même plus d'opérations ("élémentaires", évidement) que ca?
(et je n'ai pas fait le compte exacte vu le peu d'intérêt que suscite ce problème..)
Il déplace le bloc en entier
waw; j'ai creusé System.arrayCopy; fais qqch petits tests, et c'est vrai que c'est vraiment performant (et le mot est faible); je n'aurais jamais cru.. A présent, je ne copirai mes tableaux qu'ainsi
Cependant, je n'ai pas trouvé le code natif de System.arraycopy, tu sais où je peux le trouver? sinon tampis..
merci
Il y a fort à parier que le code natif soit dans une dll / binaire quelconque de ton os, et que ce code soit soit propriétaire (microsoft) ou/et spécifique à chaque os
mais franchementm ça t'arrive souvent de devoir copier un tableau dans un autre manuellement? avec les collections java ça ne donne en tout cas pas envie de manipuler des tableaux....
Sans doutes..., mais c'est le code source que je voulais lire moi
Naaan, sérieux? il hante déjà mes cauchemars, il n'est pas aussi dans le code que j'utilise quotidiennement?! Jpense d'ailleurs ne pas avoir de code propriétaire sur ma machine (même flash..). Mais c'est vrai que pour java, je suis pas sûr, jpense qu'une bonne partie est sous licence Apache, mais est-ce l'entièreté?
Surement, non? ==> comme le reste de la JVM..
Pas si souvent, c'est sur, mais quand même..
Je ne sais plus trop pour quelle occasion mais je me rappel avoir utilisé plusieurs fois une boucle for (maintenant j'ai honte) pour copier un tableau.
(Jpense que c'était pour cloner un objet sans utiliser clone(), mais avec un constructeur..)
Oui, ca, c'est clair..
Surtout que tout cela m'a réconcilié avec les ArrayList (que j'évitais autant que possible)..
cordialement,
Xa
PS:je crois qu'on c'est écarté du sujet initial... mais bon..
Le code source du code natif n'est pas fourni avec le JDK... mais on doit pouvoir le retrouver dans le projet OpenJDK...Sans doutes..., mais c'est le code source que je voulais lire moi
Mais il y a de forte chance que cela soit basé sur un memcpy. Après tout un tableau d'objet n'est rien d'autre qu'un tableau de référence (et donc équivalent à un tableau d'int).
Le JRE/JDK est sous licence GPLv2 avec le classpath exception (afin de ne pas impacter sur la licence de toutes les applications Java), mais partiellement pour le moment car il reste des code propriétaire n'appartenant pas à Sun.
Le projet OpenJDK a justement pour objectif de corriger cela, et Java 7 devrait être la première version sans code propriétaire.
Une ArrayList est quand même préférable à un tableau. Aussi rapide (puisque basé sur un tableau) et beaucoup plus sûr.
a++
Répondre avec citation
Partager