Prédire une croissance, la mesurer, et expliquer l'écart éventuel.
Scénario
HashBox hésite entre trois implémentations pour détecter des doublons dans les inscriptions. L'équipe veut un rapport avec des courbes, pas des impressions.
Objectif
Concevoir un banc d'essai fiable, mesurer trois algorithmes sur plusieurs tailles, estimer leur exposant de croissance et le comparer à la théorie.
Environnement
Python 3.10 ou plus. Modules standard seulement : time, statistics, random, cProfile, pstats.
État de départ
Un fichier bench.py vide. Trois fonctions à écrire : doublon_double_boucle, doublon_ensemble, doublon_tri.
Tâches
- Écris les trois fonctions et vérifie qu'elles donnent les mêmes résultats sur 300 entrées aléatoires.
- Écris un outil
mesurer(f, donnees, repetitions)qui renvoie la médiane. - Génère trois jeux de données par taille : sans doublon, doublon au début, doublon à la fin.
- Mesure pour au moins 5 tailles (en doublant à chaque fois).
- Calcule le rapport T(2n)/T(n) et estime l'exposant k pour chaque méthode et chaque jeu.
- Profile la méthode la plus lente avec
cProfileet nomme le goulot. - Rédige un paragraphe : la théorie prévoyait-elle ces résultats ? Où sont les écarts ?
Observations attendues
- Les trois fonctions donnent les mêmes résultats.
- La double boucle montre un exposant proche de 2 sur le jeu sans doublon et beaucoup moins si le doublon est au début.
- La méthode par ensemble montre un exposant proche de 1.
- La méthode par tri se situe entre 1 et 1,3.
- Le profil désigne la double boucle comme goulot.
Validation
Le script bench.py se relance de bout en bout et affiche le tableau des temps et des exposants. Les ordres de grandeur sont stables d'une exécution à l'autre (à ±30 %).
Indices
💡 Indice 1
Fixe random.seed(...) pour des jeux de données reproductibles.
💡 Indice 2
Limite la taille maximale de la double boucle pour que le script reste court.
💡 Indice 3
Un exposant de 1,2 pour du O(n log n) est normal.
Preuves à rendre
-
bench.py - Tableau des temps et exposants (copié dans le rapport)
- Rapport d'une page : méthode, résultats, explication des écarts
Réflexion
- Quelle mesure t'a le plus surpris·e ?
- Qu'est-ce qui rendrait ta conclusion fausse sur un autre ordinateur ?
HEF-030 — Complexité
Atelier Python

