TD1_DEV51_Qualite_Algo/Compte_rendu.md

Analyse GProf

Flat profile : Donne le temps et le nombre d'execution par fonction comme bubblesort prend 80% du temps avec 1001000 calls

cumulative   self

time seconds seconds calls s/call s/call name
77.59 2.13 2.13 1001000 0.00 0.00 bubblesort 22.22 2.74 0.61 1000000 0.00 0.00 find_rank_student 0.36 2.75 0.01 1 0.01 2.75 sort_students 0.00 2.75 0.00 1000 0.00 0.00 generate_array 0.00 2.75 0.00 2 0.00 0.00 free_array 0.00 2.75 0.00 1 0.00 0.00 generate_grades 0.00 2.75 0.00 1 0.00 0.00 generate_ranks

Fonction bubblesort est appelé 1001000 Fonction find_rank_student est appelée 1000000

*Devra donc optimiser pour réduire le temps ?

Call graph: Voir arbre appel de fonctiopns + Temps et nombre execution par fonction

Call graph (explanation follows)

granularity: each sample hit covers 2 byte(s) for 0.36% of 2.75 seconds

index % time self children called name 0.01 2.74 1/1 main [2] [1] 100.0 0.01 2.74 1 sort_students [1] 0.61 2.13 1000000/1000000 find_rank_student [3] 0.00 0.00 1000/1001000 bubblesort [4]

                                             <spontaneous>

[2] 100.0 0.00 2.75 main [2] 0.01 2.74 1/1 sort_students [1] 0.00 0.00 2/2 free_array [6] 0.00 0.00 1/1 generate_grades [7] 0.00 0.00 1/1 generate_ranks [8]

            0.61    2.13 1000000/1000000     sort_students [1]

[3] 99.6 0.61 2.13 1000000 find_rank_student [3] 2.13 0.00 1000000/1001000 bubblesort [4]

            0.00    0.00    1000/1001000     sort_students [1]
            2.13    0.00 1000000/1001000     find_rank_student [3]

[4] 77.5 2.13 0.00 1001000 bubblesort [4]

            0.00    0.00    1000/1000        generate_grades [7]

[5] 0.0 0.00 0.00 1000 generate_array [5]

            0.00    0.00       2/2           main [2]

[6] 0.0 0.00 0.00 2 free_array [6]

            0.00    0.00       1/1           main [2]

[7] 0.0 0.00 0.00 1 generate_grades [7] 0.00 0.00 1000/1000 generate_array [5]

            0.00    0.00       1/1           main [2]

[8] 0.0 0.00 0.00 1 generate_ranks [8]

L'index correspond à chaque fonction appelée exemple: [1] sort_students Dans index [1] main appele sort_students[1] et find_rank_student[3], bubblesort[4] est appelées dans sort_students[1] Quand main est appelé 1 fois il appele 1 fois sort_students d'ou le 1/1 dans called Quand find_rank_student est appelé 10 fois il appele 1 fois sort_students d'ou le 1/1 dans called

Analyse et modification

Fonction plus lente : bubblesort Nombre appel important de buublesort dans find_rank.student

int find_rank_student(int student_grade, int* grades_array, int students_number) { int position = -1; int i = 0;

/*bubblesort(grades_array,students_number);*/
for(i = students_number-1; i >= 0; i--)
{
    if(grades_array[i] == student_grade)
{
        position = students_number-i;
    break;
}
}
return position;

}

Mettre en commentaire bubblesort /* */

void bubblesort(int* array, int length) { int swapped, i, tmp; do { swapped = 0; for(i=1;i<length;i++) { if(array[i-1] > array[i]) { tmp = array[i-1]; array[i-1] = array[i]; array[i] = tmp; swapped++; } } } while(swapped > 0); }

Changement de swapped > 0 au lieu de swapped == 1; Pour le tri à bulle comparaison entre deux nombres et voir le plus petit si c'est croissant

Tri par tas plus rapide pour les gros tableaux que les tri par bulle