06 — Choisir la bonne structure de données
Ce que tu vas apprendre
- La méthode en deux questions pour choisir une structure
- Un arbre de décision concret selon ton besoin
- Trois cas réels résolus du début à la fin
- Comment cette série te change la façon d'écrire du code
Prérequis
On a vu les complexités, la façon de les calculer, le coût de chaque structure et les pièges qui font basculer en quadratique. Reste la décision pratique : face à un problème, laquelle choisir ? Cet article donne une méthode et l'applique à des cas concrets.
La méthode en deux questions
Avant de choisir une structure, réponds à deux questions sur ton code.
Question 1 : quelle est l'opération chaude ? C'est l'opération que ton code exécute le plus souvent, typiquement à l'intérieur d'une boucle ou à chaque requête. Cherches-tu sans cesse des valeurs ? Lis-tu par position ? Ajoutes-tu en fin ? As-tu besoin des éléments dans l'ordre ? Cette opération chaude doit être en O(1) ou O(log n), jamais en O(n) si elle tourne dans une boucle.
Question 2 : qu'es-tu prêt à sacrifier ? Aucune structure n'est rapide partout. Si tu veux la recherche en O(1) avec une hashmap, tu perds l'ordre et l'accès par index. Si tu veux l'accès par index avec un tableau, tu perds la recherche rapide par valeur. Identifie ce qui ne te sert pas, c'est ce que tu peux abandonner.
L'arbre de décision
À partir de ces deux questions, le choix se ramène à quelques cas.
- J'accède par position (index 5, dernier élément) et j'ajoute surtout en fin → tableau (
Array/list). Accès O(1), ajout en fin O(1) amorti. - Je teste souvent la présence d'une valeur, sans valeur associée →
Set. Présence en O(1). - J'associe des clés à des valeurs et je les retrouve par clé → hashmap (
Map/dict). Lecture, écriture, suppression en O(1). - J'ai besoin que les éléments restent triés tout en cherchant vite → structure triée / arbre équilibré (souvent via une bibliothèque ou l'index d'une base). O(log n) avec ordre.
- J'ajoute et retire surtout aux extrémités (file, pile) → file ou pile, implémentée sur tableau ou liste chaînée selon le langage.
Dans la grande majorité du code applicatif, le bon choix est l'un des trois premiers : tableau, Set ou Map. Les connaître par cœur résout déjà la plupart des problèmes de performance qu'on rencontre.
Cas 1 : détecter les doublons d'identifiants
Le besoin : on reçoit une liste de commandes et on veut signaler les identifiants en double.
L'opération chaude est « ai-je déjà vu cet identifiant ? », un test de présence répété. La réponse de l'arbre de décision est immédiate : un Set.
pythondef trouver_doublons(commandes: list[dict]) -> set[str]:
vus = set()
doublons = set()
for c in commandes:
ident = c["id"]
if ident in vus: # O(1)
doublons.add(ident)
vus.add(ident) # O(1)
return doublons
Une seule passe, chaque test en O(1), donc O(n) au total. La version naïve avec un in sur une liste aurait été O(n²) — exactement mon bug d'il y a trois ans.
Cas 2 : enrichir une liste avec des données liées
Le besoin : on a une liste de commandes, chacune avec un clientId, et une liste de clients. On veut attacher le nom du client à chaque commande.
L'opération chaude est « retrouver le client correspondant à cet id », exécutée une fois par commande. Une recherche par clé : c'est une Map.
typescriptfunction enrichir(commandes: Commande[], clients: Client[]): CommandeEnrichie[] {
const parId = new Map(clients.map((c) => [c.id, c])); // O(n), une fois
return commandes.map((cmd) => ({
...cmd,
nomClient: parId.get(cmd.clientId)?.nom ?? "inconnu", // O(1)
}));
}
On construit l'index une fois en O(n), puis chaque jointure est O(1). Total O(n). La version avec un find dans le map aurait été O(n²), le piège de l'article 05.
Cas 3 : afficher un classement par score
Le besoin : afficher les joueurs triés par score décroissant, et permettre d'accéder au joueur de rang 3.
Ici l'opération chaude n'est pas la recherche, mais l'accès par position dans un ordre. Le bon choix est un tableau, trié une fois.
typescriptconst classement = [...joueurs].sort((a, b) => b.score - a.score); // O(n log n)
classement[2]; // le 3ᵉ joueur : O(1)
Le tri coûte O(n log n) une seule fois, et l'accès par rang devient ensuite O(1). Une hashmap aurait été inutile ici : elle ne maintient pas d'ordre et ne permet pas l'accès par rang. C'est l'illustration que la « meilleure » structure dépend entièrement de l'opération chaude. Pour un test de présence, le Set gagnait ; pour un accès ordonné par position, c'est le tableau.
Ce que cette série change pour toi
Tu n'écriras pas du code radicalement différent demain. La plupart du temps, un tableau fait l'affaire et la complexité ne se voit pas. Ce qui change, c'est le moment où ça compte : quand une opération tourne des milliers de fois, quand les volumes peuvent être multipliés par dix, quand une page ralentit sans raison apparente.
Désormais, en relisant une fonction, tu te poseras la question du coût avant que la production ne te la pose. Tu repéreras un includes dans une boucle et tu sauras le remplacer par un Set. Tu choisiras une Map plutôt qu'un find imbriqué. Tu sauras qu'une recherche dans un grand tableau est O(n) et qu'il existe presque toujours une structure qui la rend O(1).
La complexité algorithmique n'est pas une matière d'examen. C'est l'outil qui te permet d'écrire du code qui tiendra l'année prochaine, quand les données auront grossi et que personne ne se souviendra de cette fonction. Rembourser la dette au moment de l'écriture coûte une minute de réflexion. La rembourser sous incident coûte un week-end.
Sources
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Chapitre 3 "Data Structures". Springer.
- Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Partie III "Data Structures". MIT Press.
- Wengrow, J. (2020). A Common-Sense Guide to Data Structures and Algorithms (2nd ed.). Pragmatic Bookshelf.
- Winters, T., et al. (2020). Software Engineering at Google, Chapitre 9 "Code Review". O'Reilly. (sur la détection des problèmes en revue)