Itérateurs et générateurs

Itérateurs et générateurs#

Hide code cell source

 
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)

Le protocole itérable#

L’une des idées les plus fondatrices de Python est que la boucle for ne connaît pas les listes — elle connaît les itérables. Un itérable est tout objet capable de livrer ses éléments un par un, dans un ordre défini. Les listes, tuples, chaînes de caractères, dictionnaires, ensembles, fichiers ouverts, et même des objets de vos propres classes peuvent tous être des itérables, dès lors qu’ils implémentent le protocole adéquat.

Ce protocole repose sur deux méthodes spéciales distinctes, ce qui introduit une séparation nette entre deux concepts souvent confondus par les débutants : l”itérable et l”itérateur.

Définition 22 (Itérable et itérateur)

  • Un itérable est un objet qui implémente __iter__(self). Cette méthode doit retourner un itérateur. Les listes, tuples, chaînes, dictionnaires sont tous des itérables.

  • Un itérateur est un objet qui implémente à la fois __iter__(self) (qui retourne self) et __next__(self). La méthode __next__ retourne l’élément suivant, ou lève StopIteration lorsqu’il n’y a plus d’éléments. Un itérateur est toujours un itérable, mais un itérable n’est pas nécessairement un itérateur.

Cette distinction est subtile mais essentielle. Une liste est un itérable : on peut en créer autant d’itérateurs que l’on souhaite, chacun conservant sa propre position de lecture. Un fichier ouvert, lui, est directement un itérateur : il maintient un curseur interne et avance ligne par ligne.

# Une liste est un itérable, pas un itérateur
ma_liste = [10, 20, 30]
print(hasattr(ma_liste, '__iter__'))   # True
print(hasattr(ma_liste, '__next__'))   # False

# iter() crée un itérateur à partir d'un itérable
it = iter(ma_liste)
print(hasattr(it, '__next__'))         # True

# next() avance l'itérateur
print(next(it))   # 10
print(next(it))   # 20
print(next(it))   # 30

try:
    next(it)
except StopIteration:
    print("StopIteration : plus d'éléments")

True
False
True
10
20
30
StopIteration : plus d'éléments

# La boucle for est du sucre syntaxique sur iter() / next()
# Ce code :
for x in [1, 2, 3]:
    print(x)

# Est équivalent à :
it = iter([1, 2, 3])
while True:
    try:
        x = next(it)
        print(x)
    except StopIteration:
        break

1
2
3
1
2
3

La fonction built-in iter() peut aussi accepter un deuxième argument, appelé sentinelle : dans ce cas, le premier argument doit être un callable, et iter() l’appellera répétitivement jusqu’à ce qu’il retourne la valeur sentinelle.

import random

# iter(callable, sentinelle) : appelle callable() jusqu'à obtenir la sentinelle
random.seed(42)
lancers = list(iter(lambda: random.randint(1, 6), 6))   # Lancer jusqu'à obtenir 6
print(f"Lancers avant d'obtenir 6 : {lancers}")

Lancers avant d'obtenir 6 : []

Implémenter un itérateur personnalisé#

Construire ses propres itérateurs permet de créer des séquences de données sophistiquées, paresseuses, et potentiellement infinies. L’implémentation du protocole itérable s’effectue en définissant __iter__ et __next__ dans vos classes.

class CompteARebours:
    """Itérateur qui compte à rebours depuis n jusqu'à 1."""

    def __init__(self, debut: int) -> None:
        if debut < 0:
            raise ValueError("Le point de départ doit être positif")
        self._valeur = debut

    def __iter__(self) -> "CompteARebours":
        return self   # Un itérateur retourne toujours self

    def __next__(self) -> int:
        if self._valeur <= 0:
            raise StopIteration
        valeur = self._valeur
        self._valeur -= 1
        return valeur


for n in CompteARebours(5):
    print(n, end=" ")
print()

# Utilisation avec les fonctions de la bibliothèque standard
print(list(CompteARebours(8)))
print(sum(CompteARebours(10)))

5 4 3 2 1 
[8, 7, 6, 5, 4, 3, 2, 1]
55

