P4a : Analyse de performances de différentes structures

Grille d'évaluation P4a

Problème

Notre but est de réaliser des tests de performance sur le temps d'éxecution et la mémoire utilisée selon la structure de données, la fonction testée, le nombre d’essais réalisés, et l'ordre de grandeur des éléments. Il y a également deux options supplémentaires : une pour réaliser ou non un affichage, et l'autre pour donner l'ordre de grandeur des éléments du tableau.

Paramètres :

• Le nombre d'essais (est attendu supérieur à 0)
• La fonction
• la structure
• l'option de l'ordre de grandeur

Dispositif expérimental

Application

code source de l'application J'ai choisi de tester les classes ArrayList et LinkedList grâce à des fichiers en bash ainsi qu'à des classes de tests en Java. Pour ce faire, j'ai réalisé une classe abstraite Structure comprenant les méthodes abstraites ajout en tête, en queue, suppression en tête, en queue, et recherche d'un nombre aléatoire parmi la structure. Les méthodes de cette classe abstraite sont implémentées dans les classes de tests SArrayList et SLinkedList. Enfin, une classe Main réalise les tests sur ces structures grâce aux paramètres qui lui sont fournis.

Paramètres :
- Le nombre d'essais (est attendu supérieur à 0)
- La fonction 
- la structure
- l'option d'affichage
- l'option de l'ordre de grandeur

Le nombre d'essais doit être supérieur à 0.

Les fonctions :
1. Ajouter n éléments en tête
2. Ajouter n élément en queue
3. Supprimer n éléments en tête
4. Supprimer n éléments en queue
5. Rechercher un élément dans une structure de donnée de taille n

Les structures de données :
1. ArrayList
2. LinkedList

L'option d'affichage :
1. Affiché
2. Ou autre que 1 : ne s'affiche pas.

Je me suis rendue compte par la suite que l'affichage n'était utile que pour vérifié la validitée du code en début de développement, je ne l'ai donc plus utilisé par la suite sans pour autant le supprimer au cas ou j'aurais besoin de tester une nouvelle structure de donnée.

L'option de définition de l'ordre de grandeur des éléments contenus dans la structure doit être supérieur à 1, 
sinon l'application retourne à son ordre de grandeur par défault :1000.

Environnement de test

J'ai testé les classes ArrayList et LinkedList grâce à des fichiers en bash ainsi qu'à des classes de tests en Java. J'ai donc l'arborescence suivante:

Projet
-> p4a (dossier)
-> perf2.sh
-> perf3.sh
-> data.dat

p4a
-> Main.java
-> Structure.java
-> SArrayList.java
-> SLinkedList.java

Description de la démarche systématique

Pour réaliser les tests et enregistrer les données ainsi que les graphiques, il suffit de tapper les lignes suivantes dans un terminal:

./perf3.sh | tee data.dat
./plot.sh

Cependant, je ne vous cache pas que la première commande a mis plus d'une heure à s'éxecuter. Sans même avoir réaliser de plot, on peut voir les lignes suivantes dans data.dat :

7500	5	1	10		0.63	47340
7500	5	1	100		0.69	43520
7500	5	1	1000		0.69	43428
7500	5	1	10000		0.68	45176
7500	5	1	100000		0.66	45132
7500	5	2	10		365.76	47332
7500	5	2	100		369.40	43800
7500	5	2	1000		371.40	47628
7500	5	2	10000		378.26	47688
7500	5	2	100000		370.94	44352

Ici, 7500 correspond aux nombres de recherches, 5 (deuxième colonne) correspond à la fonction de recherche dans une structure. Dans la 3 ème colonne , le 1 correspond a la structure de l'ArrayList et le 2 à la LinkedList. Les 10,100,...100000 (4ème colonne)correspond à l'ordre de grandeur de chaque élément de la structure. Enfin, les deux dernières colonnes sont le temps utilisateur et la mémoire. Ce que l'on remarque ici, est la différence monumentale de temps nécessaire entre les 5 premières et les 5 dernières lignes. On voit tout de suite que pour de la structure LinkedList est beaucoup moins efficace.

Résultats préalables

Temps d'exécution

Consommation mémoire

Analyse des résultats préalables

Discussion des résultats préalables

Explications précises et succinctes sur ce que les limites des résultats préalables et ce qu'ils ne permettent pas de vérifier.

Etude approfondie

Hypothèse

Expression précise et succincte d'une hypothèse. Mon hypothèse :

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

Pour refaire le jeu de test dans un fichier data.dat, enregistrer le dossier p4a et les fichiers perf2.sh et perf3.sh. Ouvrez un terminal à l'emplacement des fichiers, et écrivez la commande suivante:

./perf3.sh | tee data.dat

Pour réaliser les graphiques en fonction de data.dat obtenu précédemment, il faudra enregistrer le fichier plot.sh au même endroit que data.dat. Dans un terminal, il suffira d'écrire la commande ./plot.sh. Enfin, vous obtiendrez les graphiques correspondants.

Résultats expérimentaux

Analyse des résultats expérimentaux

Discussion des résultats expérimentaux

Conclusion et travaux futurs