README.md

P4z : Analyse de performances de différents tris

Problème

Dans l'analyse de performances de différents tris il est necessaire de trouver l'utilisation optimal pour chacun des algorithme de tris. Ainsi nous devons essayer de comprendre pourquoi certain algorithme ne fonctionnent pas avec chaques tableau mais aussi trouvre les limites qui nous empêcherais d'utiliser cette algorithme.

Pour se faire il faut bien comprendre pourquoi et comment est influé le temps et la consommation de mémoire grace aux différents parametres de celui-ci:

- Le temps d'éxécution d'un tri (Sur les tableaux de differentes allures)
- La consommation de memoire lors du tri (Sur les tableaux de differentes allures)
- Son estimation de temps d'execution (La fonction O(f) -> log(n), n^2, nlog(n), etc)
- Pareil pour la memoire
- Le nombre de comparaisons total
- Le nombre d'ecritures total

Nous allons donc chercher à comprendre l'influence des paramètres ci-dessus sur la rapidité et l'optimisation des algorithme. Par la suite nous comprendrons mieux l'application de chacun des algorithme et nous essaierons de trouver un correctif pour améliorer nos performances.

Dispositif expérimental

Application

Main

main --taille --typeTableau --typeTri 

Arguments	Default	Description
--taille	1000	La taille du tableau de n éléments.
--typeTableau -aricm	a	Défini le type du tableau avec a aléatoire, t trié, i inversé, c identique et m trié à moitié.
--typeTri -irf	i	Algorithme de tri avec i insertion, r rapide et f fusion.

./utils.c

Le main se contente d'initialiser les paramètres, les fonctions de création et d'affichage du tableau sont dans le fichier utils.c. Par la suite, le main choisit le bon tri via un switch.

Dans le fichier utils on retrouve :
    - afficherTab : qui parcourt le tableau et affiche chacun de ses elements
    - genTab : ils recoit un pointeur sur un tableau, sa taille, le type du tableau (les mêmes que dans le main) et la taille max des elements du tableau.

Environnement de test

Nos test sont réalisé sur le serveur Phoenix avec comme caractéristique

Processeur(s) :                         40
Liste de processeur(s) en ligne :       0-39
Thread(s) par cœur :                    2
Cœur(s) par socket :                    10
Socket(s) :                             2

Nom de modèle :                         Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz
Vitesse maximale du processeur en MHz : 3100,0000
Cache L1d :                             32K
Cache L1i :                             32K
Cache L2 :                              256K
Cache L3 :                              25600K

Description de la démarche systématique

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.
    - Executer le shell script: ./perf.sh
    - Executer le R script pour produire le graphe: Rscript rplot3.R

Résultats préalables

Temps d'exécution

Jeu de test	Tri par Insertion	Tri Fusion	Tri Rapide	Tri à bulle
		1	2	3

Consommation mémoire

Jeu de test	Tri par Insertion	Tri Fusion	Tri Rapide	Tri à bulle
Aléatoire

Analyse des résultats préalables

Qu'est-ce qu'on voit:

- Tri Fusion est le plus efficace dans la rapidite pour tout type de tableaux, mais la consommation de memoire reste a ameliorer

- Tri Rapide est tres rapide sur des tableaux aleatoires, mais la vitesse d'execution explose pour les tableaux constants, ranges et inverses

- Tri Insertion est beaucoup moins rapide que les deux autres algos sur les tableaux aleatoires (plus de 1 seconde de plus), mais ne fait aucune operation sur les tableaux constants et ranges, ce qui peut etre un tres grand atout dans quelques situations. Par contre son temps d'execution explose pour les tableaux inversés
- Tri A Bulle est le pire de nos quatre algos car il metra un temps monstre pour trié peut importe le type de tableaux que l'on lui donne, mais les tableau aleatoire reste les pires

Explication detaillee:

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

Expression précise et succincte d'une hypothèse.

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

Expression précise et succincte du protocole.

Suite des commandes, ou script, à exécuter pour produire les données.

Résultats expérimentaux

Analyse des résultats expérimentaux

Discussion des résultats expérimentaux

Conclusion et travaux futurs