La théorie prédit, la mesure confirme. Savoir mesurer proprement est une compétence à part entière.
⏱️ Durée : environ 70 minutes · 🎓 Niveau : débutant · 🏅 Badge : Scientifique du code
🎬 L'histoire
Kodi a optimisé une fonction et annonce fièrement : « C'est deux fois plus rapide ! » Sam demande : « Combien de fois as-tu mesuré ? Sur quelles données ? Et sur quelle machine ? » Kodi n'a mesuré qu'une fois, sur 10 éléments, pendant qu'il écoutait de la musique.
« Une mesure sans protocole n'est qu'une opinion », dit Sam.
Dans cette mission, tu apprends à construire des benchmarks fiables et à lire leurs résultats.
🎯 Ta mission
À la fin, je serai capable de :
- mesurer proprement avec
time.perf_counterettimeit - répéter les mesures et utiliser la médiane
- mesurer pour plusieurs tailles de données
- estimer l'exposant de croissance à partir de mesures
- identifier les causes de mesures trompeuses
🧩 Défi d'échauffement (5 XP)
Tu veux savoir si ton trajet à vélo est plus rapide que le bus. Tu le fais une fois : vélo 22 min, bus 25 min. Peux-tu conclure ? Liste cinq raisons pour lesquelles ta mesure pourrait être trompeuse. Que ferais-tu pour la rendre fiable ?
💡 Le concept
Les bases d'une bonne mesure
- Répéter : une mesure isolée est bruitée.
- Prendre la médiane (ou le minimum) plutôt que la moyenne, moins sensible aux pics.
- Varier n pour voir la tendance, pas un seul point.
- Isoler ce qu'on mesure : ne pas inclure la génération des données.
- Contrôler : mêmes données pour comparer deux versions.
- Noter l'environnement : machine, version de Python, charge.
time.perf_counter
import time
debut = time.perf_counter()
sorted(range(100000, 0, -1))
duree = time.perf_counter() - debut
print(round(duree, 5))
timeit
timeit répète le code et réduit le bruit.
import timeit
t = timeit.repeat("sorted(donnees)", setup="donnees = list(range(1000, 0, -1))", number=100, repeat=5)
print(min(t) / 100) # meilleur temps moyen par exécution
Un petit banc d'essai réutilisable
import time, statistics
def mesurer(f, donnees, repetitions=5):
temps = []
for _ in range(repetitions):
t = time.perf_counter()
f(donnees)
temps.append(time.perf_counter() - t)
return statistics.median(temps)
Estimer l'exposant
Si le temps vaut c × nᵏ, alors en doublant n le temps est multiplié par 2ᵏ. Le rapport entre deux mesures donne k :
| Rapport T(2n) / T(n) | Croissance probable |
|---|---|
| ≈ 1 | O(1) |
| ≈ 2 | O(n) |
| un peu plus de 2 | O(n log n) |
| ≈ 4 | O(n²) |
| ≈ 8 | O(n³) |
Pièges de mesure
| Piège | Effet |
|---|---|
| Chauffer le cache / première exécution | première mesure plus lente |
| Trop petit n | bruit plus grand que le signal |
| Données favorables (déjà triées) | résultat non représentatif |
| Autre programme en cours | pics aléatoires |
| Mesurer la création des données | on mesure autre chose |
🧠 Astuce : une courbe vaut mieux qu'un chiffre. Trace le temps pour 5 valeurs de n.
🔍 Exemple pas à pas
Problème : estimer le Big O de a_doublon à partir de mesures.
import time, statistics
def a_doublon(liste):
for i in range(len(liste)):
for j in range(i + 1, len(liste)):
if liste[i] == liste[j]:
return True
return False
def mesurer(f, donnees, repetitions=5):
temps = []
for _ in range(repetitions):
t = time.perf_counter()
f(donnees)
temps.append(time.perf_counter() - t)
return statistics.median(temps)
precedent = None
for n in (250, 500, 1000, 2000):
t = mesurer(a_doublon, list(range(n)))
rapport = "" if precedent is None else f"x{t / precedent:.1f}"
print(n, round(t, 4), rapport)
precedent = t
Lecture : à chaque doublement de n, le rapport est autour de 4 : la croissance est quadratique, ce qu'on attendait.
Remarque : on a utilisé une liste sans doublon (pire cas). Avec une liste qui commence par deux valeurs identiques, la fonction s'arrête tout de suite : mesurer le meilleur cas aurait donné une conclusion fausse.
✍️ À toi, avec aide (10 XP)
Mesure sorted sur des listes aléatoires de n = 20 000, 40 000, 80 000, 160 000 éléments.
- Génère les données avant la mesure.
- Répète 5 fois et prends la médiane.
- Calcule les rapports T(2n)/T(n). Que concluds-tu ?
💡 Indice 1
Utilise random.random() pour générer.
💡 Indice 2
Appelle sorted(donnees) dans la mesure ; ne mesure pas la génération.
💡 Indice 3
Pour du O(n log n), le rapport est un peu au-dessus de 2.
✅ Réponse
import random, time, statistics
def mesurer(f, donnees, repetitions=5):
temps = []
for _ in range(repetitions):
t = time.perf_counter()
f(donnees)
temps.append(time.perf_counter() - t)
return statistics.median(temps)
precedent = None
for n in (20000, 40000, 80000, 160000):
donnees = [random.random() for _ in range(n)]
t = mesurer(sorted, donnees)
print(n, round(t, 4), "" if precedent is None else f"x{t / precedent:.2f}")
precedent = t
Les rapports sont un peu supérieurs à 2 : cohérent avec O(n log n).
🚀 À toi, en solo (20 XP)
Écris un outil courbe(f, generateur, tailles) qui, pour une fonction f, un générateur de données generateur(n) et une liste de tailles, renvoie la liste [(n, temps_median)] et affiche une estimation de l'exposant k par régression simple : k ≈ log(T2/T1) / log(n2/n1), moyenné sur les paires consécutives.
Teste-le sur : parcours simple (k ≈ 1), double boucle (k ≈ 2), sorted (k un peu au-dessus de 1).
✅ Pistes de correction
import math, random, statistics, time
def courbe(f, generateur, tailles, repetitions=5):
points = []
for n in tailles:
donnees = generateur(n)
temps = []
for _ in range(repetitions):
t = time.perf_counter()
f(donnees)
temps.append(time.perf_counter() - t)
points.append((n, statistics.median(temps)))
exposants = [math.log(t2 / t1) / math.log(n2 / n1)
for (n1, t1), (n2, t2) in zip(points, points[1:]) if t1 > 0 and t2 > 0]
k = sum(exposants) / len(exposants)
return points, k
def parcours(l):
s = 0
for x in l:
s += x
return s
def double(l):
c = 0
for a in l:
for b in l:
c += 1
return c
gen = lambda n: list(range(n))
for nom, f, tailles ((, parcours, (, , )), (, double, (, , ))):
_, k = courbe(f, gen, tailles)
(nom, , (k, ))
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Une seule mesure | Bruit pris pour un résultat | Répéter et prendre la médiane |
| Mesurer la préparation des données | On mesure autre chose | Séparer génération et mesure |
| Un seul n | Impossible de voir la tendance | Au moins 4 ou 5 tailles |
| Comparer sur des données différentes | Comparaison injuste | Mêmes données pour les deux versions |
🐉 Mini-boss (40 XP)
Banc d'essai complet. Compare trois façons de détecter un doublon : double boucle, len(set(l)) != len(l), et tri puis comparaison des voisins.
- Génère trois jeux : sans doublon (pire cas), avec doublon au début, avec doublon à la fin.
- Mesure pour n = 1 000, 2 000, 4 000, 8 000 (réduis n pour la double boucle si besoin).
- Remplis un tableau et estime l'exposant de chaque méthode sur chaque jeu.
- Écris un rapport de 10 lignes : conclusions, limites de ta mesure, recommandation.
✅ Pistes de correction
import statistics, time
def v1(l):
for i in range(len(l)):
for j in range(i + 1, len(l)):
if l[i] == l[j]:
return True
return False
def v2(l):
return len(set(l)) != len(l)
def v3(l):
s = sorted(l)
return any(s[i] == s[i + 1] for i in range(len(s) - 1))
def mes(f, d, r=3):
t = []
for _ in range(r):
a = time.perf_counter(); f(d); t.append(time.perf_counter() - a)
return statistics.median(t)
for n in (500, , ):
jeux = {: ((n)), : [, ] + ((, n)), : ((n - )) + []}
nom, d jeux.items():
(n, nom, *((mes(f, d), ) f (v1, v2, v3)))
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Pour réduire le bruit d'une mesure, on :
- A. la fait une seule fois
- B. la fait pendant un téléchargement
- C. la répète et prend la médiane
2. Si T(2n)/T(n) ≈ 4, la croissance est :
- A. quadratique
- B. linéaire
- C. constante
3. On ne doit pas inclure dans la mesure :
- A. l'appel de la fonction
- B. la génération des données
- C. le calcul du résultat
4. 🔁 Révision mission 06 : Trier avant de chercher est rentable quand :
- A. on fait une seule recherche
- B. les données changent sans cesse
- C. on fait beaucoup de recherches
5. 🔁 Révision mission 07 : Un cache sans limite risque de :
- A. consommer toute la mémoire
- B. ralentir le processeur
- C. effacer les données
✅ Réponses
- C.
- A.
- B.
- C.
- A.
🪞 Je réfléchis (10 XP)
- Quelle « mesure rapide » as-tu déjà prise pour une vérité ?
- Comment expliquerais-tu à un collègue pourquoi on prend la médiane ?
🎒 À retenir
- Répéter, prendre la médiane, varier n.
- Séparer préparation des données et mesure.
- Le rapport T(2n)/T(n) révèle la croissance.
- Mesurer aussi le pire cas.
- Noter l'environnement de mesure.
flowchart LR
T(["Mesurer pour de vrai"])
T --> R1["1. Répéter, prendre la médiane, varier n."]
T --> R2["2. Séparer préparation des données et mesure."]
T --> R3["3. Le rapport T2n/Tn révèle la croissance."]
T --> R4["4. Mesurer aussi le pire cas."]
T --> R5["5. Noter l'environnement de mesure."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Scientifique du code
← Mission 07 — Espace mémoire et compromis temps-mémoire · Mission 09 — Profilage : trouver où le temps passe →
HEF-030 — Complexité

