Nous analysons dans cette étude les performances des différents type de structure en JAVA. Pour ce faire, nous allons tester les structures à travers plusieurs opérations, et comparer leur temp d'execution et leur alocation mémoire. Nous allons tester les trois structures suivantes :
- "ArrayList"
- "HashMap"
- "Array"
Nous allons confronter ces structures à travers 5 opérations :
- "contains"
- "remove"
- "getFirst"
- "getRandom"
- "getLast"
Nous analysons dans cette étude les performances des différents type de structure en JAVA. Pour ce faire, nous allons tester les structures à travers plusieurs opération, et comparer leur temp d'execution et leur alocation mémoire.
Nous allons tester les trois structures suivantes : "ArrayList", "HashMap" et "Array".
Nous allons confronter ces structures à travers 5 opérations : "contains", "remove", "getFirst", "getRandom" et "getLast".
L'objectif de cette étude est d'aider à la décision lorsqu'il s'agira de choisir une structure de données.
Quelle est la structure la plus performante dans tel ou tel contexte ?
Usage : java testList structure operation taille
structure : Type de la structure, peut prendre les valeurs suivantes
ArrayList
HashMap
Array
operation : Type d'opération testé sur la structure, peut prendre les valeurs suivantes :
contains : Teste si une valeur apparait dans la structure. La valeur est définie aléatoirement.
remove : Supprime toutes les occurences d'une certaine valeur dans la structure. La valeur est définie aléatoirement.
getFirst : Accède au premier élément de la structure.
getRandom : Accède a l'élément d'index n de la structure. n est définit aléatoirement.
getLast : Accède au dernier élément de la structure.
taille : Taille de la structure.
Description de la plateforme de test :
cpu family : 6
model name : Intel(R) Atom(TM) x5-Z8350 CPU @ 1.44GHz
cpu MHz : 1441.000
cache size : 1024 KB
cpu cores : 4
Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres :
javac *.java
test() {
res=`(/usr/bin/time -f"%U\t%M" java testList $1 $2 $3> /dev/null) 2>&1`
echo -e "$1\t$2\t$3\t$res"
echo -e "$1\t$2\t$3\t$res" >> ../graphs/results
}
rm ../graphs/results
touch ../graphs/results
randomMax=10000
echo -e "struct\toperation\tsize\ttmp\tmem" >> ../graphs/results
for taille in 10 200 400 800 1000 2000 4000 8000 20000 40000 80000 200000
do
for struct in ArrayList Array HashMap
do
for operation in getFirst getRandom getLast remove contains
do
for itest in `seq 1 10`
do
test $struct $operation $taille
done
done
done
done
Pour produire les données, il suffit de lancer le script.
Celui çi va lancer le programme "testList" pour chaque type de structure, pour chaque opération et pour différentes tailles, allant de 10 éléments, à 180 000 éléments.
Il va enregistrer le temps d'execution et l'allocation mesurés dans le fichier nommé "result" du dossier "graphs". Il va faire ces opérations 10 fois, afin de pouvoir faire une moyenne. On va devoir lancer le script R à la main pour générer les graphiques.
| Opération | Résultats |
|---|---|
| contains |  |
| getFirst |  |
| getRandom |  |
| getLast |  |
| remove |  |
| Opération | Résultats |
|---|---|
| contains |  |
| getFirst |  |
| getRandom |  |
| getLast |  |
| remove |  |
En observant les résulats on constate des différences de performances d'une structure à l'autre.
Du point de vue du temps processeur, la structure HashMap consomme beaucoup plus de temps processeur que les autres. On retrouve ceci sur toutes les opérations. ArrayList est souvent plus lente que la structure Array, mais de peu. L'écart semble s'amplifier à mesure que le nombre d'éléments augmente. Cet ecart est aussi beaucoup moins présent sur les opérations get.
D'un point de vue de l'espace mémoire aloué, la aussi la structure HashMap est très gourmande. De la même manière que le temps processeur, Array demande moins de mémoire qu'ArrayList, y compris pour les opérations get.
On constate que getFirst et getLast sont très similaire. En effet, les trois strucutres n'ont aucune difficulté à atteindre la fin de la liste rapidement. Elles n'ont pas besoin de parcourir l'ensemble de la liste avant d'arriver à la fin.
Ces résultats préalables sont facilement explicables. En effet, HashMap demande des opérations suplémentaire car elle prend en compte un couple clé/valeur, ce que ne font pas les structures Array et ArrayList.
Si Array prend moins de mémoire que ArrayList, c'est parceque ArrayList s'encombre de plusieurs informations pour stocker chaque case du tableau (la case suivante, la case précédente), alors qu'array ne stocke aucune de ces informations, il se contente de stocker ses données dans des cases mémoires contigue. C'est pourquoi il consomme moins de mémoire.
Nous pouvons voir dans nos résultats préalables que l'évolution de Array et ArrayList sont très similaire en temp processeur.
Notre hypothèse sera la suivante : Si l'on augmente le nombre d'éléments, on pourra observer un écart significatif de performances entre les structures Array et ArrayList?
Pour vériufier cela, nous allons modifier le script pour augmenter les tailles et tester uniquement ArrayList et Array sur l'opération getRandom. Nous n'utiliserons que l'opération getRandom car le get est une fonction présente nativement dans les deux structures, que nous n'avons pas eu à recoder dans notre étude.
#!/bin/bash
javac *.java
test() {
res=`(/usr/bin/time -f"%U\t%M" java testList $1 $2 $3> /dev/null) 2>&1`
echo -e "$1\t$2\t$3\t$res"
echo -e "$1\t$2\t$3\t$res" >> ../graphs/results2
}
rm ../graphs/results2
touch ../graphs/results2
randomMax=10000
echo -e "struct\toperation\tsize\ttmp\tmem" >> ../graphs/results2
for taille in 200000 400000 600000 800000 1000000 2000000 6000000 20000000
do
for struct in ArrayList Array
do
for operation in getRandom
do
for itest in `seq 1 5`
do
test $struct $operation $taille
done
done
done
done
Nous pouvons voir qu'en effet, ArrayList est sensiblement plus lente qu'Array, en terme de temps processeur quand la taille est très grande. De surcroit, comme on pouvait s'y attendre, elle prend beaucoup plus de mémoire que Array.
Au vu des résultats, on peut supposer que le temps processeur d'ArrayList à une croissance exponentielle, tandis que Array à une croissance linéaire. On peu donc en conclure que Array est mathématiquement plus performant que ArrayList.
En conclusions, nous pouvons valider l'hypothèse, la structure ArrayList est moins performante que Array sur les grandes structures. Cependant, elle permet l'implémentation de certaines méthodes que n'implémente pas Array.
Nous aurions pu aussi tester une autre hypothèse : A partir d'une certaine taille, la structure HashMap devient-elle plus rapide qu'ArrayList sur l'opération getRandom. (J'ai testé l'hypothèse : non)