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.

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

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

J’ai décider d’utiliser les granularités suivantes :

• Nombre d’utilisations de la fonction : *1 *5 *10 *50 *100 *500 *1000 *5000 *7500 *(10000 était initialement prévu, mais j’ai arreter le déroulement de perf3 et supprimer les lignes nécessaires dans data.dat pour ne pas perdre plus de temps.)
• Ordre de grandeur des nombres utilisés dans les structures : *10 *100 *1000 *10000 *100000

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

Ensuite, nous obtenons les graphiques précisés dans ./plot.sh. Je n’ai pas souvent réaliser la première ligne de commande, étant donner qu’elle prennait beaucoup de temps à se réaliser. J’ai même revu à la baisse mon maximum d’opérations tant le temps était long. À la fin, j’était à plus de 860 secondes pour une ligne de calcul avec une structure de LinkedList sur des recherches d’entiers.

Résultats préalables

Temps d’écecution

Comme dit précédemment, il fallait compter plus d’une heure pour obtenir tous les résultats, quasiment 2 heures.

Consommation mémoire

Analyse des résultats préalables

Sans même avoir réalisé 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 d’un nombre aléatoire 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.

Discussion des résultats préalables

Ce que l'on remarque ici, est la différence monumentale de temps utilisateur 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 en terme de temps, même si la mémoire utilisée semble avoir à peine augmenter.

Etude approfondie

Notre hypothèse sera donc : la LinkedList est moins efficace que l’ArrayList.

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

Pour vérifier notre hypothèse, nous avons tout simplement formulé les graphes de temps et de mémoire en fonction de la structure et du nombre d’utilisations des fonctions préalablement définies.

Résultats expérimentaux

Voici un graph qui représente le temps utilisateur et la mémoire nécessaire à la réalisation des tests. Notre hypothèse est ici partiellement inexacte ; La LinkedList (en bleu clair) prend tout autant de ressourse en mémoire et en temps que l'ArrayList (en bleu foncé) lorsque le nombre d’utilisation d’une fonction reste sous un certain seuil. On voit que la granularité n’est pas assez fine sur mes graphiques. C’est pourquoi j’ai décider de modifier celle-ci dans le fichier perf3.sh et de relancer un jeu de donnée data2.dat. La nouvelle granularité du nombre d’utilisations d’une fonction est donc la suivante : *1 *5 *10 *50 *100 *500 *1000 *tous les 500 pas jusqu’a 8000. J’ai lancé ce dernier jeu de test trop tard, et il prendra donc fin après minuit.Donc, il restera partiel.

Analyse des résultats expérimentaux

Après cette expèrience, nous constatons que la Linked list est beaucoup moins efficace mais uniquement dans lorsqu’on lui demande une recherche d’un nombre aléatoire, et passé un certain seuil d’expèriences : en effet, ce n’est que sur cette fonction de recherche que la LinkedList est moins efficace dans nos tests.

La question se pose alors : le code que j’ai écrit est-il optimisé ?

public int rechercher(Object e){
        int trouve =-1;
        for (int i=0; i < ll.size(); i++){
            if(ll.get(i)==e){
                trouve=i;
            }
        }
        return trouve;
    }

Effectivement, en me relisant, je vois que nous sommes obligés de reparcourir toute la LinkedList, probablement pour ne pas trouver le nombre aléatoire. C’est donc un problème de complexité linéaire O(N). En supposant que l’on utilise un algorithme dichotomique sur une liste triée, le gain de temps serait-il significatif ? La recherche passerait en complexité logarithmique, mais il faudrait au préalable trier tout le tableau, donc parcourir la plupart de ses éléments, c’est pourquoi le gain de temps et de mémoire ne serait pas énorme.. Après vérification de mon fichier SlinkedList, j’ai pu constater qu’il n’y a pas de recherche pré-implémentée comme dans l’ArrayList avec la méthode contains(). Seulement, le fait est que je n’ai pas utilisé contains dans la méthode de recherche de la classe SArrayList :

    public int rechercher(Object e){
        int trouve =-1;
        for (int i=0; i < al.size(); i++){
            if(al.get(i)==e){
                trouve=i;
            }
        }
        return trouve;
    }

Comment expliquer cette différence de temps et de mémoire pour cette fonction qui comporte la même ossature pour SArrayList que pour SLinkedList ?