profil_apres.txt : profil gprof de la version finale (0,05 s profilées
contre 38,10 s). COMPTE_RENDU.md : complexités avant/après de F1 à F10,
M de chaque fonction calculé à la main (maximum 14 → 5), profils avant
et après, justification de chaque optimisation et résultats du concours
(3,05 s → 0,061 s en -O2, empreinte inchangée).
Groupe : Ryad MEHIRI, Luka PLOUVIER, Jimmy COLOMB-RAVAT.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
main enchaînait 6 boucles et 1 test (M = 8), le plus grand M du fichier
après F9. Les calculs passent dans analyser, qui remplit une structure
Resultats ; le rapport est construit par construire_rapport à l'aide de
ajouter_formatee (vsnprintf puis ajouter_ligne), qui garde tout le
format du rapport au même endroit ; ecrire_fichier et afficher
terminent. Le plus grand M du fichier est maintenant 5.
Rapport identique octet par octet. Empreinte inchangée
(ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
categorie enchaînait 13 décisions (if imbriqués, || et &&) : M = 14,
au-dessus de l'objectif M <= 10. Elle est découpée par sens de
l'opération : categorie (M = 3), categorie_debit (M = 5),
categorie_credit (M = 5), categorie_gros_credit (M = 3), plus le
prédicat est_week_end (M = 1) qui remplace les tests jour % 7 == 5 ||
jour % 7 == 6 et jour % 7 < 5.
Mêmes catégories sur tout le domaine (montant de -50 000 à 50 000,
jour % 210, client % 10 : 210 millions de combinaisons testées).
Complexité inchangée (O(1)). Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Pour chaque transaction, on cherchait le même client parmi toutes les
transactions précédentes (O(n²) au pire). Un tableau vu[NB_CLIENTS]
indique en O(1) si le client a déjà été rencontré.
Temps (-O2) : 0,073 s → 0,069 s (au niveau du bruit de mesure ; en -O0,
nb_clients_distincts passe de 0,32 s à 0). Empreinte inchangée
(ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Même correction que F3 : au lieu de reparcourir les 30 000 transactions
pour chacun des 1 000 jours (30 millions de tests), chaque montant est
ajouté directement au total de son jour.
Temps (-O2) : 0,087 s → 0,073 s. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Pour chacun des 2 000 clients, on reparcourait les 30 000 transactions
(60 millions de tests). On met les totaux à zéro, puis chaque montant
est ajouté directement au total de son client. Les montants de chaque
client sont additionnés dans le même ordre : les totaux sont identiques.
Temps (-O2) : 0,097 s → 0,087 s. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
La triple boucle recalculait la somme de chaque période (i, j) :
J(J+1)(J+2)/6 = 167 millions d'additions pour 1 000 jours. Avec les
sommes préfixes, la meilleure période finissant au jour j commence
juste après le plus petit préfixe vu jusque-là : un seul parcours
suffit. En gardant le premier minimum et en ne remplaçant le meilleur
que s'il est strictement dépassé, on retrouve la même période que
l'original en cas d'égalité (vérifié sur 200 000 tableaux aléatoires).
Temps (-O2) : 0,25 s → 0,10 s. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
La double boucle testait les n(n-1)/2 = 450 millions de paires. Sur le
tableau trié par F1, deux recherches dichotomiques donnent en O(log n) le
nombre de transactions de montant -v. On somme ces effectifs, on retire
les montants nuls (comptés avec eux-mêmes) et on divise par 2 (chaque
paire est vue deux fois). F7 est donc appelée après le tri dans main.
Temps (-O2) : 0,92 s → 0,25 s. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Chaque requête parcourait le tableau jusqu'à trouver l'id : 30 000
requêtes × 15 000 comparaisons en moyenne. Les id formant une
permutation de 0 à n-1, un tableau position[id] construit une fois en
O(n) donne chaque transaction en O(1). Le test r != NULL de main,
devenu impossible, est retiré.
Temps (-O2) : 1,08 s → 0,92 s. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
ajouter_ligne recalculait la longueur du rapport à chaque ligne : 6 017
parcours d'un texte qui grandit jusqu'à la taille finale L, soit
O(L × nombre de lignes). ajouter_ligne reçoit désormais la position de
fin et renvoie la nouvelle : chaque caractère n'est écrit qu'une fois.
La fonction longueur n'est plus utilisée et disparaît.
Profil -O0 : longueur (1,74 s) disparaît. En -O2, le gain reste dans le
bruit de mesure. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
La récursion naïve recalculait les mêmes sous-problèmes : 266 723 739
appels pour rendre 400 centimes avec 8 pièces. Le tableau facons[0..S],
mis à jour pièce par pièce, compte les mêmes combinaisons en S × k
additions (3 200 ici).
Temps (-O2) : 1,17 s → 1,00 s. En -O0 -pg, le surcoût de _mcount
(16,2 s) disparaît avec les appels récursifs. Empreinte inchangée
(ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Le tri à bulles faisait n(n-1)/2 = 450 millions de comparaisons pour
30 000 transactions. qsort trie en O(n log n) avec une fonction de
comparaison (montant, puis id). Les id étant distincts, l'ordre est
total et le résultat identique malgré un tri non stable.
Temps (-O2) : 3,05 s → 1,17 s. Empreinte inchangée (ff68d260a7a58441).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Ryad Mehiri
Maxime Menault