Remarque 22

Notez que CompteARebours est à la fois un itérable et un itérateur : il implémente __iter__ (retournant self) et __next__. Cette conception est courante pour les itérateurs simples, mais elle présente une limitation : une fois épuisé, l’objet ne peut pas être réutilisé dans une nouvelle boucle. Pour permettre plusieurs itérations indépendantes, il vaut mieux séparer la classe itérable (qui garde les données) de la classe itérateur (qui garde la position).

class Intervalle:
    """Itérable séparé de son itérateur — permet plusieurs itérations."""

    def __init__(self, debut: int, fin: int, pas: int = 1) -> None:
        self.debut = debut
        self.fin = fin
        self.pas = pas

    def __iter__(self) -> "IntervalleIterateur":
        return IntervalleIterateur(self)


class IntervalleIterateur:
    """Itérateur associé à Intervalle."""

    def __init__(self, intervalle: Intervalle) -> None:
        self._intervalle = intervalle
        self._courant = intervalle.debut

    def __iter__(self) -> "IntervalleIterateur":
        return self

    def __next__(self) -> int:
        if self._courant >= self._intervalle.fin:
            raise StopIteration
        valeur = self._courant
        self._courant += self._intervalle.pas
        return valeur


iv = Intervalle(0, 10, 2)
print("Première itération :", list(iv))
print("Deuxième itération :", list(iv))   # Fonctionne aussi, contrairement à un itérateur simple

Première itération : [0, 2, 4, 6, 8]
Deuxième itération : [0, 2, 4, 6, 8]

Générateurs avec yield#

Implémenter manuellement __iter__ et __next__ peut devenir verbeux. Python offre une abstraction élégante : le générateur. Une fonction génératrice est une fonction ordinaire qui contient au moins une instruction yield. Lorsqu’elle est appelée, elle ne s’exécute pas immédiatement : elle retourne un objet générateur, qui est un itérateur.

Définition 23 (Générateur)

Une fonction génératrice est une fonction contenant au moins une instruction yield. Son appel retourne un objet générateur qui implémente le protocole itérateur (__iter__ et __next__). À chaque appel de next(), l’exécution reprend là où elle s’était suspendue (au dernier yield) jusqu’au prochain yield ou jusqu’à la fin de la fonction. Lorsque la fonction se termine, StopIteration est levée automatiquement.

def compte_a_rebours(debut: int):
    """Générateur équivalent à CompteARebours, en bien plus concis."""
    while debut > 0:
        yield debut
        debut -= 1


for n in compte_a_rebours(5):
    print(n, end=" ")
print()

# Même comportement qu'avant
gen = compte_a_rebours(3)
print(next(gen))   # 3
print(next(gen))   # 2
print(next(gen))   # 1
try:
    next(gen)
except StopIteration:
    print("Générateur épuisé")

5 4 3 2 1 
3
2
1
Générateur épuisé

def fibonacci():
    """Générateur infini de la suite de Fibonacci."""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b


# On ne peut pas convertir un générateur infini en liste directement !
# On prend les 15 premiers termes avec islice
from itertools import islice

premiers_termes = list(islice(fibonacci(), 15))
print(f"15 premiers termes de Fibonacci : {premiers_termes}")

15 premiers termes de Fibonacci : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

L’avantage majeur des générateurs sur les listes est la paresse (laziness) : les valeurs sont produites à la demande, une par une, sans jamais stocker l’intégralité de la séquence en mémoire. Un générateur qui produit un million de valeurs consomme à peu près la même mémoire qu’un générateur qui en produit dix.

import sys

# Comparaison mémoire : liste vs générateur
liste_million = [x**2 for x in range(1_000_000)]
gen_million = (x**2 for x in range(1_000_000))

print(f"Taille de la liste    : {sys.getsizeof(liste_million):>12,} octets")
print(f"Taille du générateur  : {sys.getsizeof(gen_million):>12,} octets")

Taille de la liste    :    8,448,728 octets
Taille du générateur  :          200 octets

yield from#

