Problème
Lors du développement d'une application en Java (ou dans un autre langage), nous utilisons très régulièrement des Collections pour stocker des données.
Cependant, chaque implémentation de cette interface réponds à certaines problématiques, et donc ce choix devient important lors de la phase d'optimisation de l'application.
Mon but fut alors de comparer le temps d'exécution et d'utilisation mémoire de différentes collections afin de voir laquelle est la plus performante.
Pour ce faire, j'ai testé 3 opérations différentes :
- L'insertion d'un élément
- La présence d'un élément
- La suppression d'un élément
Pour réaliser mes tests, j'ai choisi 3 classes implémentant l'interface ICollection qui sont :
ArrayListLinkedListHashSet
Afin d'observer les différences de temps d'exécution et d'utilisation mémoire, j'ai choisi de faire varier les paramètres suivants afin de pouvoir choisir laquelle répond le mieux à mon problème, et dans quels circonstances :
- Le nombre de tests par opération
- La taille de la structure
Dispositif expérimental
Application
Usage : java Main <structure> <longueur> <operation> <valeur associée à l'opération>structure :
LinkedList => LinkedList
HashSet => HashSet
Autres écritures => ArrayList
operation:
Présence => Contains
Suppression => Remove
Autres écritures => Add
valeur associée :
Présence => index à tester
Suppression => index à supprimerUsage : ./script.sh | tee ../data/perf.datUsage : ./graphique.R
(vérifier que le fichier data/perf.dat à été rempli à l'aide du script shell)Environnement de test
J'ai fais nos tests sur les serveurs dédiés aux élèves de l'IUT, voici le résumé des informations tirées de /proc/cpuinfo
model name : QEMU Virtual CPU version 0.13
cpu MHz : 2294.246
cache size : 512 KB
cpu cores : 1Description de la démarche systématique
Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres.
./script.sh | tee ../data/perf.dat
-> compile les fichiers .java nécéssaires à l'éxécution du Main
-> Execute la batterie de tests grâce aux fichiers java (compilé)
-> ./graphique.R : créé les deux graphiques souhaitésRésultats préalables
Temps d'exécution
Consommation mémoire
Analyse des résultats préalables
- On remarque ici une nette différence de temps lors de l'utilisation d'une Hashset dans n'importe quelle situation et pourtant, à travers l'étude de la mémoire utilisé on voit que la `Hashset` et plus gourmand, et donc répondras à une demande de rapidité et non de consommation minimale.
- De plus on voit aussi que l'`ArrayList` est un peu plus rapide que la `LinkedList` peut importe la situation, sans pour autant demander de la mémoire supplémentaire. Elle est donc à privilégier.Discussion des résultats préalables
Le HashSet est beaucoup plus rapide que les deux autres structures étudiées pour tous les tests car les valeurs qu'il contient sont triées. Cependant sur d'autres opération telles que l'insertion, sa construction lui sera fatale car elle doit réaliser un certain nombre de comparaisons afin de trouver à quelle position l'élément doit être inséré.
Cela va également augmenter drastiquement sa consommation mémoire, ce qui est probablement dû à la classification des données.
Quant à la LinkedList, elle réside sur un principe de liste chaînée et donc de maillons, c'est donc pour cela qu'elle devient rapidement gourmande par rapport aux autres structures notamment lorsqu'elle atteint une taille assez conséquente.
Enfin, l'ArrayList est une liste polyvalente alliant un temps d'éxecution faible, sans pour autant devenir gourmande en mémoire, ce qui explique qu'elle soit couramment utilisé, sans compter son principe de fonctionnement trivial.
Etude approfondie
Hypothèse
Expression précise et succincte d'une hypothèse.
Protocole expérimental de vérification de l'hypothèse
Expression précise et succincte du protocole.
Suite des commandes, ou script, à exécuter pour produire les données.