Newer
Older
# P4a : Analyse de performances de différentes structures
[Grille d'évaluation P4a](https://docs.google.com/spreadsheets/d/1x72glVEQHPx56Wr8G0RNQgfQXGX6xCsjms_6b7J6si0/edit?usp=sharing
)
## Problème
Lorsque l'on développe en Java, on aura souvent besoin d'utiliser des collections d'objets, sans que l'on en connaisse précisément leur fonctionnement.
Chacune ayant des besoins différents, le temps d'exécution et la mémoire utilisée seront impactés par l'implémentation que l'on choisira.
On cherche donc ici à voir différentes configurations, comme par exemple:
- Quel type de collection est la plus rapide pour accéder à une donnée précise dans une collection d'objets de taille normale (~1.000 éléments) ?
- Si on se place dans une très grande collection (>100.000 éléments), quelle collection permet d'utiliser la mémoire au minimum ?
Il y a donc plusieurs paramètres qui pourront faire varier les mesures de temps d'exécution ou de mémoire en fonction du type d'opération:
- La taille de la collection
- Le nombre de répétition de l'opération choisie
[code source de l'application Java](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/code/main.java) <br>
[code source du script sh](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/code/script.sh) <br>
[code source du script R](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/code/plot.r)
java -cp . main <structType> <size> <operation> <opSize>
### Structures analysées
- [LinkedList](https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html) (listes chainées)
- [ArrayList](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html) (listes non chainées)
- [Set](https://docs.oracle.com/javase/7/docs/api/java/util/Set.html) (collection sans doublon de valeurs)
### Opérations analysées
- add (ajoute un nombre d'éléments x en fin de liste)
- contains (vérifie la présence de x éléments dans la liste)
- remove (retire x éléments au sein de la liste)
Tous les tests ont été effectués sur mon ordinateur _personnel_, dont un extrait du fichier /proc/cpuinfo est le suivant:
model name : Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
cpu MHz : 800.010
cache size : 12288 KB
cpu cores : 6
```
### Description de la démarche systématique
Description de la démarche systématique et de l'espace d'exploration pour chaque paramètres.
```
> ./code/script.sh | tee ./data/src/dataTree.tsv
> ./code/plot.r
_Le script plot.r lira par défaut le fichier **dataTree.tsv** présent à l'emplacement **data/src/dataTree.tsv**_
| Opération | Plot |
|----------------------|---------------------------|
| Add |  |
| Contains |  |
| Remove |  |
| Opération | Plot |
|----------------------|---------------------------|
| Add |  |
| Contains |  |
| Remove |  |
La première chose que l'on peut remarquer est que le temps d'exécution et l'utilisation de la mémoire varient énormément selon le type de structures.
En effet, **Set** est bien plus long à l'exécution que les autres qui sont très proches lors de l'appel à l'opération **add**.
En revanche les trois structures sont très différentes sur les opérations **contains** et **remove**:
- **Set** est très stable et extrêmement rapide
- **ArrayList** reste relativement rapide même lorsque le nombre d'opérations augmente
- **LinkedList** a une augmentation très proportionnelle et prend donc beaucoup de temps s'il y a beaucoup d'opérations
Pour ce qui est de l'utilisation de la mémoire, on remarque que **Set** en utilise toujours une quantité bien supérieure à **ArrayList** et **LinkedList** quel que soit le type et nombre d'opérations.
On peut également noter que **ArrayList** est moins gourmande en mémoire que **LinkedKist**.
Bien sur, ces résultats préalables ne peuvent pas démontrer efficacement la différence de temps et d'utilisation de mémoire.
Pour se faire, il faudrait faire les tests sur d'autres ordinateurs aux performances différents par exemple.
On a remarqué lors des résultats préalables que l'utilisation de la mémoire variait peu entre la **LinkedList** et l'**ArrayList**. <br>
On veut donc ici observer si cette différence va augmenter ou non avec le temps, quand on rajoute des données et qu'on agrandit la structure.
On rajoute dans le fichier [script.sh](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/code/script.sh) les lignes suivantes:
```sh
structSize[5]=200000
structSize[6]=500000
structSize[7]=1000000
operationSize[5]=200000
operationSize[6]=500000
operationSize[7]=1000000
On relance ensuite ce script pour remplacer le contenu du fichier [dataTree.tsv](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/data/src/dataTree.tsv)
et enfin relancer le fichier [plot.r](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/code/plot.r) pour générer les nouveaux graĥes.
### Résultats expérimentaux
### Analyse des résultats expérimentaux
### Discussion des résultats expérimentaux
## Conclusion et travaux futurs
On peut conclure de la manière suivante:
- **Set** sera une bonne solution si l'on souhaite effectuer quelque chose rapidement sans se soucier de la mémoire
- **LinkedList** est le choix à privilégier si l'on sait d'avance que la vitesse d'exécution va s'allonger, et que la mémoire a des limites
- **ArrayList** sera lui le meilleur compromis entre vitesse et utilisation de la mémoire
Bien qu'ayant des avantages, **Set** possède également des points faibles à connaitre:
- L'impossibilité de doublons dans la collection
- Il utilise la mémoire bien plus que les listes (ArrayList ou LinkedList)
- **Set** n'est rapide qu'en analyse, pas en ajout