Skip to content
Snippets Groups Projects
FRANCOIS LUCAS's avatar
Lucas François authored
80664bb2
Forked from GOSSA JULIEN / P4a
51 commits ahead of the upstream repository.

P4a : Analyse de performances de différentes structures

Grille d'évaluation P4a

Problème

Une liste peut être implémentée de plusieurs façons qui vont faire varier le temps d'exécution et les performances du projet. Nous allons donc comparer les performances, la consommation de mémoire ou du CPU des structures de données déjà implémentées dans le langage Java avec des structures de données que nous allons implémenter. Les paramètres qui vont pouvoir modifier ces performances sont : -Type de structure -Type d’opérations -Taille de la structure -Nombre d’opérations effectuées

Dispositif expérimental

Organisation objet

image

Application

code source de l'application

Notre application exige des arguments pour être executé :

  • 1er argument : nom de la Structure = Array, ArrayList, LinkedList, Tableau, ListeChainee
  • 2e argument : nom de l'operation à tester : ajouter, getVal, retirer
  • 3e argument : taille de la liste testée

L'application va prendre le premier argument et créer la structure qui lui correspond. Elle va ensuite executer l'opération choisie(argument 2) avec en paramètre la taille(argument 3).

Voici ce que font les opérations que l'on utilise : X=taille

  • ajouter : ajoute à la table X numéros aléatoires allant de 0 à x
  • getVal : appeler ajouter puis retourner toutes les valeurs de la liste dans une variable
  • retirer : appeler ajouter puis supprimer toutes les valeurs de la liste

Environnement de test

Description de la plateforme de test

Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
Windows 10 Famille
Windows Subsystem for Linux

Description de la démarche systématique

Ce script va executer 500 tests pour chaque Structure et chaque Operation en précisant au .jar la taille de la Structure qui s'incrémente de 10000 par test. A chacun de ces tests le script va écrire dans le fichier resultats.CSV : le nom de la structure, sa taille, l'opération effectuée, le temps d'execution ainsi que la mémoire utilisée.

Les paramètres expérimentaux sont:

  • Structure qui est Array ou ArrayList ou Tableau ou LinkedList ou ListeChainee
  • Taille de la Structure variant de 10000 à 5000000 avec un pas de 10000
  • Operation qui est ajouter ou getVal ou retirer Pour chaque paramétrage, 1 mesures est effectuée.

X=taille

  • ajouter : ajoute à la table X numéros aléatoires allant de 0 à x
  • getVal : appeler ajouter puis retourner toutes les valeurs de la liste dans une variable
  • retirer : appeler ajouter puis supprimer toutes les valeurs de la liste

Les observations sont :

  • le temps d'execution en secondes
  • le volume de mémoire utilisé en octets
./generateValues.sh

Résultats préalables

Temps d'exécution

plot

plot

Consommation mémoire

plot

Analyse des résultats préalables

Parmis ces 5 structures on peut constater que les structures Array et Tableau sont les plus efficaces. En effet, pour celles-ci l'évolution du temps d'execution par rapport à la taille de la liste est assez légère.

On remarque cependant 3 résultats surprenants : Pour la fonction retirer dans la structure ArrayList : plus la taille de la liste augmente, plus le temps d'execution augmente de façon démesurée. Pour la fonction getVal dans les structures LinkedList et ListeChainee : plus la taille de la liste augmente, plus le temps d'exection de façon gigantesque.

Pour ce qui est de la mémoire rien de surprenant, l'évolution de la consomation de mémoire semble globalement être proportionnelle à la taille de la liste.

Discussion des résultats préalables

Nos résultats sont moyennement suffisants car il est difficile de distinguer les grandes variations tout en ayant pas d'autres courbe presque inanalysable. Si on veut voir entièrement la courbe de l'operation retirer pour la structure ArrayList il faut dézoomer énormément et alors on ne voit pas les variations des autres courbes.

