Skip to content
Snippets Groups Projects
README.md 6.29 KiB
Newer Older
gossa's avatar
gossa committed
# 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

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
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 ?
gossa's avatar
gossa committed

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
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
gossa's avatar
gossa committed

## Dispositif expérimental

### Application

[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)
gossa's avatar
gossa committed
```
java -cp . main <structType> <size> <operation> <opSize>
gossa's avatar
gossa committed
```

### 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)

gossa's avatar
gossa committed
### Environnement de test

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
Tous les tests ont été effectués sur mon ordinateur _personnel_, dont un extrait du fichier /proc/cpuinfo est le suivant:
gossa's avatar
gossa committed
```
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
model name	: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
cpu MHz		: 800.010
cache size	: 12288 KB
cpu cores	: 6
gossa's avatar
gossa committed
```

### Description de la démarche systématique

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

```
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
> ./code/script.sh | tee ./data/src/dataTree.tsv
> ./code/plot.r
gossa's avatar
gossa committed
```
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
_Le script plot.r lira par défaut le fichier **dataTree.tsv** présent à l'emplacement **data/src/dataTree.tsv**_
gossa's avatar
gossa committed

## Résultats préalables

gossa's avatar
gossa committed
### Temps d'exécution

| Opération            | Plot                      |
|----------------------|---------------------------|
| Add                  | ![plot](data/plots/v0_exectime_add.png) |
| Contains             | ![plot](data/plots/v0_exectime_contains.png) |
| Remove               | ![plot](data/plots/v0_exectime_remove.png) |
gossa's avatar
gossa committed
### Consommation mémoire

| Opération            | Plot                      |
|----------------------|---------------------------|
| Add                  | ![plot](data/plots/v0_memory_add.png) |
| Contains             | ![plot](data/plots/v0_memory_contains.png) |
| Remove               | ![plot](data/plots/v0_memory_remove.png) |
gossa's avatar
gossa committed

### Analyse des résultats préalables

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**.
gossa's avatar
gossa committed

### Discussion des résultats préalables

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
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.
gossa's avatar
gossa committed

## Etude approfondie

### Hypothèse

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
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>
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
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.
gossa's avatar
gossa committed

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

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
On rajoute dans le fichier [script.sh](https://git.unistra.fr/mcatelguihomat/P4a/-/blob/master/code/script.sh) les lignes suivantes:
```sh
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
structSize[5]=200000
structSize[6]=500000
structSize[7]=1000000

CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
operationSize[5]=200000
operationSize[6]=500000
operationSize[7]=1000000
gossa's avatar
gossa committed
```
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed
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.
gossa's avatar
gossa committed

### Résultats expérimentaux

### Analyse des résultats expérimentaux

### Discussion des résultats expérimentaux

## Conclusion et travaux futurs
CATEL-GUIHOMAT MARIN's avatar
CATEL-GUIHOMAT MARIN committed

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