forked from menault/2026_TD1_DEV51_Qualite_Algo
rabot
69 lines
3.1 KiB
Markdown
69 lines
3.1 KiB
Markdown
# 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](notes.md), [profil initial](out/profil_avant.txt),
|
|
[profil final](out/profil_apres_tri.txt) et [mesures globales](out/mesures_bilan.csv).
|