README.md

P4a : analyse de performances

Problème

On s’intéresse ici à l’étude des performances d’opérations élémentaires sur des structures de données dont les éléments sont des entiers. L’analyse se porte sur des collections d’éléments de type tableaux, listes, piles et arbres. Les opérations élémentaires consistent à ajouter un élément, supprimer un élément, ainsi que rechercher le minimum. On souhaite analyser la complexité de ces algorithmes sur les différentes structures de données par des mesures de performances temporelles, ceci en faisant varier la taille des données à traiter. La visualisation des graphiques résultants nous permettra d’analyser le comportement de ces structures de données par type d’algorithmes, notamment identifier des tendances d'évolutions particulières lorsque la taille des données à traiter augmente. Ceci nous permettra, dans le cadre d'une application concrète, de pouvoir prendre des décisions pertinentes lors du choix d’une structure de données parmi d’autres, selon un ensemble d’actions à effectuer, le but étant de sélectionner la structure la plus rapide.

Dispositif expérimental

Application

L’implémentation des structures de données et des algorithmes se fait avec le language Java sous Windows. On utilise d’une part des structures fournies par la classe Collections : ArrayDequeue, LinkedList et Stack. D’autre part, on utilise des implémentations personnelles d’arbres binaires de type Binary Search Tree et de listes chaînées, ici circulaires. Afin de généraliser les tests, on utilise une classe de base de type interface contenant les trois méthodes communes à analyser : add(), remove() et minimum(). On crée ensuite des classes wrappers encapsulant les classes de base Java. De même, nos deux classes personnelles BinaryTreeSearch et liste chaînée circulaire héritent de l’interface commune. Le diagramme UML ci-dessous illustre les classes Java de notre application.

code source de l'application

A partir des classes Java précentes, nous avons développé une application de mesures de performances appliquant chacun de nos opérations élémentaires (add(), remove(), minimum()) sur chacune des structures de données précédentes (tableaux, listes, piles et arbres). Les résultats sont exportés dans un fichier de données de type ".csv".

Description de l'application et des arguments

Environnement de test

Description de la plateforme de test

Extrait pertinent de /proc/cpuinfo

L'application a été lancé sur un ordinateur portable MSI G5 avec 6 coeurs hyperthreadés de type Intel i7 à 2.2 GHz avec 32 Go de RAM. Ci-dessous, un extrait de l'export de la commande sur le WSL (Windows Subsystem for Linux) de Windows 11 :

model name : Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz cpu MHz : 2208.007 cache size : 9216 KB siblings : 12 cpu cores : 6 fpu : yes

Description de la démarche systématique

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

Suite des commandes, ou script, à exécuter pour produire les données.

Résultats préalables

Temps d'exécution