P4z : Analyse de performances de différents tris

Grille d'évaluation P4z

Problème

Description du Problème.

Description de tous les paramètres exploratoires du problème

Dispositif expérimental

Application

code source de l'application

Pour utiliser les tris, vous avez besoin de 2 choses:
- Le binaire tri
- 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 ..
Ex : 4 3 11 29 .

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 :
- -i ou --insertion pour le tri à insertion - -f ou --fusion pour le tri à fusion - -r ou --rapide pour le tri rapide - -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

Environnement de test

Les tests se sont fait sur troglo en connexion à distance, le fichier obtenu avec cat /proc/cpuinfo est disponible ici : cpuinfo

Description de la démarche systématique

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

Pour obtenir perf.dat contenant toutes les données (à exécuter dans src/Scripts/):

./perf.sh > perf.dat

Ensuite, il faut lancer R et exécuter les commandes du fichier src/R/perf.R :

R

library(ggplot2)
perf <- read.table("perf.dat", header = TRUE)
ggplot(perf, aes(x=taille, y=temps, group=tri, colour=tri)) + geom_point() + geom_smooth() + facet_grid(tri~sort) + ggtitle("Graphe des temps d'exécution")
ggsave("../Images/graphe_temps.png")
ggplot(perf, aes(x=taille, y=mem, group=tri, colour=tri)) + geom_point() + geom_smooth() + facet_grid(tri~sort) + ggtitle("Graphe des consommations mémoire")
ggsave("../Images/graphe_memoire.png")

Résultats préalables

Temps d'exécution

Consommation mémoire

Analyse des résultats préalables

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.

Discussion des résultats préalables

Explications précises et succinctes des limites des résultats préalables et ce qu'ils ne permettent pas de vérifier.

Etude approfondie

Hypothèse

Le tri 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ée que tout les autres algorithmes coupent leurs tableaux en de plus petit tableaux, Notre hypothése est, que si le tri insertion est donc plus performant que les autres tris sur des petit tableaux, alors nous allons utiliser le tri insertion dans les autres tris, par exemple avec tri rapide.

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

Pour ce faire nous allons donc voir si effectivement le tri 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 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 pour tester, ce script à été réalisé avec 1000 tableaux de 100 éléments.

./hypothese_perf.sh 

ce qui nous donne

Donc maintenant il faut faire un tri rapide qui utilise le tri insertion et l'intégrer au main.

Résultats expérimentaux

Analyse des résultats expérimentaux

Discussion des résultats expérimentaux

Conclusion et travaux futurs