Itérateurs et Générateurs

Les itérateurs

Un itérateur permet de parcourir une séquence d’éléments. Les collections en Python comme les listes, les ensembles, les tuples, les dictionnaires et même les chaînes de caractères peuvent se comporter comme des itérateurs et être utilisés par exemple dans une expression for.

ma_liste = ["Pomme", "Poire", "Orange"]
for e in ma_liste:
    print(e)

Il est possible pour n’importe quel objet de se comporter comment un itérateur. Pour cela, il suffit qu’il implémente les méthodes spéciales __iter__() et __next__().

__iter__()

Retourne un objet qui sert d’itérateur. Un itérateur doit lui-même avoir une méthode __iter__() qui peut se limiter à retourner l’itérateur lui-même.

__next__()

Retourne l’élément suivant. S’il n’y a plus d’élément, alors cette méthode doit lever une exception de type StopIteration.

Ci-dessous un exemple d’itérateur qui permet de compter jusqu’à 10 :

class Compteur:

    def __init__(self):
        self.nombre = 0

    def __iter__(self):
        return self

    def __next__(self):
        self.nombre += 1
        if self.nombre > 10:
            raise StopIteration
        return self.nombre

Il est possible d’utiliser la classe Compteur dans une expression for :

for i in Compteur():
    print(i)

# Affiche les nombres de 1 à 10.

Les fonctions iter() et next()

La fonction iter() permet d’obtenir un itérateur à partir d’un objet. Concrètement, cette fonction appelle la méthode __iter__() de l’objet passé en paramètre.

La fonction next() attend un itérateur en paramètre et retourne l’élément suivant. Si l’itérateur est déjà positionné sur le dernier élément, cette fonction lève une exception de type StopIteration. Concrètement, cette fonction appelle la méthode __next__() de l’itérateur passé en paramètre.

it = iter(range(3))

print(next(it))
# affiche 0
print(next(it))
# affiche 1
print(next(it))
# affiche 2
print(next(it))
# provoque une exception StopIteration

Les méthodes iter() et next() permettent d’interagir directement avec un itérateur. Cependant on utilise la plupart du temps un itérateur dans une expression for ou avec le mot-clé in.

Si vous voulez rendre un objet itérable, vous pouvez simplement implémenter la méthode __iter__() dans votre classe de manière à ce qu’elle retourne le résultat d’un appel à la fonction iter() :

class Chemin:
    def __init__(self):
        self.direction = []

    def gauche(self):
        self.direction.append("gauche")

    def droite(self):
        self.direction.append("droite")

    def __iter__(self):
        return iter(self.direction)


chemin = Chemin()
chemin.droite()
chemin.gauche()
chemin.gauche()
chemin.droite()

for direction in chemin:
    print(direction)

# Affiche
#   droite
#   gauche
#   gauche
#   droite

Les générateurs

Les générateurs sont une catégorie particulière d’itérateurs. Un générateur crée à la demande l’élément suivant de la séquence. Pour cela, le générateur peut utiliser une formule mathématique pour calculer une suite ou bien il peut utiliser une système externe comme une base de données pour extraire l’élément suivant. L’intérêt d’un générateur est qu’il n’est pas nécessaire de construire en mémoire la liste complète des éléments de la séquence. Les générateurs ont donc une empreinte mémoire très faible ce qui permet d’écrire des programmes optimisés.

Le générateur le plus couramment utilisé en Python est créé via la classe range :

for i in range(50000):
    print(i)

Dans l’exemple ci-dessus, la classe range ne crée pas un tableau de 50 000 éléments. Elle crée un itérateur qui se contente de reproduire un suite mathématique en ajoutant 1 à la valeur précédente.

Note

range est une amélioration notable de Python 3. En Python 2.x, son implémentation créée effectivement une séquence en mémoire de toutes les valeurs, ce qui est beaucoup moins performant.

Nous avons déjà présenté un exemple de générateur plus haut avec l’exemple de la classe Compteur qui est en fait une implémentation très simplifiée de range :

class Compteur:

    def __init__(self):
        self.nombre = 0

    def __iter__(self):
        return self

    def __next__(self):
        self.nombre += 1
        if self.nombre > 10:
            raise StopIteration
        return self.nombre

La classe Compteur ne conserve en mémoire que l’attribut nombre, c’est-à-dire la valeur courante. Cela lui permet de déduire la valeur suivante et de mettre à jour cet attribut à chaque appel de __next(self)__.

Il est donc possible de créer des générateurs en utilisant le principe d’implémentation des itérateurs. Cependant, Python fournit deux autres manières de créer des générateurs qui sont beaucoup plus simples et donc beaucoup plus utiles dans les programmes.

Les fonctions génératrices avec yield

Python dispose du mot-clé yield. Il permet de transformer une fonction en générateur. yield retourne l’élément suivant du générateur. Tout se passe comme si une instruction à yield suspendait l’exécution de la fonction qui se continuera au passage à l’élément suivant du générateur.

