Accueil › Python › Choisir sa structure, et ce que chaque opération coûte
Choisir sa structure, et ce que chaque opération coûte
Listes, dictionnaires et ensemblesdebutant
Quatre structures, quatre questions. Le bon réflexe n'est pas de se demander « laquelle est la plus rapide ? », mais quelle question le code pose le plus souvent.
| Question posée | Structure | Écriture |
|---|---|---|
| « Quel est le n-ième ? », « dans quel ordre ? » | list |
[1, 2, 3] |
| « Quels sont les champs de cette chose ? » | tuple |
("Lyon", 40) |
| « Quelle valeur pour cette clé ? » | dict |
{"CAFE-001": 40} |
| « Est-ce dedans ? », « sans doublon » | set |
{"A", "B"} |
Et les coûts, qui tranchent les cas limites :
| Opération | list |
tuple |
dict |
set |
|---|---|---|---|---|
| Accès par index / par clé | O(1) | O(1) | O(1) moy. | — |
x in collection |
O(n) | O(n) | O(1) moy. | O(1) moy. |
| Ajout | O(1) amorti | — | O(1) moy. | O(1) moy. |
| Ajout / retrait au début | O(n) | — | — | — |
| Suppression par valeur | O(n) | — | O(1) moy. | O(1) moy. |
| Ordre conservé | oui | oui | oui (insertion) | non |
| Doublons | oui | oui | clés uniques | non |
| Mutable | oui | non | oui | oui |
| Hachable (clé possible) | non | oui | non | frozenset |
Deux lignes de ce tableau expliquent la majorité des programmes Python lents : le in sur une liste à l'intérieur d'une boucle, et le pop(0) répété. Les deux se corrigent en changeant de structure, pas en optimisant le code.
Les termes à connaître
- Coût d'une opération
Le nombre d'étapes qu'une opération demande en fonction de la taille
nde la collection. On l'écrit en notation O : O(1) ne dépend pas de la taille, O(n) y est proportionnel, O(n log n) est le coût d'un tri.- O(1) amorti
Le coût de
list.append: presque toujours immédiat, sauf quand le tableau interne est plein et doit être réalloué. Comme la réallocation est rare et agrandit généreusement, le coût moyen reste constant.- Choix par question posée
La bonne méthode : partir de la question la plus fréquente du code. « Quel est le n-ième ? » → liste. « Quelle valeur pour cette clé ? » → dictionnaire. « Est-il dedans ? » → ensemble. « Les champs d'une même chose ? » → tuple.
- collections.deque
Une file à double extrémité :
appendleftetpoplefty coûtent O(1), contre O(n) pourlist.insert(0, x)etlist.pop(0). À utiliser dès qu'on travaille par le début d'une séquence.- Égalité entre types
Une liste n'est jamais égale à un tuple, même avec le même contenu :
[1, 2] == (1, 2)vautFalse. Les ensembles et les dictionnaires, en revanche, ignorent l'ordre dans leur comparaison.- Hachabilité
La contrainte qui décide de ce qu'on peut mettre en clé de dictionnaire ou en élément d'ensemble. Mutable (
list,dict,set) → non hachable ; immuable (str,int,tuple,frozenset) → hachable.- timeit
Le module de la bibliothèque standard qui mesure un temps d'exécution en le répétant. C'est la seule façon honnête de comparer deux structures : les ordres de grandeur guident le choix, la mesure le tranche.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.