2026_TD1_DEV51_Qualite_Algo/COMPTE_RENDU.md

Compte rendu — Optimisation de l'analyseur de mots

R5.A.04 — Qualité algorithmique

Adrien RABOT — Théo ANASTASIO

1. Objectif et méthode

Réduire le temps d'exécution sans modifier les résultats, sur un texte fixe contenant 250 000 mots et 5 866 mots distincts retenus.

Les temps sont mesurés avec gcc -O0, sans -pg. Le profil est obtenu séparément avec gcc -O0 -pg et gprof, car l'instrumentation ralentit le programme.

2. Analyse et pistes prioritaires

Le profil initial conduit aux priorités suivantes, classées par gain attendu :

1. Accélérer la recherche des mots. La recherche linéaire provoque 296 656 203 appels à egales. Une recherche dichotomique ou une table de hachage permet de réduire ces comparaisons.
2. Calculer la moyenne une seule fois. longueur_moyenne est appelée 5 867 fois, car la variance recalcule la même moyenne pour chaque mot.
3. Supprimer les parcours répétés des chaînes. longueur est appelée 36 009 819 fois au total. Mémoriser les longueurs et les positions de fin évite de reparcourir les mots, les lignes et le rapport.
4. Remplacer le tri à bulles. Ses 17 202 045 appels à doit_echanger justifient un tri en O(n log n).

3. Optimisations et gains mesurés

Chaque gain est relatif à la version précédente. Les deux premières étapes reposent sur une mesure ponctuelle ; les suivantes utilisent la médiane de cinq exécutions par version.

Optimisation	Modification	Avant	Après	Temps gagné
Recherche dichotomique	Tableau maintenu trié, recherche en O(log n)	2,80 s	1,45 s	≈ 48 %
Moyenne	Un seul calcul, transmis au calcul de variance	1,46 s	0,88 s	≈ 40 %
Table de hachage	Recherche et insertion en O(1) en moyenne	0,888 s	0,831 s	6,4 %
Longueurs et chaînes	Champ taille, arrêt sur \0, position de fin conservée	0,832 s	0,362 s	56,5 %
Tri par tas	Tri en O(n log n), sans tableau supplémentaire	0,367 s	0,113 s	69,3 %

La version finale utilise le hachage à la place de la dichotomie. Son gain supplémentaire reste limité car la recherche était déjà efficace.

Tous les appels à longueur sont supprimés. Le tri ne fait plus que 129 602 appels à doit_echanger, soit environ 133 fois moins. Le classement reste par fréquence décroissante, puis par ordre alphabétique.

4. Bilan et validation

Une comparaison directe des versions initiale et finale donne les médianes suivantes, sur cinq exécutions par version dans les mêmes conditions :

Mesure	Version initiale	Version finale
Temps réel	2,81 s	0,11 s
Pic mémoire résident (RSS)	6 664 Kio	6 668 Kio

Le programme est environ 25,5 fois plus rapide, soit 96,1 % de temps en moins sur ce jeu de données.

Le rapport et la sortie console sont identiques octet par octet. L'empreinte reste 1d53de903efd2b7c.

Sources : notes, profil initial, profil final et mesures globales.