Newer
Older
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.
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.
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".
L'application Java attend **deux arguments** :
- **taille** : taille des données à traiter
- **filename** : nom du fichier de données de mesures .csv à produire
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 **/proc/cpuinfo** 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
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.
1) Lancer/exécuter le script "execute.bat" dans un PowerShell.
Ce script se charge de compiler le programme, puis de lancer l'application, puis de générer les graphes avec le langage R (son exécutable de script Rscript.exe).
| Jeu de test | ICArrayDeque | ICLinkedList | ICStack | ICOwnLinkedList | ICBinaryTreeSearch |
|----------------------|---------------------------|---------------------------|---------------------------|------------------|--------------------|
| minimum |  |  |  |  |  |
| add |  |  |  |  |  |
| remove |  |  |  |  |  |
Explications précises et succinctes des résultats préalables.
Explicitation par un calcul de complexité certains résultats.
Explications précises et succinctes des limites des résultats
préalables et ce qu'ils ne permettent pas de vérifier. Quelles questions soulèvent ces résultats?