L’instruction yield from permet à un générateur de déléguer à un autre itérable. Elle est plus concise et plus efficace que d’itérer manuellement sur le sous-itérable pour re-yielder ses éléments.

def aplatir(imbriqué):
    """Aplatit récursivement une structure imbriquée de listes."""
    for élément in imbriqué:
        if isinstance(élément, list):
            yield from aplatir(élément)   # Délégation récursive
        else:
            yield élément


données = [1, [2, 3], [4, [5, 6]], 7, [8, [9, [10]]]]
print(list(aplatir(données)))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def chaîne(*iterables):
    """Concatène plusieurs itérables — imitation de itertools.chain."""
    for it in iterables:
        yield from it


print(list(chaîne([1, 2], "abc", range(3))))

[1, 2, 'a', 'b', 'c', 0, 1, 2]

yield from prend également en charge le passage de valeurs dans les deux sens lorsque l’on utilise la méthode .send() des générateurs avancés, ce qui est au cœur des coroutines — un sujet traité dans le chapitre sur la programmation asynchrone.

Expressions génératrices#

Tout comme les listes ont leurs compréhensions, les générateurs ont leurs expressions génératrices (generator expressions). La syntaxe est identique à celle des compréhensions de listes, mais avec des parenthèses au lieu des crochets. Le résultat est un objet générateur paresseux.

# Compréhension de liste : calcule tout immédiatement
carrés_liste = [x**2 for x in range(10)]

# Expression génératrice : calcule à la demande
carrés_gen = (x**2 for x in range(10))

print(type(carrés_liste))   # <class 'list'>
print(type(carrés_gen))     # <class 'generator'>

# Dans un appel de fonction, les parenthèses supplémentaires ne sont pas nécessaires
total = sum(x**2 for x in range(100))
print(f"Somme des carrés de 0 à 99 : {total}")

# Filtrage dans une expression génératrice
pairs_carrés = list(x**2 for x in range(20) if x % 2 == 0)
print(f"Carrés des pairs : {pairs_carrés}")

<class 'list'>
<class 'generator'>
Somme des carrés de 0 à 99 : 328350
Carrés des pairs : [0, 4, 16, 36, 64, 100, 144, 196, 256, 324]

La règle pratique : préférez les expressions génératrices aux compréhensions de listes lorsque vous n’avez pas besoin d’accéder plusieurs fois aux résultats ou de les indexer. Si vous construisez une liste pour immédiatement la passer à sum(), max(), min(), any(), all() ou list(), une expression génératrice est plus appropriée.

Le module itertools#

Le module itertools de la bibliothèque standard est une boîte à outils d’itérateurs hautement optimisés, écrits en C. Maîtriser itertools permet d’écrire des traitements de données à la fois concis, expressifs, et très efficaces en mémoire.

```{prf:definition} itertools :label: definition-10-03 Le module itertools regroupe des fonctions de construction d’itérateurs qui s’inspirent de la programmation fonctionnelle et des langages APL, Haskell et SML. Ses fonctions se déclinent en trois familles : les itérateurs infinis (count, cycle, repeat), les itérateurs de terminaison (chain, islice, compress, dropwhile, takewhile, zip_longest…) et les itérateurs combinatoires (product, permutations, combinations, combinations_with_replacement).


```{code-cell} python
import itertools

# ─── Itérateurs infinis ───
print("=== count ===")
for x in itertools.islice(itertools.count(10, 2), 5):
    print(x, end=" ")
print()

print("=== cycle ===")
jours = itertools.cycle(["lun", "mar", "mer"])
print([next(jours) for _ in range(7)])

print("=== repeat ===")
print(list(itertools.repeat("Python", 3)))

# ─── Itérateurs de terminaison ───
print("=== chain ===")
print(list(itertools.chain([1, 2], [3, 4], [5])))

print("=== islice ===")
print(list(itertools.islice(range(100), 2, 12, 3)))   # début=2, fin=12, pas=3

print("=== takewhile / dropwhile ===")
données = [1, 3, 5, 2, 4, 6, 1]
print(list(itertools.takewhile(lambda x: x % 2 != 0, données)))  # Prend tant qu'impair
print(list(itertools.dropwhile(lambda x: x % 2 != 0, données)))  # Saute tant qu'impair

