Les générateurs sont un sujet délicat en Python que je vous propose de démystifier. Pour aborder cette thématique, nous commencerons notre voyage avec les itérables et les conteneurs avant d’attaquer les générateurs.
Rappel sur les itérables
Quand vous lisez des éléments un par un d’une liste, on appelle cela de l’itération :
>>> lst = [1, 2, 3]
>>> for i in lst :
... print(i)
1
2
3Et quand on utilise une liste en compréhension (comprehension list), on crée une liste, donc un itérable. Encore une fois, avec une boucle for, on prend ses éléments un par un, donc on itère dessus :
>>> lst = [x*x for x in range(3)]
>>> for i in lst :
... print(i)
0
1
4À chaque fois que l’on peut utiliser une boucle for sur quelque chose, c’est un itérable : listes, chaines de caractères, fichiers ouverts, sockets, etc.
Ces itérables sont pratiques, car on peut les lire autant qu’on veut, mais ce n’est pas toujours idéal parce qu’on doit stocker tous les éléments en mémoire.
Rappel sur les conteneurs
En général, les itérables sont souvent des conteneurs. On appelle conteneur une structure de données contenant des éléments tel que par exemple :
- list, deque, … ;
- set, frozensets, … ;
- dict, defaultdict, OrderedDict, Counter, … ;
- tuple, namedtuple, … ;
- str.
Les conteneurs sont des structures de données qui vivent en mémoire et conservent généralement toutes leurs valeurs en mémoire également. Les conteneurs sont faciles à comprendre, car vous pouvez les considérer comme de vrais conteneurs : une boîte, un placard, une maison, un bateau, etc.
La principale particularité d’un conteneur est qu’il prend en charge les tests d’appartenance. Techniquement, un objet est un conteneur lorsqu’on peut lui demander s’il contient un certain élément. Vous pouvez effectuer de tels tests d’appartenance sur des listes, des ensembles ou des tuples :
>>> 1 in [1, 2, 3] # liste
True
>>> 4 not in [1, 2, 3]
True
>>> 1 in {1, 2, 3} # set
True
>>> 4 not in {1, 2, 3}
True
>>> 1 in (1, 2, 3) # tuple
True
>>> 4 not in (1, 2, 3)
TrueVous noterez que c’est parce qu’il est possible de lire autant de fois que l’on veut le contenu d’un conteneur qu’il est possible de faire des tests d’appartenance sur leur contenu.
Les conteneurs sont les premiers itérables que l’on apprend généralement à utiliser en Python :
>>> for element in [1, 2, 3]: # liste
... print (element)
1
2
3
>>> for caractere in "chat": # chaine de caracteres
... print (caractere)
c
h
a
tMais se ne sont pas les seuls itérables existant :
>>> for nombre in range(3): # itérateur
... print (element)
0
1
2Pour résumer ce que nous venons d’apprendre :
- Tous les conteneurs sont des itérables, mais tous les itérables ne sont pas des conteneurs ;
- Seuls les conteneurs prennent en charge nativement les tests d’appartenance.
Différence entre Itérable et Itérateur
Bien qu’un itérable soit un objet, il n’est pas nécessairement une structure de données (un conteneur) et il peut aussi renvoyer un itérateur (dont le but est de renvoyer tous ses éléments). La différence entre un itérable et un itérateur est importante. Regardons ensemble cet exemple :
>>> x = [1, 2, 3] # iterable
>>> y = iter(x) # iterateur
>>> next(y)
1
>>> next(y)
2
>>> type(x)
<class 'list'>
>>> type(y)
<class 'list_iterator'>Ici, x est un itérable, tandis que y est une instance d’un itérateur qui produit des valeurs à partir de l’itérable x. Vous remarquerez que quand y est appelé à l’aide de next(), celui-ci a gardé en mémoire son état précédent.
NB : Le fait que x soit une structure de données (une liste) n’est pas une exigence pour construire un itérateur.
Alors, qu’est-ce qu’un itérateur ? C’est un objet avec états qui produira la valeur suivante lorsque vous l’appellerez avec next(). La façon dont il produit une valeur n’a pas d’importance. Un itérateur est donc juste une usine qui fabrique de valeurs. Chaque fois que vous lui demanderez la valeur “suivante”, il saura comment la calculer, car il conserve à tout moment, en mémoire, un état interne qui lui permet de connaître la prochaine valeur à retourner. Par sa nature, un itérateur n’a pas de tests d’appartenance.
Transformer une liste en compréhension en expression génératrice
Avant d’aborder concrètement les générateurs, attardons-nous sur le cas particulier de l’expression génératrice, qui est une forme particulière d’itérateur. Pour cela, rien de plus simple, il suffit de remplacer les [] d’une liste en compréhension par des (). Cela revient à créer une expression génératrice.
Avant :
>>> comprehension_de_liste = [x*x for x in range(3)]
>>> type(comprehension_de_liste)
<class 'list'>
>>> for i in comprehension_de_liste :
... print(i)
0
1
4Après :
>>> generateur = (x*x for x in range(3))
>>> type(generateur)
<class 'generator'>
>>> for i in generateur :
... print(i)
0
1
4Typographiquement, la seule différence avec la liste en compréhension est la suivante :
- On a utilisé des
()au lieu des[].
Fonctionnement, il y a 2 différences majeures à connaître :
- On ne peut lire
generateurqu’une seule et unique fois ; - Tous les éléments sont générés les uns après les autres et donc ils ne sont pas stockés en mémoire en même temps.
En effet, le principe des générateurs, c’est justement qu’ils génèrent tout à la volée : ici, il calcule 0, puis l’oublie, puis calcule 1, et l’oublie, et calcule 4. Tout ça un par un.
Les générateurs
Enfin, nous arrivons au cœur du sujet : les générateurs. Un générateur est un type particulier d’itérateur. Un générateur vous permet d’écrire des itérateurs dans une syntaxe élégante et succincte qui évite d’écrire des classes avec les méthodes __iter__() et __next__().
Soyons explicites :
- Tout générateur est aussi un itérateur (pas l’inverse !) ;
- Tout générateur est donc une usine qui produit à la volée des valeurs.
Pour fonctionner, les générateurs utilisent l’instruction yield.
Le mot-clé yield
yield est un mot clé, spécifique aux générateurs, qui s’apparente à return puisque son rôle est de retourner une valeur, à la différence près qu’il ne quitte pas la fonction.
A noté aussi que la présence d’un yield dans une fonction transforme automatiquement celle-ci en générateur.
>>> def creer_generateur() :
... ma_list = range(3)
... for i in ma_list:
... yield i*i
...
>>> generateur = creer_generateur() # crée un générateur
>>> generateur # generateur est un objet !
<generator object creer_generateur at 0x2b484b9addc0>
>>> for i in generateur:
... print(i)
0
1
4Bien que cet exemple soit inutile, en pratique, quand on sait que notre fonction doit retourner de nombreuses valeurs que l’on ne souhaite lire qu’une seule fois, on utilisera un générateur.
Le principe fondamental à connaitre concernant le mot-clé yield est de savoir qu’à l’appel de la fonction, son code n’est pas exécuté. À la place, la fonction va retourner un objet générateur :
creer_generateur()n’exécute pas le code qu’elle contient ;creer_generateur()retourne un objet générateur.
En fait, tant que l’on ne touche pas au générateur, il ne se passe rien. Puis, dès que l’on commence à itérer sur le générateur, le code de la fonction s’exécute.
La première fois que le code s’exécute, il part du début de la fonction, arrive jusqu’à yield, et retourne la première valeur. Ensuite, à chaque nouveau tour de boucle, le code reprend à l’endroit où il s’était arrêté précédemment. Fonctionnellement, Python sauvegarde l’état du code du générateur entre chaque appel. Puis, à chaque nouvel appel, il exécute le code à nouveau jusqu’à ce qu’il rencontre yield. Donc dans notre cas, il va faire un tour de boucle. Vous l’aurez compris, yield fonctionne comme un point d’arrêt sur lequel la fonction est stoppée jusqu’au prochain appel de celle-ci.
Il va continuer comme cela jusqu’à ce que le code ne rencontre plus aucun yield et donc qu’il n’y ait plus de valeur à retourner. Le générateur est alors considéré comme définitivement vide. Comme il ne peut pas être réinitialisé, si vous souhaitez le réutiliser, il vous faudra en créer un autre.
La raison pour laquelle le code ne rencontrera plus yield sera celle de votre choix : condition if/else, boucle, récursion… Vous pouvez même yielder à l’infini comme dans cet exemple :
def repeter(valeur):
while True:
yield valeurRésultat :
>>> for i in repeter('Salut'):
... print(i)
'Salut'
'Salut'
'Salut'
'Salut'
'Salut'
...N’oubliez pas d’appuyer sur Ctrl+C si vous voulez sortir de la boucle infinie dans une session exécutée avec l’interpréteur interactif.
Le mot-clé next
Utiliser une boucle n’est pas l’unique moyen d’itérer sur un générateur. Vous pouvez aussi utiliser l’instruction next(). Reprenons notre fonction creer_generateur() :
>>> def creer_generateur() :
... for i in range(3):
... yield i*i
...
>>> generateur = creer_generateur() # crée un générateur
>>> print(next(generateur))
0
>>> print(next(generateur))
1
>>> print(next(generateur))
4
>>> print(next(generateur))
StopIteration
>>> print(next(generateur))
StopIterationNotre generateur a cessé de produire de nouvelles valeurs après trois itérations. Il l’a fait en levant une exception StopIteration lorsque l’exécution a atteint la fin de la fonction sans rencontrer d’instruction yield.
En résumé, le code de la fonction génératrice ne s’exécute que lorsque next() est appelé sur l’objet générateur. next() exécute le code du générateur jusqu’au prochain yield. L’exécution peut être reprise à tout moment en faisant appel au générateur avec next(). On remarque aussi qu’une erreur StopIteration est levée quand le générateur a épuisé tous les yield.
Quid de la vitesse et de la mémoire ?
Les générateurs offrent le plus d’avantages en matière de consommation de mémoire, en raison de la méthode d’évaluation qu’ils fournissent, empêchant toutes les valeurs d’être chargées en mémoire en même temps.
Dans l’exemple suivant, nous allons comparer la taille en octets d’un générateur pour générer une séquence de 50 000 entiers par rapport à une liste statique de 50 000 entiers.
>>> from sys import getsizeof
>>> comp = [x * 5 for x in range(50000)]
>>> getsizeof(comp)
406488
>>> gen = (x * 5 for x in range(50000))
>>> getsizeof(gen)
112Le générateur ne consomme que 112 octets de mémoire alors que la liste d’entiers générée statiquement consomme 406 488 octets de mémoire. Dans cet exemple particulier, le générateur est ~3600x plus efficace en mémoire que la liste.
Si nous représentions schématiquement la différence de consommation de mémoire, cela donnerait le schéma de principe suivant (qui n’est pas à l’échelle) :
Les générateurs n’ont pas que des avantages. Alors que l’on gagne mémoire, il est possible d’observer une baisse de performances sur les temps d’exécution. En effet, l’utilisation d’un générateur par opposition à une liste de valeurs générée statiquement entraîne un nombre beaucoup plus élevé d’appels de fonction et par conséquent un temps d’exécution plus long.
Ci-dessous, une simple somme de 100 000 entiers est profilée à l’aide de cProfile.
>>> import cProfile
>>> cProfile.run('sum((i for i in range(100000)))')
100005 function calls in 0.041 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
100001 0.020 0.000 0.020 0.000 :1()
1 0.000 0.000 0.041 0.041 :1()
1 0.000 0.000 0.041 0.041 {built-in method builtins.exec}
1 0.021 0.021 0.041 0.041 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
>>> cProfile.run('sum([i for i in range(100000)])')
5 function calls in 0.012 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.008 0.008 0.008 0.008 :1()
1 0.002 0.002 0.012 0.012 :1()
1 0.000 0.000 0.012 0.012 {built-in method builtins.exec}
1 0.003 0.003 0.003 0.003 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}L’expression génératrice génère 100 005 appels de fonction en 41 ms, par rapport à la liste en compréhension qui ne génère que 5 appels de fonction en 12 ms.
Cela est dû au générateur renvoyé par l’expression génératrice et à l’appel de next() pour obtenir chaque valeur de la séquence.
La conclusion naturelle de ces observations est qu’une attention particulière doit être accordée aux exigences d’un système. Si les contraintes de mémoire l’emportent sur la vitesse, alors un générateur est la solution la plus adaptée. Inversement, si la consommation de mémoire est moins prioritaire que les performances d’exécution, il est plus approprié d’utiliser une source de données statique telle qu’une liste.
Le mot de la fin
Les générateurs permettent non seulement d’économiser de la
mémoire, mais surtout de masquer la complexité d’un algorithme derrière
une API classique d’itération. Les fonctions génératrices sont une
fonctionnalité intéressante de Python, et vous ne devriez pas hésiter à les utiliser dans vos propres programmes.
Synthétiquement :
- Les fonctions génératrices ont une syntaxique élégante et
intéressante pour écrire des objets qui prennent en charge le protocole
itérateur ; - L’instruction
yieldvous permet de suspendre temporairement l’exécution d’une fonction génératrice et d’en renvoyer des valeurs ; - Les générateurs lèvent des exceptions
StopIterationune fois que le flux de contrôle a quitté la fonction génératrice par tout autre moyen qu’une instructionyield.
Enfin, pour vous y retrouver dans tous les termes employés dans cet article, voici un schéma récapitulatif :
Pour finir, j’ai volontairement omis d’aborder les méthodes .send(), .throw() et .close() qui sont couramment utilisées avec les générateurs. Elles seront abordées dans un article dédié au même titre que l’implémentation de générateurs sous forme de class.
J’espère que cet article vous aura apporté un peu de clarté sur le concept des générateurs.
Si vous avez des questions, les commentaires sont là pour ça.
Bonjour Monsieur,
Bravo pour vos explications très claires, et notamment le schéma final qui est le modèle type sur les générateurs / conteneurs et itérateurs / itérables !
Excellent article qui explique succintement la notion de générateur en Python !
Merci pour vos explications très claires. J’adore votre travail !
La phrase “Seuls les conteneurs prennent en charge les tests d’appartenance.” est fausse.
Si la classe
Cne définit pas la méthode__contains__alors(x in C)devient :any(x==element for element in C).Donc le test d’appartenance est possible pour tout itérable.
Par exemple :
1 in (x**2 for x in range(9))=>True;2 in (x**2 for x in range(9))=>False.Bonjour,
Je comprends votre remarque et c’est effectivement très intéressant que vous spécifiez la méthode
__contains__qui correspond à l’implémentation du test d’appartenance dans les conteneurs. Sans cette méthode, le test d’appartenance est tout de même possible, mais pas nativement, comme vous l’avez démontré très efficacement. Dès lors, si ce n’est pas natif, c’est qu’ils ne sont pas pris en charge.C’est pour cette raison que dans la section des conteneurs, j’ai pris le soin de spécifier ce qui fait la particularité d’un test d’appartenance :
Je vais voir à rajouter un mot sur le fait que le test d’appartenance soit natif ou non.
Je vous remercie pour votre retour.
Christophe