def ma_fonction():
    yield "un"
    yield "deux"
    yield "trois"


for x in ma_fonction():
    print(x)

# Affiche
#   un
#   deux
#   trois

Ainsi il est très facile d’implémenter la fonctionnalité identique à notre classe Compteur mais cette fois-ci sous la forme d’une fonction génératrice :

def compteur():
    cpt = 1
    while cpt <= 10:
        yield cpt
        cpt += 1


for x in compteur():
    print(x)

# Affiche les nombres de 1 à 10

Une fonction génératrice est très souvent beaucoup plus simple à implémenter et à comprendre qu’un itérateur tout en permettant d’arriver au même résultat.

Il est possible d’utiliser la syntaxe yield from pour signaler que l’on souhaite créer une fonction génératrice à partir d’un générateur. Ainsi notre fonction génératrice compteur() peut simplement être implémentée à partir de range :

def compteur():
    yield from range(1, 11)

Les générateurs en compréhension

Comme pour les listes en compréhension, il est possible de définir un générateur en compréhension en utilisant des parenthèses plutôt que les crochets.

for i in (x**2 for x in range(5)):
    print(i)

# Affiche: 0 1 4 9 16

Même si la syntaxe est très proche, le mécanisme sous-jacent est très différent de la liste en compréhension. Si vous prenez les exemples ci-dessous :

[x**2 for x in range(1,1001)]
(x**2 for x in range(1,1001))

Le premier est une liste en compréhension qui crée donc une liste de 1000 éléments en mémoire. Le second est un générateur en compréhension. Il s’agit donc d’une fonction qui peut fournir à la demande la valeur de l’élément suivant de la séquence. Il n’y a donc aucune liste en mémoire qui est créée.

Note

Il n’est pas nécessaire d’écrire les parenthèses quand on passe le générateur comme paramètre d’une fonction :

sum(x**2 for x in range(10))

Les fonctions enumerate, map, zip, filter

Parmi les fonctions de base en Python (appelées builtins functions), il existe des fonctions qui produisent des itérateurs. Nous connaissons déjà range() (qui est en fait une classe en Python 3) : elle crée un itérateur sur une suite de nombres. Mais il existe quatre autres fonctions extrêmement utiles.

enumerate()

produit un itérateur qui retourne un tuple contenant un compteur de l’itération courante et la valeur obtenue à partir de l’itérateur passé en paramètre. Le paramètre nommé start permet d’indiquer la valeur de départ du compteur (par défaut 0) :

Affichage des jours de la semaine avec leur numéro
la_semaine = ["lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi", "dimanche"]
for cpt, v in enumerate(la_semaine, start=1):
    print(cpt, v)

# Affiche
#   1 lundi
#   2 mardi
#   3 mercredi
#   4 jeudi
#   5 vendredi
#   6 samedi
#   7 dimanche
map()

produit un itérateur qui accepte une fonction pour produire une nouvelle valeur à partir de la valeur obtenue par l’itérateur passé en second paramètre :

Affichage des jours de la semaine en majuscules
la_semaine = ["lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi", "dimanche"]
for v in map(str.upper, la_semaine):
    print(v)

# Affiche
#   LUNDI
#   MARDI
#   MERCREDI
#   JEUDI
#   VENDREDI
#   SAMEDI
#   DIMANCHE

Cette fonction permet également de combiner les valeurs produites par plusieurs itérateurs :

Concaténation deux à deux des lettres de deux mots
for v in map(lambda x, y: x + y, "hello", "world"):
    print(v)

# Affiche
#   hw
#   eo
#   lr
#   ll
#   od
zip()

produit un itérateur qui produit un tuple regroupant les valeurs de chacun des itérateurs passés en paramètre. L’itération s’arrête lorsque l’un des itérateurs se termine.

filter()

produit un itérateur qui retourne la valeur de l’itérateur passé en second paramètre que si la fonction passée en premier paramètre retourne True pour cette valeur.

Affichage des jours de la semaine qui commence par un m
la_semaine = ["lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi", "dimanche"]
for v in filter(lambda x: x.startswith("m"), la_semaine):
    print(v)

# Affiche
#   mardi
#   mercredi

Le module itertools

Le module itertools fournit des fonctions très utiles pour créer des générateurs. Par exemple, il est possible de créer un générateur infini (du moins allant jusqu’à la plus grande valeur possible d’un entier) grâce à count() :

import itertools as it

for i in it.count():
    # Attention l'itération ne s'arrête pas avant longtemps
    print(i)

Il est également possible de réaliser un produit cartésien entre plusieurs générateurs grâce à la fonction product() :

import itertools as it

for x, y in it.product(range(5), range(100,102)):
    print(x, y)

# Affiche
#   0 100
#   0 101
#   1 100
#   1 101
#   2 100
#   2 101
#   3 100
#   3 101
#   4 100
#   4 101