print("=== compress ===")
masque = [1, 0, 1, 1, 0, 1]
print(list(itertools.compress("ABCDEF", masque)))

print("=== zip_longest ===")
print(list(itertools.zip_longest([1, 2, 3], ["a", "b"], fillvalue="?")))

=== chain ===

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[13], line 3
      1 # ─── Itérateurs de terminaison ───
      2 print("=== chain ===")
----> 3 print(list(itertools.chain([1, 2], [3, 4], [5])))
      5 print("=== islice ===")
      6 print(list(itertools.islice(range(100), 2, 12, 3)))   # début=2, fin=12, pas=3

NameError: name 'itertools' is not defined

# ─── Itérateurs combinatoires ───
print("=== product ===")
print(list(itertools.product([0, 1], repeat=3)))   # Toutes les chaînes binaires de longueur 3

print("=== permutations ===")
print(list(itertools.permutations("ABC", 2)))

print("=== combinations ===")
print(list(itertools.combinations(range(5), 3)))

print("=== combinations_with_replacement ===")
print(list(itertools.combinations_with_replacement("AB", 3)))

# ─── groupby : regrouper des éléments consécutifs ───
print("=== groupby ===")
# IMPORTANT : les données doivent être triées par la clé avant groupby
mots = ["pomme", "poire", "prune", "abricot", "ananas", "banane"]
mots_triés = sorted(mots, key=lambda m: m[0])

for lettre, groupe in itertools.groupby(mots_triés, key=lambda m: m[0]):
    print(f"  {lettre} : {list(groupe)}")

```{prf:example} Pipeline de traitement de données avec itertools :label: example-10-01 Imaginons un flux de transactions financières. On souhaite filtrer les transactions positives, les regrouper par catégorie, et calculer le total de chaque groupe — sans jamais charger tout le flux en mémoire.

import itertools
from collections import defaultdict

transactions = [
    ("alimentation", 45.0),
    ("alimentation", -5.0),   # remboursement
    ("transport", 30.0),
    ("loisirs", 120.0),
    ("alimentation", 80.0),
    ("transport", 15.0),
    ("loisirs", -10.0),
    ("loisirs", 55.0),
]

# Filtrer, trier, grouper — tout en mode itérateur
positives = ((cat, montant) for cat, montant in transactions if montant > 0)
triées = sorted(positives, key=lambda t: t[0])

totaux = {
    catégorie: sum(m for _, m in groupe)
    for catégorie, groupe in itertools.groupby(triées, key=lambda t: t[0])
}
print(totaux)
# {'alimentation': 125.0, 'loisirs': 175.0, 'transport': 45.0}


```{code-cell} python
import itertools
from collections import defaultdict

transactions = [
    ("alimentation", 45.0),
    ("alimentation", -5.0),
    ("transport", 30.0),
    ("loisirs", 120.0),
    ("alimentation", 80.0),
    ("transport", 15.0),
    ("loisirs", -10.0),
    ("loisirs", 55.0),
]

positives = ((cat, montant) for cat, montant in transactions if montant > 0)
triées = sorted(positives, key=lambda t: t[0])

totaux = {
    catégorie: sum(m for _, m in groupe)
    for catégorie, groupe in itertools.groupby(triées, key=lambda t: t[0])
}
print(totaux)

Itérateurs infinis et gestion de la terminaison#

Un générateur infini ne pose aucun problème en Python, à condition de ne jamais tenter de le convertir en une structure de données finie sans le tronquer au préalable. Les outils de terminaison d”itertools (islice, takewhile) sont les bons compagnons des générateurs infinis.

