Structures de données avancées

Au-delà des boucles

Vous savez déjà comment fonctionnent les listes, les dictionnaires et les boucles en Python. C'est le moment de passer à la vitesse supérieure. Il ne s'agit plus seulement de faire fonctionner le code, mais de l'écrire de manière plus élégante, lisible et surtout, plus performante. Nous allons explorer des techniques qui distinguent un code fonctionnel d'un code Pythonique.

L'art de la compréhension

Les compréhensions sont une des caractéristiques les plus appréciées de Python. Elles permettent de créer des listes ou des dictionnaires de manière concise et lisible, en se basant sur une séquence existante. C'est une façon de penser plus déclarative : au lieu de dire comment construire la liste étape par étape, vous décrivez ce que la liste doit contenir.

Imaginez que vous voulez une liste contenant les carrés des dix premiers entiers. La méthode classique utilise une boucle :

squares = []
for x in range(10):
    squares.append(x**2)

# squares -> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Avec une compréhension de liste, vous obtenez le même résultat en une seule ligne expressive :

squares = [x**2 for x in range(10)]

# squares -> [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

La même logique s'applique aux dictionnaires. Pour créer un dictionnaire associant chaque nombre à son carré :

square_map = {x: x**2 for x in range(10)}

Mais que se passe-t-il si vous manipulez des millions d'éléments ? Créer une liste entière en mémoire peut être inefficace. C'est là qu'interviennent les expressions génératrices. Elles ressemblent aux compréhensions de listes, mais utilisent des parenthèses au lieu de crochets. Elles ne construisent pas la liste complète, mais créent un objet itérateur qui génère les valeurs une par une, à la demande. C'est un exemple d' (lazy evaluation), une technique extrêmement puissante pour économiser la mémoire.

# Ceci crée une liste complète en mémoire
list_comp = [x**2 for x in range(10_000_000)]

# Ceci crée un objet générateur, n'utilisant presque pas de mémoire
gen_exp = (x**2 for x in range(10_000_000))

# On peut ensuite itérer sur le générateur
# sum(gen_exp) est beaucoup plus efficace en mémoire que sum(list_comp)

La boîte à outils `collections`

Le module de Python est une mine d'or. Il fournit des types de données conteneurs spécialisés qui sont des alternatives aux conteneurs de base comme dict, list, set, et tuple. Explorons quelques-uns des plus utiles.

namedtuple

noun

Une fonction de fabrique pour créer des sous-classes de tuples avec des noms de champs. Elles permettent un code plus lisible et auto-documenté.

Au lieu d'accéder aux éléments d'un tuple par leur index, comme data[0], un namedtuple vous permet d'utiliser des noms, comme data.x. C'est un excellent compromis entre la légèreté d'un tuple et la lisibilité d'un objet.

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p1 = Point(11, y=22)

print(p1.x + p1.y)  # Accès par nom, beaucoup plus clair
print(p1[0] + p1[1])  # L'accès par index fonctionne toujours

Un autre outil puissant est le defaultdict. Il se comporte comme un dictionnaire normal, à une exception près : si vous essayez d'accéder à une clé qui n'existe pas, il la crée avec une valeur par défaut, au lieu de lever une KeyError. C'est incroyablement utile pour regrouper ou compter des éléments.

from collections import defaultdict

# Compter les occurrences de chaque mot dans une phrase
sentence = "le chat est sur le tapis"
word_counts = defaultdict(int)  # La valeur par défaut pour une nouvelle clé sera int(), soit 0

for word in sentence.split():
    word_counts[word] += 1

# word_counts['le'] -> 2
# word_counts['chat'] -> 1
# word_counts['chien'] -> 0 (la clé est créée à la volée)

Enfin, Counter est un sous-classe de dictionnaire spécialisée dans le comptage d'objets hachables. C'est une version encore plus directe et puissante de l'exemple précédent.

from collections import Counter

sentence = "le chat est sur le tapis"
word_counts = Counter(sentence.split())

print(word_counts)
# Counter({'le': 2, 'chat': 1, 'est': 1, 'sur': 1, 'tapis': 1})

# Il possède des méthodes utiles
print(word_counts.most_common(2)) # -> [('le', 2), ('chat', 1)]

Complexité et performance

Choisir la bonne structure de données n'est pas qu'une question de commodité. C'est une décision cruciale pour la performance, surtout lorsque les données deviennent volumineuses. L'efficacité des opérations comme l'ajout, la suppression ou la recherche d'un élément est mesurée par la (Grand O).

Sans entrer dans une analyse mathématique formelle, voici ce qu'il faut retenir pour les structures de base en Python :

Opération	Liste (list)	Ensemble (set)	Dictionnaire (dict)
Accès (par index/clé)	$O(1)$	Non applicable	$O(1)$ en moyenne
Recherche (valeur)	$O(n)$	$O(1)$ en moyenne	$O(1)$ en moyenne (pour les clés)
Insertion/Suppression (à la fin)	$O(1)$	$O(1)$ en moyenne	$O(1)$ en moyenne
Insertion/Suppression (au début)	$O(n)$	$O(1)$ en moyenne	$O(1)$ en moyenne

Qu'est-ce que cela signifie en pratique ?

Rechercher un élément dans une longue liste est lent. Python doit potentiellement parcourir chaque élément ( $O(n)$ ).
Rechercher une clé dans un dictionnaire ou un élément dans un ensemble est extrêmement rapide, peu importe leur taille ( $O(1)$ ). C'est leur super-pouvoir, grâce à l'utilisation interne de tables de hachage.
Ajouter ou retirer un élément au début d'une liste est coûteux. Tous les autres éléments doivent être décalés ( $O(n)$ ). Pour ce cas, collections.deque est la solution, avec des opérations en $O(1)$ aux deux extrémités.

Le choix est donc un arbitrage. Si vous avez besoin de maintenir un ordre et d'accéder par index, une liste est parfaite. Si vous devez vérifier fréquemment et rapidement la présence d'un élément, un ensemble ou un dictionnaire est imbattable.

Quiz Questions 1/5

Quelle est la principale différence entre une compréhension de liste [i for i in range(1000000)] et une expression génératrice (i for i in range(1000000)) en Python ?

Quiz Questions 2/5

Pour compter les occurrences de chaque mot dans une longue liste de mots, quel outil du module collections serait le plus direct et le plus efficace ?

Maîtriser ces concepts vous permet d'écrire un code non seulement plus propre, mais aussi beaucoup plus performant.

Maîtrise de la Programmation Python