Aller plus vite en utilisant plus de mémoire, ou économiser la mémoire en acceptant d'aller plus lentement.
⏱️ Durée : environ 70 minutes · 🎓 Niveau : débutant · 🏅 Badge : Équilibriste
🎬 L'histoire
Le serveur de HashBox plante : « MemoryError ». Après avoir ajouté un cache géant pour accélérer les pages, Kodi a consommé toute la mémoire.
« Le temps et la mémoire sont deux ressources, dit Sam. Quand tu en gagnes sur l'une, tu en perds souvent sur l'autre. Il faut décider en connaissance de cause. »
Tu apprends à mesurer la complexité en espace et à arbitrer entre temps et mémoire.
🎯 Ta mission
À la fin, je serai capable de :
- définir la complexité en espace
- distinguer mémoire de l'entrée et mémoire supplémentaire
- identifier des compromis temps-mémoire classiques
- mesurer la mémoire d'une structure avec
sys.getsizeofettracemalloc - décider si un cache est une bonne idée
🧩 Défi d'échauffement (5 XP)
Tu organises une fête et tu dois te souvenir de 100 allergies d'invités. Option A : tu les notes toutes sur une feuille (coûte du papier, mais lecture instantanée). Option B : tu les redemandes à chaque invité (aucun papier, mais beaucoup de temps). Dans quelles situations choisirais-tu A, ou B ?
💡 Le concept
La complexité en espace
C'est la quantité de mémoire supplémentaire utilisée en fonction de n, sans compter l'entrée elle-même.
| Algorithme | Mémoire supplémentaire |
|---|---|
| Somme d'une liste | O(1) (une variable) |
| Copie de liste | O(n) |
| Tri par insertion | O(1) (sur place) |
| Tri fusion | O(n) |
| Récursion de profondeur p | O(p) (la pile d'appels) |
| Fibonacci avec mémo | O(n) |
Compromis classiques
| On gagne du temps en… | …au prix de la mémoire |
|---|---|
| gardant un ensemble pour tester la présence | O(n) mémoire |
| mémoïsant les résultats | O(nombre de sous-problèmes) |
| construisant un index | taille de l'index |
| précalculant une table | taille de la table |
Dans l'autre sens, on économise de la mémoire en recalculant à la demande, en compressant, ou en traitant les données par flux (un morceau à la fois).
Flux et générateurs
Plutôt que de charger un fichier de 10 Go en mémoire, on le lit ligne par ligne. En Python, un générateur produit les valeurs une à une.
def carres_liste(n):
return [i * i for i in range(n)] # n valeurs en mémoire
def carres_generateur(n):
for i in range(n):
yield i * i # une valeur à la fois
print(sum(carres_generateur(1000))) # même résultat, mémoire O(1)
Mesurer la mémoire
import sys
print(sys.getsizeof([0] * 1000)) # taille de la liste elle-même
print(sys.getsizeof(set(range(1000))))
tracemalloc suit la mémoire utilisée par un bloc de code :
import tracemalloc
tracemalloc.start()
donnees = [i for i in range(100000)]
courant, pic = tracemalloc.get_traced_memory()
tracemalloc.stop()
print(courant // 1024, "Ko")
🧠 Astuce : avant d'ajouter un cache, demande « combien d'éléments au maximum, et combien d'octets chacun ? »
🔍 Exemple pas à pas
Problème : comparer la mémoire d'une liste et d'un générateur pour 1 million de valeurs.
import sys
liste = [i for i in range(1_000_000)]
gen = (i for i in range(1_000_000))
print("liste :", sys.getsizeof(liste) // 1024, "Ko")
print("générateur:", sys.getsizeof(gen), "octets")
print(sum(liste) == sum(i for i in range(1_000_000))) # même résultat
Observation : la liste occupe plusieurs mégaoctets (8 octets par référence au minimum, sans compter les entiers eux-mêmes) ; le générateur quelques centaines d'octets.
Le compromis : le générateur ne permet de lire les valeurs qu'une seule fois, dans l'ordre. La liste permet l'accès par indice et plusieurs parcours.
Cache avec borne : on limite la taille du cache pour contrôler la mémoire.
from functools import lru_cache
@lru_cache(maxsize=128)
def carre_couteux(n):
return n * n
for i in range(1000):
carre_couteux(i % 200)
print(carre_couteux.cache_info())
✍️ À toi, avec aide (10 XP)
Écris deux versions de moyenne_fichier(lignes) où lignes est un itérable de textes contenant chacun un nombre :
- une version qui construit d'abord la liste de tous les nombres ;
- une version qui calcule la moyenne en un seul passage, avec 2 variables.
Compare la mémoire avec tracemalloc pour 200 000 lignes.
💡 Indice 1
La version flux garde seulement somme et compte.
💡 Indice 2
Utilise (str(i) for i in range(200000)) comme source.
💡 Indice 3
Compare le pic mémoire get_traced_memory()[1].
✅ Réponse
import tracemalloc
def moyenne_liste(lignes):
nombres = [float(l) for l in lignes]
return sum(nombres) / len(nombres)
def moyenne_flux(lignes):
somme, compte = 0.0, 0
for l in lignes:
somme += float(l)
compte += 1
return somme / compte
def pic(f):
tracemalloc.start()
f((str(i) for i in range(200000)))
_, p = tracemalloc.get_traced_memory()
tracemalloc.stop()
return p // 1024
print("liste:", pic(moyenne_liste), "Ko ; flux:", pic(moyenne_flux), "Ko")
La version flux est en O(1) mémoire ; la liste en O(n).
🚀 À toi, en solo (20 XP)
Table de précalcul. Tu dois répondre très vite à 100 000 questions « combien y a-t-il d'entiers premiers inférieurs ou égaux à x ? » pour x ≤ 100 000.
- Version sans précalcul : compter à chaque question.
- Version avec précalcul : une table construite une fois.
- Compare le temps et la mémoire. Quand le précalcul est-il justifié ?
✅ Pistes de correction
import time, random
N = 100_000
def est_premier(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
def sans_precalcul(x):
return sum(1 for k in range(2, x + 1) if est_premier(k))
# crible d'Ératosthène + table cumulée
crible = [True] * (N + 1)
crible[0] = crible[1] = False
for i in range(2, int(N ** 0.5) + 1):
if crible[i]:
for j in range(i * i, N + 1, i):
crible[j] =
cumul, c = [] * (N + ),
k (N + ):
c += crible[k]
cumul[k] = c
(sans_precalcul(x) == cumul[x] x (, , ))
t = time.perf_counter()
_ ():
cumul[random.randint(, N)]
((time.perf_counter() - t, ), , N + , )
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Cache sans limite | La mémoire grossit jusqu'au plantage | Borner la taille (lru_cache(maxsize=…)) |
| Charger tout en mémoire | MemoryError sur les gros fichiers | Lire par flux |
| Ignorer la pile d'appels | Récursion profonde = mémoire et RecursionError | Utiliser une boucle |
| Optimiser la mémoire sans besoin | Code plus complexe pour rien | Mesurer d'abord |
🐉 Mini-boss (40 XP)
Le cache de HashBox. La page de profil appelle calculer_stats(membre_id) (coûteux : simulé par un calcul de 5 ms). 50 000 membres, mais 80 % des requêtes concernent 500 membres populaires.
- Écris la fonction sans cache et mesure 2 000 requêtes générées selon cette répartition.
- Ajoute
lru_cacheavecmaxsize= 100, 500, 5 000. - Mesure temps total et mémoire pour chaque taille.
- Recommande une taille de cache avec une justification chiffrée.
✅ Pistes de correction
import random, time
from functools import lru_cache
random.seed(1)
populaires = list(range(500))
requetes = [random.choice(populaires) if random.random() < 0.8 else random.randint(500, 49999) for _ in range(2000)]
def calculer_stats(i):
time.sleep(0.0005) # simule 0,5 ms (réduit pour que l'exercice reste court)
return i * 2
def executer(f):
t = time.perf_counter()
for r in requetes:
f(r)
return time.perf_counter() - t
print("sans cache :", round(executer(calculer_stats), 2), "s")
for taille in (100, 500, 5000):
cache = lru_cache(maxsize=taille)(calculer_stats)
print(taille, round(executer(cache), 2), "s", cache.cache_info().hits, "succès")
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. La complexité en espace mesure :
- A. la mémoire supplémentaire utilisée
- B. le temps d'exécution
- C. le nombre de lignes
2. Un générateur permet de :
- A. trier plus vite
- B. produire des valeurs une à une sans tout stocker
- C. accéder par indice
3. Un cache sans limite risque de :
- A. ralentir le processeur
- B. effacer les données
- C. consommer toute la mémoire
4. 🔁 Révision mission 06 : Le tri fusion utilise une mémoire supplémentaire de :
- A. O(n)
- B. O(1)
- C. O(n²)
5. 🔁 Révision mission 05 : x in ensemble coûte en moyenne :
- A. O(n)
- B. O(1)
- C. O(n²)
✅ Réponses
- A.
- B.
- C.
- A.
- B.
🪞 Je réfléchis (10 XP)
- Dans ta vie, où as-tu « précalculé » quelque chose pour gagner du temps plus tard ?
- Quel serait un bon critère pour décider qu'un cache vaut la mémoire qu'il coûte ?
🎒 À retenir
- Complexité en espace = mémoire supplémentaire selon n.
- Le temps et la mémoire s'échangent souvent.
- Flux et générateurs économisent la mémoire.
- Un cache doit être borné.
- On mesure avant d'optimiser.
flowchart LR
T(["Espace mémoire et compromis…"])
T --> R1["1. Complexité en espace = mémoire supplémentaire selon n."]
T --> R2["2. Le temps et la mémoire s'échangent souvent."]
T --> R3["3. Flux et générateurs économisent la mémoire."]
T --> R4["4. Un cache doit être borné."]
T --> R5["5. On mesure avant d'optimiser."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Équilibriste
← Mission 06 — Recherche et tri : le grand écart · Mission 08 — Mesurer pour de vrai →
HEF-030 — Complexité

