forked from menault/TD1_DEV51_Qualite_Algo
32 lines
1.6 KiB
Plaintext
32 lines
1.6 KiB
Plaintext
Rapport TD1 :
|
|
|
|
J'ai compilé la commande : "gcc -g -pg -o student_rank student_rank.c heapsort.c bubblesort.c" ce qui a créé gmon.out en plus de compiler grâce
|
|
à -pg.
|
|
|
|
Puis est lancer le code avec "./student_rank <Nombre etudiants> <Nombre notes par etudiants> <mode debug (0 ou 1)>" les informations
|
|
qui seront utilisés tout le reste du TD sont 1000 étudiants, 1000 notes et mode 0.
|
|
|
|
En ajoutant "time" devant la commande pour lancer le code l'on obtient le temps de l'exécution qui est de 3 secondes environ pour 1000 étudiants
|
|
et de plus de 1 minute pour 5000 étudiants.
|
|
|
|
L'on utilise l'outil GPROF avec fait la commande "gprof student_rank".
|
|
|
|
Gprof :
|
|
Flat profile = temps et nombre d'exécution par fonction
|
|
Call graph = arbre appel fonctions + temps et nombre d'exécution par fonction
|
|
|
|
Fonction la plus lente = bubblesort
|
|
|
|
Le problème vient du nombre d'appels de bubblesort donc il faudrait réduire son nombre d'appels.
|
|
|
|
Dans student_rank un des appels de la fonction bubblesort est inutile, j'ai mis en commentaire l'appel de bubblesort ligne 58 de la fonction
|
|
find_rank_student dans student_rank.c. Le temps gagner est colossal. Mais un problème dans le classement car il n'est pas à 100% correct.
|
|
|
|
L'on modifie dans bubblesort.c la ligne 20 à la place du "swapped==1" on met "swapped>0", mais du coup le code remet beaucoup de temps.
|
|
|
|
Si l'on modifie à la ligne 80 du student_rank on change "bubblesort" par "heapsort" l'exécution est 10 fois plus rapide.
|
|
Dernière vérification avec GPROF pour voir s'il y a moyen d'optimiser plus (possiblement sift)
|
|
|
|
|
|
Recherche sur Wikipédia sur le Tri rapide.
|