Formations — 1 037 leçons en français

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 n de 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é : appendleft et popleft y coûtent O(1), contre O(n) pour list.insert(0, x) et list.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) vaut False. 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.

Lire l'explication détaillée et faire le quiz →

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.