P4a : Analyse de performances de différentes structures
Problème
Langage utilisé
Nous avons choisi d'utiliser le langage Java car il est plus adapté à notre organisation.
Description du problème
Analyse de performance de quatre structures identiques contenant des nombres mais fonctionnant différemment.
Nous aurons plusieurs paramètres au démarrage :
- Nombre de valeurs dans chaque tableau : chaque structure a une taille fixe de un million d'éléments générés aléatoirement.
- Nombre d'opérations : à chaque test, on augmente le nombre d'opérations de 100. Le nombre d'opérations varie de 100 à 5000.
- Type de l'opération : AddTete, AddQueue, RemoveTete, RemoveMiddle ou Get.
- Type de structure : nous utilisons des structures déjà existante (ArrayList, LinkedList, Table) et que nous avons créées nous-même (ChainedList composée de Link et d'un Cursor).
Contrainte : il faut de l’abstraction, et au moins un tableau ET une liste chaînée (Maillons)
Description des paramètres exploratoires du problème
- Analyser la différence de temps d'éxécution CPU et de consommation de mémoire sur des opérations simples dans chaque structure (insérer, supprimer, sélectionner).
Organisation du projet
Dispositif expérimental
Organisation objet
Description de l'organisation des classes et interfaces
Nous avons utilisé trois packages différents :
- Un pour les structures déjà existantes, StandardStructure : ArrayList, LinkedList et Table.
- Un pour celle que nous avons créée, PersonalStructure : ChainedList et ses composants, Link et Cursor.
- Un pour ce qui est commun aux deux packages précédents, defaultpackage : Main et Structure.
Pour les structures déjà existantes, nous avons préféré recréer une classe wrapper pour chacune d'entre elles afin de personnaliser les fonctions que nous voulions tester et adapter leur fonctionnement à chaque structure.
Diagramme de classes
Application
Description de l'application et des arguments
Pour utiliser notre application, il faut lui passer plusieurs paramètres dans l'ordre suivant : le type de structure que l'on souhaite évaluer, le nombre de valeurs (un million), la méthode que l'on va évaluer et le nombre d'opérations.
Le Main va ensuite créer une structure en fonction des paramètres qu'on lui a passé et la remplir de nombres aléatoires. Il va ensuite appeler la fonction choisie en utilisant un switch.
Environnement de test
Description de la plateforme de test
Description de la démarche systématique
-
Taille : taille de la structure, fixe à 100 000 éléments
-
nbOperation : nombre d'itérations pour chaque opération -> effectuer une observation à plus ou moins grande échelle, va de 50 à 250 avec un pas de 50
-
operation : String de l'opération courant (Add, remove, etc) il y en a 8 afin de pouvoir faire une observation d'ensemble sur toute les opération d'un coup
-
type : String de la structure courante. Il y a 4 structures (tableau, arraylist, linkedlist et maillon) afin de pouvoir faire une observation sur chacune d'entres elles
-
Les observation sont : le temps CPU sur x nombre d'opération et la consommation mémoire.
library(ggplot2)
perf <- read.csv2("perf.csv", sep="\t", dec=".")
GraphCPU <- ggplot(perf,aes(y = CPU, x = nbOperation, colour = Structure, shape =Structure)) + geom_point() + geom_smooth() + ggtitle("Evaluation du temps d'éxecution du CPU") + labs(y="Temps en secondes", x="Nombre d'opérations") + facet_grid(.~Operation)
GraphMemoire <- ggplot(perf,aes(y = Mem, x = nbOperation, colour = Structure, shape =Structure)) + geom_point() + geom_smooth() + ggtitle("Evaluation de la consommation mémoire") + labs(y="Temps en secondes", x="Nombre d'opérations") + facet_grid(.~Operation)
GraphCPU + coord_cartesian(ylim = c(0, 1))
Résultats préalables
Temps d'exécution
Dézoomé
Zoomé
Consommation mémoire
Analyse des résultats préalables
On constate que la mémoire agis différemment uniquement en fontion des structures et non pas des opérations sur celles-ci. De plus, la linkedList prend le plus de mémoire. ArrayList est la structure qui prend le moins de consommation mémoire, ce qui est logique car implémentée de base par java et rapide dans le temps CPU.
Le temps CPU varie grandement entre les structures. Bien sur, nous constatons des tendances comme par exemple ArrayList et Tableau qui sont souvent joints et LinkedList et Maillon qui sont aussi joints. C'est donc cohérent par rapport au mécanisme de la structure car on vois bien que sur les méthodes comme add (tete, queue, random) où l'ont constatent que le temps CPU est le même partout, ou presque pour linked et Maillon qui prennent plus ou moins de temps sur la méthode Get, ce qui est logique car ce sont des listes chainées (le déplacement prend du temps).
Cependant, sur les méthodes removes (tête, middle) on constatent un temps CPU énorme sur tableau. Ce qui est logique. Lorsqu'une valeur de tableau est retirée, il faut que tout ses éléments soient décalé vers la gauche, mais quand nous avons 1 millions d'élements ou même 100 000, cela prend du temps. Les résultats sont donc cohérents car removeMiddle prend deux à trois fois moins de temps que removeTete pour tableau. Mais à part linked et tableau, les tendances sont similaires pour les autres structures sur les autres méthodes.
Discussion des résultats préalables
Nos observation couvrent la totalité du problème, qui est ici d'analyser comment se comportent les différentes structures sur diverses opérations.
Etude approfondie
Hypothèse
Expression précise et succincte d'une hypothèse.
Protocole expérimental de vérification de l'hypothèse
Ainsi, le code nous renverra l’indice qui correspond à l’endroit où la valeur voulue se trouve dans le tableau et nous aurons un résultat correspondant à l'indice de la valeur trouvée dans chaque tableau
- Temps d'exécution des deux programmes (et leur différence)
- Types de recherche de chaque programme (une standard et une recherche dichotomique)
- Comment le “Random” influe sur la performance des structures
- Comment améliorer la performance des deux structures
- Déterminer la classe de compléxité des structures
Suite des commandes, ou script, à exécuter pour produire les données.