--- jupytext: text_representation: extension: .md format_name: myst format_version: 0.13 jupytext_version: 1.16.0 kernelspec: name: python3 display_name: Python 3 --- # Structures de données natives ```{code-cell} python :tags: [hide-input] import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np import seaborn as sns sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1) ``` ## Les listes (`list`) La **liste** est la structure de données la plus polyvalente de Python. C'est une séquence **ordonnée**, **mutable** et **hétérogène** : elle peut contenir des éléments de types différents, dans n'importe quel ordre, et son contenu peut être modifié après sa création. Sous le capot, Python implémente les listes comme des **tableaux dynamiques** (*dynamic arrays*) : une zone de mémoire contiguë qui se redimensionne automatiquement lorsque nécessaire. ```{code-cell} python # Création d'une liste vide = [] nombres = [1, 2, 3, 4, 5] hétérogène = [42, "bonjour", 3.14, True, None] imbriquée = [[1, 2], [3, 4], [5, 6]] # Liste de listes print(type(nombres)) print(len(nombres)) ``` ### Indexation et slicing ```{code-cell} python fruits = ["pomme", "banane", "cerise", "datte", "figue"] # Accès par indice (négatifs depuis la fin) print(fruits[0]) # Premier print(fruits[-1]) # Dernier print(fruits[-2]) # Avant-dernier # Slicing : [début:fin:pas] print(fruits[1:3]) # ["banane", "cerise"] print(fruits[::-1]) # Inversion complète print(fruits[::2]) # Un sur deux # Modification par indice ou slice fruits[0] = "abricot" fruits[1:3] = ["citron", "mangue", "kiwi"] # Peut changer la longueur ! print(fruits) ``` ### Méthodes essentielles ```{code-cell} python ma_liste = [3, 1, 4, 1, 5, 9, 2, 6] # Ajout ma_liste.append(5) # Ajoute à la fin — O(1) amorti ma_liste.insert(2, 99) # Insère à l'indice 2 — O(n) ma_liste.extend([7, 8, 9]) # Ajoute tous les éléments — O(k) print(ma_liste) # Suppression ma_liste.remove(99) # Supprime la première occurrence de 99 — O(n) élément = ma_liste.pop() # Retire et retourne le dernier — O(1) élément2 = ma_liste.pop(0) # Retire et retourne l'indice 0 — O(n) print(f"Retiré en fin : {élément}, en début : {élément2}") print(ma_liste) ``` ```{code-cell} python # Tri nombres = [5, 2, 8, 1, 9, 3] nombres.sort() # Tri en place — O(n log n) print(nombres) nombres.sort(reverse=True) # Tri décroissant print(nombres) # sorted() retourne une nouvelle liste (n'affecte pas l'original) original = [5, 2, 8, 1] trié = sorted(original, key=lambda x: -x) print(original) # Inchangé print(trié) # Autres méthodes print([1, 2, 3].count(2)) # Nombre d'occurrences print([1, 2, 3, 2].index(2)) # Indice de la première occurrence ``` ### Complexité des opérations ```{prf:remark} :label: remark-05-01 La complexité algorithmique des opérations sur les listes Python est déterminée par leur implémentation en tableau dynamique. Les opérations en fin de liste (`append`, `pop()`) sont en **O(1) amorti**. Les opérations en début ou au milieu (`insert(0, …)`, `pop(0)`, `remove`) nécessitent de décaler tous les éléments suivants et sont en **O(n)**. Pour des insertions et suppressions fréquentes en tête de liste, la structure `collections.deque` est bien plus adaptée. ``` ### Listes imbriquées ```{code-cell} python # Matrice 3×3 matrice = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] # Accès : matrice[ligne][colonne] print(matrice[1][2]) # 6 # Transposée par compréhension transposée = [[matrice[j][i] for j in range(3)] for i in range(3)] for ligne in transposée: print(ligne) ``` ## Les tuples (`tuple`) Le **tuple** est une séquence **ordonnée** et **immuable**. Une fois créé, son contenu ne peut plus être modifié. Cette immuabilité en fait un outil de choix pour représenter des données qui ne doivent pas changer : coordonnées géographiques, enregistrements de base de données, clés de dictionnaires composites. ```{code-cell} python # Création vide = () singleton = (42,) # La virgule est obligatoire pour un singleton ! point = (3.0, 4.0) coordonnées = (48.8566, 2.3522, "Paris") # Le parenthèsage est optionnel (c'est la virgule qui fait le tuple) triplet = 1, 2, 3 print(type(triplet)) # Immutabilité try: point[0] = 10 except TypeError as e: print(f"TypeError : {e}") ``` ### Déballage (*unpacking*) ```{code-cell} python # Déballage simple x, y = (3.0, 4.0) print(f"x = {x}, y = {y}") # Échange de variables (pythonique, sans variable temporaire) a, b = 10, 20 a, b = b, a print(f"a = {a}, b = {b}") # Déballage avec * (reste) premier, *reste = [1, 2, 3, 4, 5] print(f"premier = {premier}, reste = {reste}") *début, dernier = [1, 2, 3, 4, 5] print(f"début = {début}, dernier = {dernier}") premier, *milieu, dernier = [1, 2, 3, 4, 5] print(f"premier = {premier}, milieu = {milieu}, dernier = {dernier}") ``` ```{code-cell} python # Déballage dans une boucle points = [(1, 2), (3, 4), (5, 6)] for x, y in points: print(f"Distance à l'origine : {(x**2 + y**2)**0.5:.3f}") # Retourner plusieurs valeurs depuis une fonction def divmod_perso(a, b): return a // b, a % b # Retourne un tuple quotient, reste = divmod_perso(17, 5) print(f"17 ÷ 5 = {quotient} reste {reste}") ``` ### Tuples nommés (`collections.namedtuple`) ```{code-cell} python from collections import namedtuple # Définir un type enregistrement (comme une struct légère) Point = namedtuple('Point', ['x', 'y']) Étudiant = namedtuple('Étudiant', ['nom', 'note', 'filière']) p = Point(3.0, 4.0) print(p.x, p.y) print(p[0], p[1]) # Aussi accessible par indice print(f"Distance : {(p.x**2 + p.y**2)**0.5:.3f}") alice = Étudiant("Alice", 18.5, "Informatique") print(alice) print(alice.nom) # Les namedtuples sont immuables comme les tuples ordinaires # Mais on peut créer une version modifiée avec _replace alice_m1 = alice._replace(filière="Mathématiques") print(alice_m1) ``` ## Les dictionnaires (`dict`) Le **dictionnaire** est une structure de données clé-valeur qui repose sur une **table de hachage** (*hash table*). Il permet l'accès, l'insertion et la suppression d'éléments en **O(1)** en moyenne. Depuis Python 3.7, les dictionnaires **préservent l'ordre d'insertion** — une propriété garantie par la spécification du langage. ```{code-cell} python # Création vide = {} vide2 = dict() scores = {"Alice": 95, "Bob": 87, "Charlie": 91} from_tuples = dict([("a", 1), ("b", 2), ("c", 3)]) par_compréhension = {x: x**2 for x in range(5)} print(scores) print(par_compréhension) ``` ### Accès et modification ```{code-cell} python scores = {"Alice": 95, "Bob": 87, "Charlie": 91} # Accès direct (lève KeyError si la clé est absente) print(scores["Alice"]) # Accès sécurisé avec get() print(scores.get("Dave")) # None print(scores.get("Dave", 0)) # 0 (valeur par défaut) # Modification scores["Alice"] = 98 scores["Dave"] = 79 # Insertion del scores["Charlie"] # Suppression print(scores) # Test d'appartenance print("Bob" in scores) print("Charlie" in scores) ``` ### Itération sur un dictionnaire ```{code-cell} python inventaire = {"pomme": 10, "banane": 5, "cerise": 25} # Itérer sur les clés (comportement par défaut) for clé in inventaire: print(clé) # Itérer sur les valeurs for valeur in inventaire.values(): print(valeur) # Itérer sur les paires clé-valeur for clé, valeur in inventaire.items(): print(f"{clé}: {valeur}") # Fusionner deux dictionnaires (Python 3.9+) compléments = {"kiwi": 8, "mangue": 3} total = inventaire | compléments print(total) ``` ### `collections.defaultdict` et `collections.Counter` ```{code-cell} python from collections import defaultdict, Counter # defaultdict : valeur par défaut automatique groupes = defaultdict(list) données = [("A", 1), ("B", 2), ("A", 3), ("B", 4), ("C", 5)] for groupe, valeur in données: groupes[groupe].append(valeur) print(dict(groupes)) # Counter : comptage d'occurrences texte = "abracadabra" occurrences = Counter(texte) print(occurrences) print(occurrences.most_common(3)) mots = "le chat mange le chat noir et le chat".split() fréquences = Counter(mots) print(fréquences.most_common(3)) ``` ## Les ensembles (`set` et `frozenset`) Un **ensemble** est une collection **non ordonnée** d'éléments **uniques**. Comme le dictionnaire, il repose sur une table de hachage, ce qui garantit un test d'appartenance en **O(1)** — un avantage décisif sur les listes pour les grands jeux de données. Les éléments d'un ensemble doivent être **hashables** (immuables). ```{code-cell} python # Création vide = set() # Attention : {} crée un dict vide, pas un set ! consonnes = {'b', 'c', 'd', 'f', 'g'} depuis_liste = set([1, 2, 2, 3, 3, 3, 4]) # Élimine les doublons print(depuis_liste) # Test d'appartenance — O(1) print('b' in consonnes) print('a' in consonnes) ``` ### Opérations ensemblistes ```{code-cell} python A = {1, 2, 3, 4, 5} B = {3, 4, 5, 6, 7} # Union : éléments dans A ou B (ou les deux) print(A | B) print(A.union(B)) # Intersection : éléments dans A et B print(A & B) print(A.intersection(B)) # Différence : éléments dans A mais pas dans B print(A - B) print(A.difference(B)) # Différence symétrique : éléments dans l'un ou l'autre mais pas les deux print(A ^ B) print(A.symmetric_difference(B)) # Tests de sous-ensemble et sur-ensemble print({1, 2} <= A) # Sous-ensemble print(A >= {1, 2}) # Sur-ensemble ``` ```{code-cell} python # Suppression des doublons en préservant l'ordre (astuce) def dédupliquer_ordonné(séquence): vu = set() return [x for x in séquence if not (x in vu or vu.add(x))] données = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] print(dédupliquer_ordonné(données)) ``` ### `frozenset` : ensemble immuable ```{code-cell} python # frozenset : hashable, peut servir de clé de dictionnaire fs = frozenset({1, 2, 3}) print(type(fs)) # Usage : clé de dictionnaire (un set ordinaire ne peut pas) graphe = { frozenset({1, 2}): "arête A-B", frozenset({2, 3}): "arête B-C", } print(graphe[frozenset({1, 2})]) ``` ## Choisir la bonne structure Choisir la bonne structure de données est souvent la décision la plus importante pour la performance et la lisibilité du code. Voici les critères principaux : ```{prf:definition} Hashabilité :label: definition-05-01 Un objet est **hashable** si sa valeur de hachage ne change jamais au cours de sa vie (méthode `__hash__`) et s'il peut être comparé à d'autres objets (méthode `__eq__`). En pratique, les objets **immuables** sont hashables (`int`, `float`, `str`, `tuple`, `frozenset`), tandis que les objets **mutables** ne le sont pas (`list`, `dict`, `set`). La hashabilité est requise pour pouvoir utiliser un objet comme clé de dictionnaire ou comme élément d'un ensemble. ``` | Critère | `list` | `tuple` | `dict` | `set` | |---|---|---|---|---| | Ordonné | Oui | Oui | Oui (3.7+) | Non | | Mutable | Oui | Non | Oui | Oui | | Doublons | Oui | Oui | Clés non | Non | | Hashable | Non | Si éléments hashables | Non | Non | | Accès par indice | O(1) | O(1) | O(1) par clé | Non | | Appartenance | O(n) | O(n) | O(1) | O(1) | ```{prf:example} Choisir la structure adaptée :label: example-05-01 Quelques règles pratiques pour guider le choix : - **`list`** : séquence dont l'ordre importe, avec possibilité de doublons, et qu'on modifie régulièrement. Idéale pour stocker des enregistrements dans un ordre précis. - **`tuple`** : données structurées immuables (coordonnées, enregistrement de base de données), valeur de retour multiple d'une fonction, clé composite de dictionnaire. - **`dict`** : association clé-valeur, accès rapide par clé, accumulation de données par catégorie. C'est la structure à préférer dès qu'on se retrouve à chercher un élément par un identifiant. - **`set`** : élimination des doublons, tests d'appartenance fréquents, opérations ensemblistes. Remplace avantageusement une liste quand l'ordre n'importe pas et qu'on teste souvent `x in ...`. ``` ## `collections` et `array` Le module `collections` de la bibliothèque standard propose des structures de données spécialisées qui complètent les types natifs. ### `deque` : file double d'accès ```{code-cell} python from collections import deque # deque (double-ended queue) : O(1) en tête ET en fin file = deque([1, 2, 3, 4]) file.append(5) # Ajouter à droite — O(1) file.appendleft(0) # Ajouter à gauche — O(1) print(file) file.pop() # Retirer à droite — O(1) file.popleft() # Retirer à gauche — O(1) print(file) # Rotation file = deque(range(5)) file.rotate(2) # Décaler à droite de 2 print(file) file.rotate(-2) # Décaler à gauche de 2 print(file) # Taille maximale (utile pour les files glissantes) fenêtre = deque(maxlen=3) for i in range(6): fenêtre.append(i) print(list(fenêtre)) ``` ### `OrderedDict` ```{code-cell} python from collections import OrderedDict # OrderedDict : garantit l'ordre même avant Python 3.7 # Son intérêt principal aujourd'hui : la méthode move_to_end od = OrderedDict([("a", 1), ("b", 2), ("c", 3)]) od.move_to_end("a") # Déplace "a" à la fin print(od) od.move_to_end("c", last=False) # Déplace "c" au début print(od) ``` ### `ChainMap` ```{code-cell} python from collections import ChainMap # ChainMap : vue unifiée de plusieurs dictionnaires # Idéal pour gérer des configurations par niveaux défauts = {"couleur": "bleu", "taille": "medium", "langue": "fr"} config_utilisateur = {"couleur": "rouge", "taille": "large"} config_session = {"langue": "en"} # Priorité de gauche à droite config = ChainMap(config_session, config_utilisateur, défauts) print(config["couleur"]) # rouge (config_utilisateur) print(config["langue"]) # en (config_session) print(config["taille"]) # large (config_utilisateur) ``` ### `array.array` pour les données numériques homogènes ```{code-cell} python import array # array.array : tableau typé, plus compact qu'une liste de nombres # Code de type : 'd' = double (float 64 bits), 'i' = int 32 bits vecteur = array.array('d', [1.0, 2.5, 3.7, 4.2]) print(vecteur) print(vecteur[0]) # Avantage : consomme beaucoup moins de mémoire qu'une liste import sys liste_int = list(range(10_000)) arr_int = array.array('l', range(10_000)) print(f"liste: {sys.getsizeof(liste_int)} octets") print(f"array: {sys.getsizeof(arr_int)} octets") ``` ```{prf:remark} :label: remark-05-02 Pour les calculs numériques intensifs, ni les listes ni `array.array` ne sont la bonne réponse : **NumPy** offre des tableaux multidimensionnels avec des opérations vectorisées qui s'exécutent en code C compilé, plusieurs ordres de grandeur plus rapides. `array.array` reste utile lorsqu'on veut économiser de la mémoire avec des séquences numériques monodimensionnelles sans dépendre de NumPy. ``` ## Visualisation des complexités algorithmiques ```{code-cell} python :tags: [hide-input] fig, ax = plt.subplots(figsize=(13, 8)) ax.set_xlim(-0.5, 13.5) ax.set_ylim(-0.5, 7.5) ax.axis('off') ax.set_title( "Complexité algorithmique des opérations principales\nsur les structures de données Python", fontsize=13, fontweight='bold', pad=20 ) palette = sns.color_palette("muted", 4) # Couleurs pour O(1), O(log n), O(n), O(n log n) couleur_o1 = "#2ecc71" # Vert : optimal couleur_ologn = "#3498db" # Bleu : bon couleur_on = "#e67e22" # Orange : acceptable couleur_onlogn = "#e74c3c" # Rouge : coûteux def couleur_complexité(c): if c == "O(1)": return couleur_o1 elif c == "O(log n)": return couleur_ologn elif c == "O(n)": return couleur_on else: return couleur_onlogn # En-têtes des colonnes structures = ["list", "tuple", "dict", "set"] en_têtes_x = [2.2, 5.0, 7.8, 10.6] for x, nom in zip(en_têtes_x, structures): ax.text(x, 7.0, nom, ha='center', va='center', fontsize=12, fontweight='bold', color='#333333', fontfamily='monospace', bbox=dict(boxstyle='round,pad=0.3', facecolor='#e8e8e8', edgecolor='#cccccc')) # Opérations (lignes) opérations = [ "Accès par indice / clé", "Recherche (in)", "Insertion en fin", "Insertion en début", "Suppression (milieu)", "Tri", ] # Données : (list, tuple, dict, set) données_complexité = [ ["O(1)", "O(1)", "O(1)", "—"], ["O(n)", "O(n)", "O(1)", "O(1)"], ["O(1)*", "—", "O(1)*", "O(1)*"], ["O(n)", "—", "O(n)", "O(n)"], ["O(n)", "—", "O(n)", "O(n)"], ["O(n log n)", "—", "—", "—"], ] y_positions = [6.0, 5.1, 4.2, 3.3, 2.4, 1.5] for row_idx, (op, y, row) in enumerate( zip(opérations, y_positions, données_complexité)): # Fond alterné fond = '#fafafa' if row_idx % 2 == 0 else '#f0f4f8' bg = patches.FancyBboxPatch((-0.3, y - 0.38), 13.3, 0.76, boxstyle="round,pad=0.05", linewidth=0, edgecolor='none', facecolor=fond) ax.add_patch(bg) # Nom de l'opération ax.text(0.0, y, op, ha='left', va='center', fontsize=8.5, color='#333333') # Cellules de complexité for x, complexité in zip(en_têtes_x, row): if complexité == "—": ax.text(x, y, "—", ha='center', va='center', fontsize=9, color='#bbbbbb') else: c = couleur_complexité(complexité.rstrip('*')) cell = patches.FancyBboxPatch( (x - 1.0, y - 0.3), 2.0, 0.6, boxstyle="round,pad=0.08", linewidth=1.5, edgecolor=c, facecolor=c, alpha=0.25 ) ax.add_patch(cell) cell_brd = patches.FancyBboxPatch( (x - 1.0, y - 0.3), 2.0, 0.6, boxstyle="round,pad=0.08", linewidth=1.5, edgecolor=c, facecolor='none' ) ax.add_patch(cell_brd) ax.text(x, y, complexité, ha='center', va='center', fontsize=8.5, fontweight='bold', color=c, fontfamily='monospace') # Légende légende = [ (couleur_o1, "O(1) : temps constant"), (couleur_ologn, "O(log n) : logarithmique"), (couleur_on, "O(n) : linéaire"), (couleur_onlogn, "O(n log n) : quasi-linéaire"), ] for i, (c, texte) in enumerate(légende): lx = 0.5 + i * 3.2 cell = patches.FancyBboxPatch((lx - 0.1, 0.3), 2.9, 0.5, boxstyle="round,pad=0.05", linewidth=1.5, edgecolor=c, facecolor=c, alpha=0.25) ax.add_patch(cell) cell_brd = patches.FancyBboxPatch((lx - 0.1, 0.3), 2.9, 0.5, boxstyle="round,pad=0.05", linewidth=1.5, edgecolor=c, facecolor='none') ax.add_patch(cell_brd) ax.text(lx + 1.35, 0.55, texte, ha='center', va='center', fontsize=7.5, color=c, fontweight='bold') ax.text(13.2, 0.1, "* = O(1) amorti", ha='right', va='center', fontsize=7, color='#888888', style='italic') plt.tight_layout() plt.show() ``` ## Résumé Dans ce chapitre, nous avons exploré les structures de données natives de Python et leur usage approprié : - Les **listes** (`list`) sont des tableaux dynamiques ordonnés et mutables. Les opérations en fin de liste sont en O(1) amorti ; les opérations en début ou au milieu sont en O(n). Elles s'utilisent quand l'ordre importe et que les doublons sont autorisés. - Les **tuples** (`tuple`) sont des séquences immuables, hashables (si leurs éléments le sont), idéales pour les données structurées fixes. Le déballage (*unpacking*) et l'opérateur `*rest` offrent une syntaxe très expressive. `collections.namedtuple` ajoute un accès par nom sans sacrifier l'immuabilité. - Les **dictionnaires** (`dict`) offrent un accès clé-valeur en O(1) et préservent l'ordre d'insertion depuis Python 3.7. `.get()` évite les `KeyError` ; `.items()` permet d'itérer simultanément sur clés et valeurs. `defaultdict` et `Counter` sont des spécialisations très utiles du module `collections`. - Les **ensembles** (`set`) garantissent l'unicité et le test d'appartenance en O(1). Ils supportent toutes les opérations ensemblistes classiques (`|`, `&`, `-`, `^`). `frozenset` est leur variante immuable et hashable. - Le choix de la structure dépend de critères essentiels : la **mutabilité**, la nécessité d'un **ordre**, la tolérance aux **doublons**, la **hashabilité** et la complexité des **opérations les plus fréquentes**. - Le module `collections` enrichit la bibliothèque standard avec `deque` (insertions/suppressions O(1) aux deux extrémités), `OrderedDict` (avec `move_to_end`), et `ChainMap` (vue multicouche de dictionnaires). `array.array` est une alternative légère et compacte pour les tableaux numériques homogènes. Dans le chapitre suivant, nous aborderons la **programmation orientée objet** en Python : classes, héritage, méthodes spéciales et les protocoles qui sous-tendent les structures de données que nous venons d'explorer.