Au premier abord, on pourrait croire que Array et Tableau sont les plus efficaces mais ce n'est qu'une façade. En effet, dans notre code, ces structures ne suppriment pas vraiment les valeurs lorsqu'on utilise l'operation retirer. En réalité elle les remplace seulement par une valeur null. On peut alors se demander comment réellement retirer un element de ces structures et quel impact que cela aura sur le temps d'execution et la mémoire consommée.

Ces résultats ne nous permettent donc pas réellement de savoir quelle est la Structure la plus efficace dans la globalité.

Etude approfondie

Hypothèse

Un Tableau est différent d'une ArrayList car contrairement à celle-ci quand on lui supprimme une valeur, sa taille ne change pas (la case est seulement null). On peut cependant trouver une façon d'arriver à retirer une valeur et de faire en sorte que la taille de ce talbeau se décremente. Pour cela on peut réassigner ce tableau à une copie de lui-même qui à la même taille-1 et sans cette valeur.

Cependant, logiquement cette méthode risque d'être beaucoup plus couteuse au niveau des ressources utilisées et du temps d'execution. Cela peut nous permettre de savoir quelle structure est réellement la plus efficace et la moins couteuse pour retirer une valeur. Car en effet nous avons souvent besoin de retirer des valeurs d'une liste.

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

Ce script va executer 26 tests pour chaque Structure et chaque Operation en précisant au .jar la taille de la Structure qui s'incrémente de 10000 par test. A chacun de ces tests le script va écrire dans le fichier resultats.CSV : le nom de la structure, sa taille, l'opération effectuée, le temps d'execution ainsi que la mémoire utilisée.

Les paramètres expérimentaux sont:

  • Structure qui est Array ou ArrayList ou Tableau ou LinkedList ou ListeChainee
  • Taille de la Structure variant de 10000 à 5000000 avec un pas de 10000
  • Operation qui est ajouter ou getVal ou retirer Pour chaque paramétrage, 1 mesures est effectuée.

X=taille

  • ajouter : ajoute à la table X numéros aléatoires allant de 0 à x
  • getVal : appeler ajouter puis retourner toutes les valeurs de la liste dans une variable
  • retirer : appeler ajouter puis supprimer toutes les valeurs de la liste

Les observations sont :

  • le temps de d'execution en seconde
  • le volume de mémoire utilisé en octet
./valuesForHypothese.sh

Résultats expérimentaux

Temps d'exécution

plot

Consommation mémoire

plot

Analyse des résultats expérimentaux

Notre ListeChainee semble avoir des performances assez similaires à celles de la LinkedList de java.

Parmis ces résultats on remarque que le temps d'execution augmente fortement par rapport au nombre d'opération effectuées pour les structures Array et Tableau.

Discussion des résultats expérimentaux

Nos résultats nous permettent d'appuyer notre hypothèse cependant faire seulement 26 tests n'est pas suffisant pour l'affirmer à 100%. Il faudrait que l'on fasse énormément plus de test, cependant cela prendrait beaucoup plus de temps (de façon exponentielle).

Notre hypothèse semble alors correcte, en effet on remarque bien que la courbe d'évolution du temps d'execution augmente proportionellement au nombre de fois qu'est executé retirer pour les structures Tableau et Array. Cela signifie en effet que Tableau et Array ne sont pas les meilleures structures à utiliser pour retirer des valeurs.

Cependant il reste alors difficile de déterminer quelle Structure est la plus efficace et économique. En effet chaque Structure à ses points forts et ses points faibles, il est ainsi difficile de trancher.

Conclusion et travaux futurs

Il en convient alors que chaque structure à bien sa "spécialité". C'est à dire que par exemple LinkedList est la liste la plus performante pour retirer des valeurs d'une liste. On pourrait réaliser plus de tests sur d'autres opérations afin d'avoir plus de données à analyser. Pour ainsi réussir à décider quelle structure est la plus efficace dans la globalité.

Dans le futur, on peut se fixer sur un nouveau problème : les tableaux à 2 dimensions. Il serait intéressant d'étudier ce qui serait le plus efficace et le moins couteux niveau temps d'execution et mémoire consommée entre créer un tableau à 2 dimensions et une liste de liste.