def nombres_premiers():
    """Générateur infini des nombres premiers (crible naïf)."""
    def est_premier(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for i in range(3, int(n**0.5) + 1, 2):
            if n % i == 0:
                return False
        return True

    n = 2
    while True:
        if est_premier(n):
            yield n
        n += 1


# Premiers 20 nombres premiers
print(list(itertools.islice(nombres_premiers(), 20)))

# Premiers nombres premiers inférieurs à 50
print(list(itertools.takewhile(lambda p: p < 50, nombres_premiers())))

Avantages mémoire et performance#

La valeur principale des itérateurs et des générateurs est la consommation mémoire constante pour le traitement de flux de données potentiellement illimités. Un pipeline d’itérateurs n’alloue jamais qu’un nombre fixe d’objets en mémoire, quelle que soit la taille des données.

Hide code cell source

 
import time

def mesurer_temps(fn):
    debut = time.perf_counter()
    résultat = fn()
    return time.perf_counter() - debut, résultat

N = 5_000_000

# Version liste : crée N éléments en mémoire
t_liste, r_liste = mesurer_temps(lambda: sum([x**2 for x in range(N) if x % 3 == 0]))

# Version génératrice : traite un élément à la fois
t_gen, r_gen = mesurer_temps(lambda: sum(x**2 for x in range(N) if x % 3 == 0))

assert r_liste == r_gen

fig, axes = plt.subplots(1, 2, figsize=(11, 5))
fig.suptitle("Compréhension de liste vs expression génératrice", fontsize=14, fontweight='bold')

palette = sns.color_palette("muted", 2)

# Temps
axes[0].bar(["Liste", "Générateur"], [t_liste * 1000, t_gen * 1000],
            color=palette, edgecolor='white', linewidth=1.5)
axes[0].set_ylabel("Temps (ms)")
axes[0].set_title(f"Durée d'exécution (N = {N:,})")
for i, t in enumerate([t_liste, t_gen]):
    axes[0].text(i, t * 1000 + 5, f"{t*1000:.1f} ms", ha='center', fontsize=11,
                 fontweight='bold', color=palette[i])

# Mémoire (illustrative)
taille_liste = sys.getsizeof([x**2 for x in range(10_000) if x % 3 == 0])
taille_gen = sys.getsizeof(x**2 for x in range(10_000) if x % 3 == 0)

axes[1].bar(["Liste\n(10 000 élts)", "Générateur"], [taille_liste / 1024, taille_gen / 1024],
            color=palette, edgecolor='white', linewidth=1.5)
axes[1].set_ylabel("Mémoire (ko)")
axes[1].set_title("Empreinte mémoire")
for i, t in enumerate([taille_liste, taille_gen]):
    axes[1].text(i, t / 1024 + 1, f"{t / 1024:.1f} ko", ha='center', fontsize=11,
                 fontweight='bold', color=palette[i])

plt.tight_layout()
plt.show()

Résumé#

Ce chapitre a exposé le protocole itérable de Python, mécanisme central qui unifie toutes les structures de données et tous les outils de traitement séquentiel :

  • Le protocole itérable repose sur __iter__ (qui retourne un itérateur) et __next__ (qui retourne l’élément suivant ou lève StopIteration). Les fonctions iter() et next() permettent d’interagir manuellement avec ce protocole.

  • Un itérable peut produire plusieurs itérateurs indépendants ; un itérateur maintient un état de progression unique et ne peut être parcouru qu’une fois.

  • Les fonctions génératrices (contenant yield) créent des objets générateurs de façon concise. L’exécution se suspend à chaque yield et reprend au next() suivant.

  • yield from délègue à un sous-itérable, simplifie les générateurs récursifs et prend en charge la communication bidirectionnelle pour les coroutines.

  • Les expressions génératrices offrent une syntaxe compacte pour créer des générateurs paresseux à la volée.

  • Le module itertools fournit une palette d’itérateurs optimisés : itérateurs infinis (count, cycle, repeat), de terminaison (chain, islice, compress, takewhile, dropwhile, zip_longest) et combinatoires (product, permutations, combinations). groupby regroupe des éléments consécutifs selon une clé.

  • L’avantage décisif des itérateurs est leur consommation mémoire constante : ils traitent les données au fil de l’eau, sans jamais matérialiser la séquence complète.

Dans le chapitre suivant, nous explorerons les décorateurs — un mécanisme élégant qui s’appuie sur les fonctions de première classe et les fermetures pour transformer et enrichir des fonctions ou des classes.

Contenu