forked from menault/2026_TD1_DEV51_Qualite_Algo
61 lines
3.6 KiB
Plaintext
61 lines
3.6 KiB
Plaintext
Derqsi bilal
|
|
Pierre Courtehoux
|
|
Youness Boulalam
|
|
|
|
Mesurer / Profiler
|
|
Temps d'exécution et empreinte sans -pg
|
|
Empreinte du rapport : 1d53de903efd2b7c
|
|
L'empreinte permet de vérifier que l'exécution du programme retourne exactement le même résultat après les optimisations.
|
|
real 0m2.659s
|
|
user 0m2.637s
|
|
sys 0m0.004s
|
|
Profilage
|
|
La fonction la plus appelée est egales(), avec 308 701 874 appels, pour un temps d'exécution de 0,72 seconde.
|
|
La deuxième fonction qui consomme le plus de temps est longueur(), avec 36 009 819 appels, pour un temps d'exécution de 0,69 seconde.
|
|
% cumulative self self total
|
|
time seconds seconds calls ms/call ms/call name
|
|
33.26 0.72 0.72 308701874 0.00 0.00 egales
|
|
31.42 1.41 0.69 36009819 0.00 0.00 longueur
|
|
14.68 1.73 0.32 150182 0.00 0.01 chercher_mot
|
|
Analyse
|
|
On peut voir qu'une grande partie du temps d'exécution, soit environ 80 %, est concentrée dans les trois fonctions egales(), longueur() et chercher_mot().
|
|
Cette consommation importante s'explique par le fait que ces fonctions sont très fréquemment utilisées.
|
|
Par exemple, egales() compare les caractères des chaînes un par un afin de déterminer si deux mots sont identiques. Elle est donc appelée un très grand nombre de fois.
|
|
On peut également constater que la majorité des appels à egales() provient de chercher_mot() :
|
|
296 656 203 / 308 701 874 appels
|
|
Cela montre que chercher_mot() est un point important à optimiser afin de réduire le nombre d'appels à egales() et d'obtenir un maximum de gain avec un minimum de modifications.
|
|
Optimisation 1 : réduire le nombre d'appels à egales()
|
|
Il n'est pas nécessairement possible d'améliorer significativement la fonction egales() elle-même, car son fonctionnement est déjà simple : elle parcourt les caractères des deux chaînes jusqu'à trouver une différence ou atteindre la fin.
|
|
En revanche, on peut réduire fortement le nombre de fois où cette fonction est appelée.
|
|
La fonction chercher_mot() effectue actuellement une recherche linéaire dans le tableau des mots. Pour chaque nouveau mot, elle compare celui-ci avec les mots déjà présents dans le tableau.
|
|
Une amélioration importante serait donc d'utiliser une table de hachage afin de retrouver directement le mot recherché, au lieu de parcourir successivement toutes les entrées.
|
|
Cette optimisation permettrait de réduire fortement le nombre d'appels à egales() et donc le temps d'exécution.
|
|
Optimisation 2 : calculer la moyenne une seule fois
|
|
Dans ecart_type_longueur(), la moyenne était recalculée à chaque itération de la boucle.
|
|
La moyenne ne change pourtant pas pendant cette boucle. Il est donc inutile de la recalculer plusieurs milliers de fois.
|
|
La fonction peut être modifiée ainsi :
|
|
double somme = 0.0;
|
|
double moyenne = longueur_moyenne(table, n);
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
double ecart = longueur(table[i].mot) - moyenne;
|
|
somme += ecart * ecart;
|
|
}
|
|
|
|
return somme / n;
|
|
Cette modification permet de calculer la moyenne une seule fois, au lieu de la recalculer pour chaque mot.
|
|
Résultat après optimisation
|
|
L'empreinte du rapport reste identique :
|
|
Empreinte du rapport : 1d53de903efd2b7c
|
|
Cela confirme que le résultat du programme n'a pas été modifié par l'optimisation.
|
|
Après compilation avec :
|
|
gcc -O0 analyseur.c -o analyseur
|
|
et exécution avec :
|
|
time ./analyseur
|
|
on obtient :
|
|
real 0m2.107s
|
|
user 0m2.081s
|
|
sys 0m0.003s
|
|
Avant optimisation, le temps real était de 2,659 secondes. Après optimisation, il est de 2,107 secondes.
|
|
On obtient donc un gain d'environ 0,55 seconde, soit environ 21 % de réduction du temps d'exécution.
|