La vraie compétence : choisir la bonne structure, expliquer pourquoi, et prouver qu'elle tient ses promesses.
⏱️ Durée : environ 80 minutes · 🎓 Niveau : débutant · 🏅 Badge : Ingénieur·e des données
🎬 L'histoire
Dernière mission du module. Maya donne à Kodi trois besoins, et lui demande de choisir la bonne structure pour chacun, avec des preuves :
- un historique des 1 000 dernières actions ;
- une recherche de membres par préfixe de nom (« Mar… ») ;
- un classement en temps réel des 10 meilleurs scores.
« Pas d'intuition seule, dit Sam. Les opérations, les coûts, les invariants. »
Tu rassembles tout le module dans une démarche de choix.
🎯 Ta mission
À la fin, je serai capable de :
- lister les opérations et leur fréquence pour un besoin
- comparer plusieurs structures sur des critères précis
- énoncer l'invariant d'une structure
- écrire des tests de propriétés pour une structure
- justifier un choix par un compromis
🧩 Défi d'échauffement (5 XP)
Tu dois stocker les 100 000 produits d'une boutique. Écris trois opérations que tu feras (rechercher par nom, lister par prix, ajouter…). Pour chacune, quelle structure du module te vient en tête ? Une seule structure suffit-elle ?
💡 Le concept
La démarche en 5 étapes
- Opérations : quelles actions, avec quelle fréquence ?
- Contraintes : taille des données, ordre, doublons, mémoire.
- Candidates : 2 ou 3 structures plausibles.
- Comparaison : coût des opérations clés, simplicité, mémoire.
- Preuve : invariant et tests.
Tableau de synthèse
| Structure | Lire par position | Chercher une valeur | Ajouter | Retirer | Ordre ? |
|---|---|---|---|---|---|
Tableau (list) | rapide | lent | fin : rapide | milieu : lent | oui |
| Liste chaînée | lent | lent | début : rapide | rapide si position connue | oui |
| Pile / file | : | : | rapide | rapide (une extrémité) | LIFO / FIFO |
| Dictionnaire / ensemble | : | rapide | rapide | rapide | non garanti |
Les invariants
Un invariant de structure est une propriété qui doit toujours être vraie :
| Structure | Invariant |
|---|---|
| Pile | on retire toujours le dernier ajouté |
| BST | gauche < nœud < droite |
| Tas-min | parent ≤ enfants |
| Ensemble | pas de doublons |
Pour le vérifier, on écrit une fonction verifier_invariant() et on l'appelle dans les tests, après chaque opération.
Les tests de propriétés
Au lieu d'exemples fixes, on teste des propriétés sur beaucoup d'entrées aléatoires :
- insérer puis retirer tous les éléments d'un tas donne une liste triée ;
- le parcours en ordre d'un BST est trié ;
- une pile rend les éléments dans l'ordre inverse de leur entrée.
import heapq, random
for _ in range(300):
donnees = [random.randint(-100, 100) for _ in range(random.randint(0, 20))]
tas = []
for x in donnees:
heapq.heappush(tas, x)
sortie = [heapq.heappop(tas) for _ in range(len(tas))]
assert sortie == sorted(donnees)
print("propriété du tas vérifiée")
🧠 Astuce : combiner deux structures est courant. Un dictionnaire + une liste ou un tas résout souvent des besoins qu'une seule ne couvre pas.
🔍 Exemple pas à pas
Besoin 1 : historique des 1 000 dernières actions.
Opérations : ajouter (très fréquent), lire toutes les actions (rare). Taille bornée.
Candidat : deque(maxlen=1000) : l'ajout supprime automatiquement la plus ancienne.
Besoin 2 : recherche par préfixe.
Opérations : trouver tous les noms commençant par « Mar ». Candidats : liste triée + recherche binaire sur le préfixe, ou BST. Le choix : liste triée et bisect.
import bisect
noms = sorted(["Marie", "Marc", "Maya", "Omar", "Sara", "Marion"])
def par_prefixe(noms_tries, prefixe):
debut = bisect.bisect_left(noms_tries, prefixe)
fin = bisect.bisect_left(noms_tries, prefixe + "\uffff")
return noms_tries[debut:fin]
print(par_prefixe(noms, "Mar")) # ['Marc', 'Marie', 'Marion']
Besoin 3 : classement des 10 meilleurs.
Opération : un nouveau score arrive ; on veut toujours les 10 meilleurs. Candidat : tas-min de taille 10 (mission 07).
Tableau de décision :
| Besoin | Structure | Raison |
|---|---|---|
| Historique | deque(maxlen=1000) | ajout rapide, taille bornée automatiquement |
| Préfixe | liste triée + bisect | recherche binaire, résultat contigu |
| Top 10 | tas-min de taille 10 | seul le minimum du tas compte |
✍️ À toi, avec aide (10 XP)
Pour chaque besoin, remplis : opérations, structure, raison.
- Vérifier si un e-mail est déjà inscrit (100 000 e-mails, ajouts fréquents).
- Annuler les dernières actions d'un éditeur.
- Servir les demandes dans l'ordre d'arrivée.
- Trouver le plus court trajet entre deux stations de métro.
💡 Indice 1
Pour 1, pense à « est-il présent ? » rapide.
💡 Indice 2
Pour 2 et 3, pense à LIFO et FIFO.
💡 Indice 3
Pour 4, c'est un problème de relations avec distance en nombre d'arrêts.
✅ Réponse
- Présence rapide, ajouts → ensemble (ou dictionnaire).
- Dernier ajouté, premier annulé → pile.
- Premier arrivé, premier servi → file (
deque). - Stations reliées → graphe (liste d'adjacence) + BFS.
🚀 À toi, en solo (20 XP)
Écris une classe Classement qui garde les N meilleurs scores avec le nom du joueur.
ajouter(nom, score);top()renvoie la liste[(nom, score), …]du meilleur au moins bon ;- un score d'un joueur existant n'est retenu que s'il améliore le sien.
Ajoute verifier_invariant() (au plus N entrées, pas de doublon de joueur) et un test de propriétés sur 300 séquences aléatoires comparées à une version naïve.
✅ Pistes de correction
import random
class Classement:
def __init__(self, n):
self.n = n
self._scores = {}
def ajouter(self, nom, score):
if nom not in self._scores or score > self._scores[nom]:
self._scores[nom] = score
if len(self._scores) > self.n:
pire = min(self._scores, key=lambda k: (self._scores[k], k))
del self._scores[pire]
def top(self):
return sorted(self._scores.items(), key=lambda x: (-x[1], x[0]))
def verifier_invariant(self):
assert len(self._scores) <= self.n
():
meilleur = {}
nom, s evenements:
meilleur[nom] = (meilleur.get(nom, s), s)
(meilleur.items(), key= x: (-x[], x[]))[:n]
_ ():
evs = [(random.choice(), random.randint(, )) _ (random.randint(, ))]
c = Classement()
e evs:
c.ajouter(*e)
c.verifier_invariant()
attendu = naif(, evs)
[s _, s c.top()] == [s _, s attendu]
()
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Choisir par habitude | Toujours une liste, même quand c'est lent | Lister d'abord les opérations |
| Optimiser trop tôt | Complexité inutile pour 50 éléments | Mesurer avant de complexifier |
| Oublier l'invariant | Bug silencieux | Écrire verifier_invariant() et l'appeler dans les tests |
| Une seule structure à tout faire | Compromis forcé | Combiner (dictionnaire + tas, etc.) |
🐉 Mini-boss (60 XP)
Projet final du module — dossier de choix. Pour chacun des cinq besoins ci-dessous, produis une fiche d'une demi-page :
- file d'attente d'un support client (priorité aux clients premium) ;
- correcteur orthographique (« ce mot existe-t-il ? ») ;
- suggestion « membres que tu pourrais connaître » ;
- historique de navigation avec retour arrière ;
- agenda où l'on cherche les rendez-vous entre deux dates.
Chaque fiche : opérations et fréquence, structure choisie et alternative écartée, invariant, coût attendu, un petit code de démonstration avec test.
✅ Pistes de correction
Pistes : (1) tas avec compteur d'arrivée ; (2) ensemble de mots ; (3) graphe + amis d'amis (BFS à distance 2) ; (4) deux piles (arrière/avant) ; (5) liste triée par date + bisect, ou BST. Une bonne fiche justifie le choix par les opérations les plus fréquentes et nomme honnêtement ce qu'on perd.
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Pour choisir une structure, on commence par :
- A. lister les opérations et leur fréquence
- B. choisir la plus récente
- C. utiliser une liste
2. Un invariant de structure est :
- A. un commentaire
- B. une propriété toujours vraie
- C. un test unique
3. Un test de propriété :
- A. vérifie un seul exemple
- B. remplace le code
- C. vérifie une règle sur beaucoup d'entrées aléatoires
4. 🔁 Révision mission 09 : BFS trouve dans un graphe non pondéré :
- A. le plus court chemin en nombre d'arêtes
- B. le chemin le plus long
- C. un chemin au hasard
5. 🔁 Révision mission 04 : Une table de hachage associe :
- A. des nœuds à des feuilles
- B. des clés à des valeurs
- C. des listes à des tris
✅ Réponses
- A.
- B.
- C.
- A.
- B.
🪞 Je réfléchis (10 XP)
- Quel besoin réel de ta vie professionnelle ou scolaire pourrait être traité avec les structures du module ?
- Quelle structure te semblait étrangère au début et te paraît maintenant évidente ?
🎒 À retenir
- On choisit une structure à partir des opérations et de leur fréquence.
- Comparer sur coûts, mémoire, simplicité.
- L'invariant dit ce qui doit toujours être vrai.
- Les tests de propriétés couvrent beaucoup de cas.
- Combiner des structures est normal.
flowchart LR
T(["Choisir, prouver, comparer"])
T --> R1["1. On choisit une structure à partir des opérations et de leur fréquence."]
T --> R2["2. Comparer sur coûts, mémoire, simplicité."]
T --> R3["3. L'invariant dit ce qui doit toujours être vrai."]
T --> R4["4. Les tests de propriétés couvrent beaucoup de cas."]
T --> R5["5. Combiner des structures est normal."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 120 XP · 🏅 Badge Ingénieur·e des données
← Mission 09 — Explorer un graphe : DFS et BFS
🎉 Félicitations
Tu as terminé HEF-020 — Structures de données. Tu sais décrire une structure par ses opérations, en implémenter les principales, choisir la bonne selon l'usage, et prouver qu'elle tient ses promesses.
→ Prochain module : HEF-030 — Complexité
HEF-020 — Structures de données

