#Structures de données
Prérequis conseillés: bases de Python (boucles, fonctions, classes) et les notations de complexité du module Algorithmique 1 (grand O, pire cas, coût amorti).
Objectifs du module:
- Choisir une structure selon les opérations dominantes du programme, pas par habitude.
- Énoncer pour chaque structure l'invariant qui garantit sa correction.
- Justifier les coûts asymptotiques de ses opérations (moyenne et pire cas).
- Reconnaître les pièges d'implémentation qui coûtent un facteur 10 en pratique.
#Le choix se décide par les opérations
On ne « collectionne » pas des structures pour elles-mêmes. Une structure de données est un contrat: elle rend certaines opérations bon marché et en paie le prix sur d'autres. Avant de choisir, comptez ce que fait réellement votre programme. Lit-on par index? Insère-t-on en tête? Exige-t-on un ordre trié? Cherche-t-on par clé?
| Structure | Accès indexé | Recherche | Insertion/suppression | Ordre |
|---|---|---|---|---|
| Tableau dynamique | O(1) | O(n) | O(n) au milieu, O(1) amorti en fin | non |
| Liste chaînée | O(n) | O(n) | O(1) si position connue | non |
| Pile / file | sommets seulement | O(n) | O(1) aux extrémités | LIFO / FIFO |
| Table de hachage | par clé: O(1) moyen | O(1) moyen, O(n) pire cas | O(1) amorti moyen | non |
| BST équilibré | O(log n) par position triée | O(log n) | O(log n) | oui, parcours trié |
| Tas binaire | minimum O(1) | O(n) | O(log n) | ordre partiel |
Aucune ligne de ce tableau n'est magique: chacune découle d'un invariant de représentation que les chapitres détaillent.
#Deux familles: séquentiel et hiérarchique
Le tableau dynamique est une rangée de cases contiguës: on saute directement à la case 42 (accès indexé O(1)), mais insérer au milieu décale ceux de droite (O(n)). La liste chaînée est un sentier balisé: chaque maillon connaît le suivant. Glisser un maillon entre deux existants est immédiat si on est déjà au bon endroit (insertion locale O(1)), mais atteindre le 42ᵉ maillon impose 36 sauts de pointeurs (O(n)), et ces sauts gaspillent le cache mémoire.
Plus haut, les arbres imposent un ordre et maintiennent les opérations en O(log n) lorsqu'ils sont équilibrés. Les arbres équilibrés servent d'ensembles et dictionnaires triés. Les tas répondent à une seule question, « quel est le plus petit tout de suite ? », et suffisent pour les files de priorité (ordonnancement, Dijkstra). Les tables de hachage offrent un accès clé/valeur en O(1) amorti en moyenne, au prix de l'absence d'ordre.
#Décider, puis vérifier
Trois réflexes pour trancher:
- Optimiser le chemin critique: la structure qui sert l'opération la plus fréquente, au détriment des opérations rares.
- Se méfier des dogmes: un tableau simple bat souvent une liste chaînée en pratique grâce à la localité mémoire, même quand les gros O se ressemblent.
- Choisir la mutabilité selon le contexte: les structures persistantes facilitent l'historique et le partage, les structures mutables évitent les allocations dans les boucles chaudes.
#Mise en pratique: top-K
Écrivez une fonction qui maintient les K plus grands éléments vus jusqu'ici dans un flux de valeurs.
- Version naïve: un tableau trié de taille K, réinséré à chaque nouvelle valeur. Coût par élément: O(K) pour la recherche de position et le décalage.
- Version tas: un min-tas de taille K. Chaque nouvel élément est comparé au minimum du tas en O(1); s'il est plus grand, on remplace le minimum en O(log K).
Vérification: appliquez les deux versions au flux [3, 1, 9, 2, 7, 8, 5] avec K = 3. Les deux doivent répondre [7, 8, 9]. La version tas ne diffère pas par le résultat (les deux sont correctes) mais par le coût: comptez les comparaisons pour K = 3 puis K = 1000 sur un flux de dix mille valeurs tirées au hasard. Le rapport doit croître à peu près comme K / log K.