P4a : Analyse de performances de différentes structures

Groupe: Hugo KELHETTER

Grille d'évaluation P4a

Problème

Description du Problème.

Le langage utilisé est java

Pour décider quelle structure de données utiliser lors d'un projet, il est nécessaire de connaitre et comparer les coût mémoire et cpu des différentes structures disponible ainsi que celles implémentée. L'efficacité des structures varient en fonction de leur utilisations, il faut donc les tester dans une large variété de cas. Les structures choisies sont :

• ArrayList
• LinkedList
• Tableau (classe maison)
• ListeBilatere (classe vue en P31)

Description de tous les paramètres exploratoires du problème

• ajout de données à une position aléatoire
• suppression de données à une position aléatoire
• parcourt de donnée à une position aléatoire

Dispositif expérimental

Organisation objet

Application

code source de l'application

L'application prend 3 paramètres.  
Le premier correspond à la structure à tester :
- 1 : TableauListe (wrapper de ArrayList)
- 2 : ListeChaine (wrapper de LinkedList)  
- 3 : Tableau (classe maison)
- 4 : ListeBilatere
Le deuxième est la méthode à tester :
- add1 : add()
- get1 : get()
- remove1 : remove()
Le troisième est le nombre de valeurs que les structures doivent contenir.

ADD :
Ajoute à une position donnée de la structure une nouvelle valeur le nombre de fois envoyer ne paramètre lors du lancement. La position donnée est obtenu en lisant le fichier main/scripts/ajout.txt

GET :
Récupere la valeur à une position donnée le nombre de fois envoyer en paramètre lors du lancement. La position donnée est obtenu en lisant le fichier main/scripts/position.txt

REMOVE :
Supprime la valeur à la position de la structure le nombre de fois envoyer ne paramètre lors du lancement

Si l'application prend les paramètres : 1 add1 1000
On ajoutera 1000 valeurs à des positions aléatoires dans une ArrayList
Si l'application prend les paramètres 1 remove1 1000
On remplira l'ArrayList avec 1000 valeur par la méthode de test de add, puis on lui supprime ses 1000 valeurs dans un ordre aléatoire.

Lancer le script main/script/lancement.sh effectue tous les testes y compris pour les sections suivantes.

Environnement de test

Description de la plateforme de test

vendor_id	: AuthenticAMD
cpu family	: 23
model		: 24
model name	: AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx
stepping	: 1
microcode	: 0x8108102
cpu MHz		: 2394.484
cache size	: 512 KB
physical id	: 0
siblings	: 8
cpu cores	: 4
apicid		: 0
initial apicid	: 0
fpu		: yes
fpu_exception	: yes
cpuid level	: 13
wp		: yes
bogomips	: 4192.19
TLB size	: 2560 4K pages
clflush size	: 64
cache_alignment	: 64
address sizes	: 43 bits physical, 48 bits virtual

Description de la démarche systématique

Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres.

Les paramètres expérimentaux sont
- Les nombres de valeurs à avoir dans la structure allant de 10000 à 80000 avec un pas de 5000
-La position à la quelle on travail dans les strucutes : aléatoire,tête ou queue

Résultats préalables

Temps d'exécution

Consommation mémoire

Analyse des résultats préalables

TEMPS : Les structures ListeBilatere et LinkedList semblent être très lente. Les structure ArrayList et Tableau d'un autre côté semblent très rapide.

RAM : La consommation mémoire semble être égale pour toutes les structures.

Discussion des résultats préalables

Pour les trois tests, la manipulation de données se fait en lisant un fichier unique. Ce fichier a été créé dans le but de fournir des positions aléatoires mais unique pour chaque instance. On ne prend cependant pas en compte le comportement dans des cas précis :

• Toujours travailler sur la première position ou la dernière
• Alterner entre la première et la dernière position

On peut imaginer que les insertions et les suppressions soient beaucoup plus rapide si l'on ne travail que sur la dernière position par exemple.

Etude approfondie

Hypothèse

Les listes chainées ne semblent pas être efficaces pour la manipulation de données à des positions aléatoire. Ces structures sont peut être à privilégier pour la manipulation en queue ou en tête.

Protocole expérimental de vérification de l'hypothèse

Expression précise et succincte du protocole.

3 nouvelles fonctions de test ont été créées. Elles font la même chose que les fonctions précédente mais travaillent uniquement sur la position 0 au lieu de travailler en aléatoire. Les testes sont réalisé dans lancement.sh. Pour tester directement une fonction il suffit de changer le paramètre de fonction décrit plus haut :  
add2 : add()  
get2 : get()  
remove2 : remove()

Résultats expérimentaux

Temps d'exécution

Consommation mémoire

Analyse des résultats expérimentaux

Les consommations mémoires semblent similaire. Tableau plus lente même lorsqu'on travail à une position fixe. LinkedList et ListeBilatere sont plus rapide que ArrayList en travaillant en tête ou en queue à l'exception de remove en queue pour ListeBilatere.

Discussion des résultats expérimentaux

Tableau ne semble pas être une structure à utiliser. ArrayList semble être une structure polyvalente capable d'être utilisée dans tous les cas d'utilisations. Les listes chaînées semblent être à priviliégier quand l'on sait que l'on va travailler à une position fixe bien que ListeBilatere semble être une version moins efficace de LinkedList.

Conclusion et travaux futurs

ArrayList semble être la structure par défaut.
LinkedList est envisageable pour travailler à une position unique.
Tableau est bannie.