Newer
Older
[Grille d'évaluation P4z](https://docs.google.com/spreadsheets/d/1VXeO91rhy04xa0p8KUhWliFl228utHaDir8MstO5Z-M/edit?usp=sharing)
Notre problème ? Comment trier efficacement des tableaux !
Et par efficacement trier des tableaux, nous entendons les trier le plus rapidement possible, en consommant le moins de mémoire possible. Pour ceci nous allons partir de 4 algorithmes de tri différents et étudier leur temps d'exécution et leur consommation de mémoire en fonction du tableau à trier (tableau généré aléatoirement, déjà trié, trié dans le sens inverse, trié à moitié).
Pour utiliser les tris, vous avez besoin de 2 choses:<br>
- Le binaire `tri`<br>
- Un document texte contenant les éléments du tableau, chaque élément est séparé du prochain par un espace et pour finit par un `.`. <br>
Ex : `4 3 11 29 .`<br>
Le binaire demande une option et un fichier, le fichier est du type de ceux définit plus haut, quant aux option il en existe plusieures : <br>
- `-i` ou `--insertion` pour le tri à insertion
- `-f` ou `--fusion` pour le tri à fusion
- `-r` ou `--rapide` pour le tri rapide
- `-b` ou `--bulle` pour le tri à bulle
- `-ri` ou `--rapideInsertion` pour le tri rapide mélangé avec le tri insertion (développé dans l'hypothèse)
- `-a` ou `--all` pour tout les tris disponibles
- `-iv` ou `--insertion-verbose` pour le tri à insertion avec les affichages avancés
- `-fv` ou `--fusion-verbose` pour le tri à fusion avec les affichages avancés
- `-rv` ou `--rapide-verbose` pour le tri rapide avec les affichages avancés
- `-g` qui génére un nouveau tableau sur stdout avec une taille du tableau et un nombre max
- `-gt` qui génére un nouveau tableau trié sur stdout avec une taille du tableau et un nombre max
- `-gti` qui génére un nouveau tableau trié dans le sens inverse sur stdout avec une taille du tableau et un nombre max
- `-gtp` qui génére un nouveau tableau trié à moitié sur stdout avec une taille du tableau et un nombre max
Les tests se sont fait sur troglo en connexion à distance, le fichier obtenu avec cat /proc/cpuinfo est disponible ici : [cpuinfo](src/Scripts/cpuinfo.txt).
D'autres test (principalement pour les hypothèses) ont été effectués sur l'ordinateur personnel d'Antonin, (ce qui a déjà entrainé quelques soucis), le cpuinfo de l'ordinateur est disponible ici : [cpuinfo_antonin](src/Scripts/cpuinfo_antonin.txt).
```
model name : Intel(R) Xeon(R) CPU E5-2630L v3 @ 1.80GHz
cpu MHz : 1198.728
cache size : 20480 KB
```
```
model name : Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
stepping : 10
microcode : 0xca
cpu MHz : 1407.683
cache size : 12288 KB
```
On va tester le tri à bulle, le tri par insertion, le tri fusion et le tri rapide avec des tableaux générés aléatoirement de taille entre 0 et 100 000 et ayant des valeurs entre 0 et 100 000 pour observer leurs temps d'exécution et leur consommation mémoire.
Pour obtenir perf.dat contenant toutes les données (à exécuter dans [src/Scripts/](src/Scripts/)):
```
Ensuite, il faut lancer R et exécuter le script [src/R/perf.R](src/R/perf.R) :
<img src="src/Images/graphe_temps.png" width="500"/>
<img src="src/Images/graphe_memoire.png" width="500"/>
Grâce à ces deux graphes, nous pouvons constater qu'il y a principalement 3 types de tri :
- Les tris qui s'exécutent rapidement mais consomment beaucoup de mémoire, comme le tri fusion qui consommera toujours beaucoup de mémoire, que le tableau soit de base trié, trié dans le sens inverse ou aléatoire.
- Les tris qui consomment peu de mémoire mais s'exécutent plus lentement, comme le tri par insertion qui n'a aucun problème avec un tableau déjà trié, mais met plus de temps avec un tableau trié dans le sens inverse. Le tri à bulle lui, est aussi plus rapide avec un tableau trié mais reste lent.
- Les tris qui s'exécutent rapidement et consomment peu de mémoire, plus rare, comme le tri rapide qui cependant a beaucoup de mal avec un tableau déjà trié, voir trié dans le sens inverse.
Certains résulats ne permettent pas de déduire que, par exemple, le tri par insertion est plus rapide sur des tableaux à moitié rangé.
Le tri rapide s'il sélectionne comme pivot le premier éléments (ou le dernier) va se retrouver bloqué ou extrêmement lent, ces cas sont particuliers et on ne peux donc pas les déterminé simplement à la simple vue des graphiques.
Le tri par insertion devient de plus en plus long quand la taille du tableau augmente, et donc celui-ci ne sait traiter efficacement uniquement des petits tableaux, étant donné que tout les autres algorithmes coupent leurs tableaux en de plus petit tableaux. Notre hypothèse est, que si le tri par insertion est donc plus performant que les autres tris sur des petit tableaux, alors nous allons l'utiliser dans les autres tris, dans notre cas nous l'utiliserons sur le tri rapide pour voir s'il est possible d'améliorer le temps d'éxécution en consommant autant ou très légérement plus de mémoire en comparant donc les résultats obtenus en exécutant le tri rapide normal avec celui optimisé.
### Protocole expérimental de vérification de l'hypothèse
Pour se faire nous allons donc voir si effectivement le tri par insertion se déroule plus rapidement sur plein de petit tableaux, pour le test nous avons commencé avec des tableaux de taille 100, et au lieux de regarder le temps de chaque tri de faire le tri d'un tableau puis d'un autre, etc..., on va juste prendre le temps pour trier tout les tableaux.
En faisant certains test, nous avons aussi remarqué que le tri par insertion est encore plus rapide lorsque les tableaux à traiter sont déjà presque triés.
Tout d'abord pour tester l'hypothèse on fait un petit [script](src/Scripts/hypothese_perf.sh), ce script à été réalisé avec 1000 tableaux de 100 éléments.
Ce qui nous donne :
Donc maintenant il faut faire un tri rapide qui utilise le tri par insertion et l'intégrer au main.
### Résultats expérimentaux
### Analyse des résultats expérimentaux
- Les résultats du tri rapide sont en moyenne toujours en dessous du tri rapide optimisé avec le tri insertion, le cas est d'autant plus flagrant lorsque le tableaux traité est déjà trié.
- L'éxécution consomme autant de mémoire ou légérement plus que tri rapide.
Nous savons que les tableaux aléatoire sont beaucoup moins bien traités que les tableaux triès pour le tri insertion, et que les tableaux triés eux font exploser le tri rapide. En combinant les deux, nous améliorons nettement la vitesse de traitement des tableaux déjà triés et même la vitesse de traitement des tableaux random, et le tout pour au pire, une légére augmentation de l'espace mémoire pris par l'éxécution.
En conclusion nous pouvons donc voir que un tri qui en apparence n'est pas très bon peu aider pour réaliser un tri plus rapide, une telle association permet moins de cas spéciaux qui font exploser le temps d'éxécution.
Nous pouvons donc assez facilement imaginer d'autre cas de ce style pour d'autres tris, mais pour avoir un tel interêt à le faire sur d'autre tri, il faudrait passer énormément de temps sur des tris qui pourrait se compléter, pour leurs offrir une optimisation optimale, compliqué mais absolument pas insurmontable.