Comprendre les générateurs en Python

218

Je lis le livre de recettes Python en ce moment et je regarde actuellement des générateurs. J'ai du mal à me tourner la tête.

Comme je viens d'un arrière-plan Java, y a-t-il un équivalent Java? Le livre parlait de «producteur / consommateur», mais quand j'entends dire que je pense au filetage.

Qu'est-ce qu'un générateur et pourquoi l'utiliseriez-vous? Sans citer aucun livre, évidemment (sauf si vous pouvez trouver une réponse décente et simpliste directement à partir d'un livre). Peut-être avec des exemples, si vous vous sentez généreux!

Federer
la source

Réponses:

402

Remarque: ce post suppose la syntaxe Python 3.x.

Un générateur est simplement une fonction qui renvoie un objet sur lequel vous pouvez appeler next, de telle sorte que pour chaque appel, il renvoie une valeur, jusqu'à ce qu'il déclenche une StopIterationexception, signalant que toutes les valeurs ont été générées. Un tel objet est appelé un itérateur .

Les fonctions normales renvoient une seule valeur en utilisant return, comme en Java. En Python, cependant, il existe une alternative, appelée yield. Utiliser yieldn'importe où dans une fonction en fait un générateur. Observez ce code:

>>> def myGen(n):
...     yield n
...     yield n + 1
... 
>>> g = myGen(6)
>>> next(g)
6
>>> next(g)
7
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Comme vous pouvez le voir, myGen(n)est une fonction qui donne net n + 1. Chaque appel à nextrenvoie une valeur unique, jusqu'à ce que toutes les valeurs aient été générées. forles boucles appellent nexten arrière-plan, donc:

>>> for n in myGen(6):
...     print(n)
... 
6
7

De même, il existe des expressions de générateur , qui fournissent un moyen de décrire succinctement certains types courants de générateurs:

>>> g = (n for n in range(3, 5))
>>> next(g)
3
>>> next(g)
4
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Notez que les expressions de générateur ressemblent beaucoup à des listes de compréhension :

>>> lc = [n for n in range(3, 5)]
>>> lc
[3, 4]

Observez qu'un objet générateur est généré une fois , mais que son code n'est pas exécuté d'un seul coup. Appelle uniquement pour nextexécuter (en partie) le code. L'exécution du code dans un générateur s'arrête une fois qu'une yieldinstruction a été atteinte, sur laquelle il renvoie une valeur. L'appel suivant à fait nextalors continuer l'exécution dans l'état dans lequel le générateur a été laissé après le dernier yield. Il s'agit d'une différence fondamentale avec les fonctions régulières: celles-ci commencent toujours l'exécution au "sommet" et ignorent leur état lors du retour d'une valeur.

Il y a plus de choses à dire sur ce sujet. Il est par exemple possible de sendremonter les données dans un générateur ( référence ). Mais c'est quelque chose que je vous suggère de ne pas examiner avant d'avoir compris le concept de base d'un générateur.

Vous pouvez maintenant vous demander: pourquoi utiliser des générateurs? Il y a deux bonnes raisons:

  • Certains concepts peuvent être décrits de manière beaucoup plus succincte à l'aide de générateurs.
  • Au lieu de créer une fonction qui renvoie une liste de valeurs, on peut écrire un générateur qui génère les valeurs à la volée. Cela signifie qu'aucune liste n'a besoin d'être construite, ce qui signifie que le code résultant est plus efficace en mémoire. De cette façon, on peut même décrire des flux de données qui seraient tout simplement trop volumineux pour tenir en mémoire.
  • Les générateurs permettent une manière naturelle de décrire des flux infinis . Considérez par exemple les nombres de Fibonacci :

    >>> def fib():
    ...     a, b = 0, 1
    ...     while True:
    ...         yield a
    ...         a, b = b, a + b
    ... 
    >>> import itertools
    >>> list(itertools.islice(fib(), 10))
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
    

    Ce code utilise itertools.islicepour prendre un nombre fini d'éléments d'un flux infini. Il est conseillé d'avoir un bon aperçu des fonctions du itertoolsmodule, car ce sont des outils essentiels pour écrire des générateurs avancés avec une grande facilité.


  † A propos de Python <= 2.6: dans les exemples ci-dessus nextest une fonction qui appelle la méthode __next__sur l'objet donné. En Python <= 2.6 on utilise une technique légèrement différente, à savoir o.next()au lieu de next(o). Python 2.7 a un next()appel .next, vous n'avez donc pas besoin d'utiliser ce qui suit dans 2.7:

>>> g = (n for n in range(3, 5))
>>> g.next()
3
Stephan202
la source
9
Vous mentionnez qu'il est possible de sendtransmettre des données à un générateur. Une fois que vous avez fait cela, vous avez une «coroutine». Il est très simple d'implémenter des modèles comme le consommateur / producteur mentionné avec des coroutines car ils n'ont pas besoin de Locks et ne peuvent donc pas bloquer. Il est difficile de décrire les coroutines sans dénigrer les threads, donc je dirai simplement que les coroutines sont une alternative très élégante au threading.
Jochen Ritzel
Les générateurs Python sont-ils essentiellement des machines de Turing en termes de fonctionnement?
Fiery Phoenix
48

Un générateur est en fait une fonction qui renvoie (des données) avant qu'il ne soit terminé, mais il s'arrête à ce point et vous pouvez reprendre la fonction à ce point.

>>> def myGenerator():
...     yield 'These'
...     yield 'words'
...     yield 'come'
...     yield 'one'
...     yield 'at'
...     yield 'a'
...     yield 'time'

>>> myGeneratorInstance = myGenerator()
>>> next(myGeneratorInstance)
These
>>> next(myGeneratorInstance)
words

etc. L'avantage (ou l'un) des générateurs est que, du fait qu'ils traitent les données une par une, vous pouvez gérer de grandes quantités de données; avec les listes, les besoins excessifs en mémoire peuvent devenir un problème. Les générateurs, tout comme les listes, sont itérables, ils peuvent donc être utilisés de la même manière:

>>> for word in myGeneratorInstance:
...     print word
These
words
come
one
at 
a 
time

Notez que les générateurs offrent une autre façon de gérer l'infini, par exemple

>>> from time import gmtime, strftime
>>> def myGen():
...     while True:
...         yield strftime("%a, %d %b %Y %H:%M:%S +0000", gmtime())    
>>> myGeneratorInstance = myGen()
>>> next(myGeneratorInstance)
Thu, 28 Jun 2001 14:17:15 +0000
>>> next(myGeneratorInstance)
Thu, 28 Jun 2001 14:18:02 +0000   

Le générateur encapsule une boucle infinie, mais ce n'est pas un problème car vous n'obtenez chaque réponse qu'à chaque fois que vous la demandez.

Caleb Hattingh
la source
30

Tout d'abord, le terme générateur était à l'origine quelque peu mal défini en Python, conduisant à beaucoup de confusion. Vous voulez probablement dire les itérateurs et les itérables (voir ici ). Ensuite, en Python, il y a aussi des fonctions de générateur (qui renvoient un objet générateur), des objets de générateur (qui sont des itérateurs) et des expressions de générateur (qui sont évaluées en un objet générateur).

Selon l'entrée du glossaire pour le générateur, il semble que la terminologie officielle est maintenant que générateur est l'abréviation de "fonction de générateur". Dans le passé, la documentation définissait les termes de manière incohérente, mais heureusement, cela a été corrigé.

Il pourrait être judicieux d'être précis et d'éviter le terme "générateur" sans autre spécification.

nikow
la source
2
Hmm je pense que vous avez raison, du moins selon un test de quelques lignes en Python 2.6. Une expression de générateur renvoie un itérateur (alias «objet générateur»), pas un générateur.
Craig McQueen
22

Les générateurs peuvent être considérés comme un raccourci pour créer un itérateur. Ils se comportent comme un Iterator Java. Exemple:

>>> g = (x for x in range(10))
>>> g
<generator object <genexpr> at 0x7fac1c1e6aa0>
>>> g.next()
0
>>> g.next()
1
>>> g.next()
2
>>> list(g)   # force iterating the rest
[3, 4, 5, 6, 7, 8, 9]
>>> g.next()  # iterator is at the end; calling next again will throw
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

J'espère que cela aide / est ce que vous recherchez.

Mettre à jour:

Comme de nombreuses autres réponses le montrent, il existe différentes façons de créer un générateur. Vous pouvez utiliser la syntaxe entre parenthèses comme dans mon exemple ci-dessus, ou vous pouvez utiliser yield. Une autre caractéristique intéressante est que les générateurs peuvent être "infinis" - des itérateurs qui ne s'arrêtent pas:

>>> def infinite_gen():
...     n = 0
...     while True:
...         yield n
...         n = n + 1
... 
>>> g = infinite_gen()
>>> g.next()
0
>>> g.next()
1
>>> g.next()
2
>>> g.next()
3
...
surpenser
la source
1
Maintenant, Java a des Streams, qui sont beaucoup plus similaires aux générateurs, sauf que vous ne pouvez apparemment pas simplement obtenir l'élément suivant sans une quantité surprenante de tracas.
Fund Monica's Lawsuit
12

Il n'y a pas d'équivalent Java.

Voici un petit exemple artificiel:

#! /usr/bin/python
def  mygen(n):
    x = 0
    while x < n:
        x = x + 1
        if x % 3 == 0:
            yield x

for a in mygen(100):
    print a

Il y a une boucle dans le générateur qui va de 0 à n, et si la variable de boucle est un multiple de 3, elle donne la variable.

A chaque itération de la forboucle, le générateur est exécuté. Si c'est la première fois que le générateur s'exécute, il démarre au début, sinon il continue à partir du moment précédent qu'il a cédé.

Wernsey
la source
2
Le dernier paragraphe est très important: l'état de la fonction de générateur est «gelé» à chaque fois qu'elle produit qch, et continue exactement dans le même état lorsqu'elle est invoquée la prochaine fois.
Johannes Charra
Il n'y a pas d'équivalent syntaxique en Java à une "expression de générateur", mais les générateurs - une fois que vous en avez un - ne sont essentiellement qu'un itérateur (mêmes caractéristiques de base qu'un itérateur Java).
overthink
@overthink: Eh bien, les générateurs peuvent avoir d'autres effets secondaires que les itérateurs Java ne peuvent pas avoir. Si je mettais print "hello"après x=x+1dans mon exemple, "bonjour" serait imprimé 100 fois, tandis que le corps de la boucle for ne serait exécuté que 33 fois.
Wernsey
@iWerner: Je suis sûr que le même effet pourrait être obtenu en Java. L'implémentation de next () dans l'itérateur Java équivalent devrait toujours rechercher de 0 à 99 (en utilisant votre exemple mygen (100)), vous pouvez donc System.out.println () à chaque fois si vous le souhaitez. Cependant, vous ne reviendriez que 33 fois à partir de next (). Ce qui manque à Java, c'est la syntaxe de rendement très pratique qui est beaucoup plus facile à lire (et à écrire).
overthink
J'ai adoré lire et me souvenir de cette définition d'une seule ligne: si c'est la première fois que le générateur s'exécute, il démarre au début, sinon, il continue à partir du moment précédent, il a cédé.
Iqra.
8

J'aime décrire les générateurs, à ceux qui ont une formation décente dans les langages de programmation et l'informatique, en termes de trames de pile.

Dans de nombreuses langues, il y a une pile au-dessus de laquelle se trouve le "cadre" de pile actuel. Le cadre de pile comprend l'espace alloué aux variables locales à la fonction, y compris les arguments passés à cette fonction.

Lorsque vous appelez une fonction, le point d'exécution actuel (le "compteur de programme" ou équivalent) est poussé sur la pile et un nouveau cadre de pile est créé. L'exécution est ensuite transférée au début de la fonction appelée.

Avec les fonctions régulières, à un moment donné, la fonction renvoie une valeur et la pile est "sautée". Le cadre de pile de la fonction est ignoré et l'exécution reprend à l'emplacement précédent.

Lorsqu'une fonction est un générateur, elle peut renvoyer une valeur sans que le cadre de pile ne soit supprimé, à l'aide de l'instruction yield. Les valeurs des variables locales et le compteur de programme dans la fonction sont conservés. Cela permet au générateur d'être repris ultérieurement, avec une exécution continue à partir de l'instruction yield, et il peut exécuter plus de code et retourner une autre valeur.

Avant Python 2.5, tous les générateurs le faisaient. Python 2.5 a ajouté la capacité de transmettre des valeurs de retour dans le générateur ainsi. Ce faisant, la valeur transmise est disponible en tant qu'expression résultant de l'instruction yield qui avait temporairement renvoyé le contrôle (et une valeur) du générateur.

L'avantage principal des générateurs est que "l'état" de la fonction est préservé, contrairement aux fonctions normales où chaque fois que le cadre de pile est supprimé, vous perdez tout cet "état". Un avantage secondaire est d'éviter une partie de la surcharge des appels de fonction (création et suppression de trames de pile), bien qu'il s'agisse généralement d'un avantage mineur.

Peter Hansen
la source
6

La seule chose que je peux ajouter à la réponse de Stephan202 est une recommandation que vous jetiez un coup d'œil à la présentation PyCon '08 de David Beazley "Generator Tricks for Systems Programmers", qui est la meilleure explication unique du comment et du pourquoi des générateurs que j'ai vus. nulle part. C'est ce qui m'a fait passer de "Python a l'air plutôt amusant" à "C'est ce que je cherchais". C'est à http://www.dabeaz.com/generators/ .

Robert Rossney
la source
6

Cela aide à faire une distinction claire entre la fonction foo et le générateur foo (n):

def foo(n):
    yield n
    yield n+1

foo est une fonction. foo (6) est un objet générateur.

La manière typique d'utiliser un objet générateur est en boucle:

for n in foo(6):
    print(n)

La boucle s'imprime

# 6
# 7

Considérez un générateur comme une fonction pouvant être reprise.

yieldse comporte comme returndans le sens où les valeurs qui sont produites sont "renvoyées" par le générateur. Contrairement à return, cependant, la prochaine fois que le générateur reçoit une valeur, la fonction du générateur, foo, reprend là où elle s'était arrêtée - après la dernière déclaration de rendement - et continue de fonctionner jusqu'à ce qu'elle atteigne une autre déclaration de rendement.

Dans les coulisses, lorsque vous appelez, bar=foo(6)la barre d'objets du générateur est définie pour que vous ayez un nextattribut.

Vous pouvez l'appeler vous-même pour récupérer les valeurs issues de foo:

next(bar)    # Works in Python 2.6 or Python 3.x
bar.next()   # Works in Python 2.5+, but is deprecated. Use next() if possible.

Lorsque foo se termine (et qu'il n'y a plus de valeurs produites), l'appel next(bar)renvoie une erreur StopInteration.

unutbu
la source
5

Ce message utilisera les nombres de Fibonacci comme outil pour construire pour expliquer l'utilité des générateurs Python .

Cet article présentera à la fois du code C ++ et Python.

Les nombres de Fibonacci sont définis comme la séquence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ....

Ou en général:

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2

Cela peut être transféré dans une fonction C ++ extrêmement facilement:

size_t Fib(size_t n)
{
    //Fib(0) = 0
    if(n == 0)
        return 0;

    //Fib(1) = 1
    if(n == 1)
        return 1;

    //Fib(N) = Fib(N-2) + Fib(N-1)
    return Fib(n-2) + Fib(n-1);
}

Mais si vous souhaitez imprimer les six premiers nombres de Fibonacci, vous recalculerez beaucoup de valeurs avec la fonction ci-dessus.

Par exemple :, Fib(3) = Fib(2) + Fib(1)mais Fib(2)recalcule également Fib(1). Plus la valeur que vous souhaitez calculer est élevée, plus vous vous sentirez mal.

On peut donc être tenté de réécrire ce qui précède en gardant une trace de l'état dans main.

// Not supported for the first two elements of Fib
size_t GetNextFib(size_t &pp, size_t &p)
{
    int result = pp + p;
    pp = p;
    p = result;
    return result;
}

int main(int argc, char *argv[])
{
    size_t pp = 0;
    size_t p = 1;
    std::cout << "0 " << "1 ";
    for(size_t i = 0; i <= 4; ++i)
    {
        size_t fibI = GetNextFib(pp, p);
        std::cout << fibI << " ";
    }
    return 0;
}

Mais c'est très moche, et cela complique notre logique main. Il vaudrait mieux ne pas avoir à se soucier de l'état de notre mainfonction.

Nous pourrions renvoyer un vectorde valeurs et utiliser un iteratorpour itérer sur cet ensemble de valeurs, mais cela nécessite beaucoup de mémoire en même temps pour un grand nombre de valeurs de retour.

Donc, revenons à notre ancienne approche, que se passe-t-il si nous voulons faire autre chose que d'imprimer les chiffres? Nous devions copier et coller tout le bloc de code mainet changer les instructions de sortie en tout ce que nous voulions faire. Et si vous copiez et collez du code, vous devriez être abattu. Vous ne voulez pas vous faire tirer dessus, n'est-ce pas?

Pour résoudre ces problèmes et éviter de se faire tirer dessus, nous pouvons réécrire ce bloc de code à l'aide d'une fonction de rappel. Chaque fois qu'un nouveau numéro de Fibonacci est rencontré, nous appelons la fonction de rappel.

void GetFibNumbers(size_t max, void(*FoundNewFibCallback)(size_t))
{
    if(max-- == 0) return;
    FoundNewFibCallback(0);
    if(max-- == 0) return;
    FoundNewFibCallback(1);

    size_t pp = 0;
    size_t p = 1;
    for(;;)
    {
        if(max-- == 0) return;
        int result = pp + p;
        pp = p;
        p = result;
        FoundNewFibCallback(result);
    }
}

void foundNewFib(size_t fibI)
{
    std::cout << fibI << " ";
}

int main(int argc, char *argv[])
{
    GetFibNumbers(6, foundNewFib);
    return 0;
}

Il s'agit clairement d'une amélioration, votre logique mainn'est pas aussi encombrée et vous pouvez faire tout ce que vous voulez avec les numéros de Fibonacci, simplement définir de nouveaux rappels.

Mais ce n'est pas encore parfait. Et si vous vouliez obtenir seulement les deux premiers numéros de Fibonacci, puis faire quelque chose, puis en obtenir plus, puis faire autre chose?

Eh bien, nous pourrions continuer comme nous l'avons été, et nous pourrions recommencer à ajouter l'état main, permettant à GetFibNumbers de démarrer à partir d'un point arbitraire. Mais cela va encore alourdir notre code, et il semble déjà trop gros pour une tâche simple comme l'impression de nombres de Fibonacci.

Nous pourrions mettre en œuvre un modèle de producteur et de consommateur via quelques fils. Mais cela complique encore plus le code.

Parlons plutôt des générateurs.

Python a une fonctionnalité de langage très agréable qui résout des problèmes comme ceux-ci appelés générateurs.

Un générateur vous permet d'exécuter une fonction, de vous arrêter à un point arbitraire, puis de reprendre là où vous vous étiez arrêté. Renvoyant à chaque fois une valeur.

Considérez le code suivant qui utilise un générateur:

def fib():
    pp, p = 0, 1
    while 1:
        yield pp
        pp, p = p, pp+p

g = fib()
for i in range(6):
    g.next()

Ce qui nous donne les résultats:

0 1 1 2 3 5

L' yieldinstruction est utilisée en conjonction avec des générateurs Python. Il enregistre l'état de la fonction et renvoie la valeur yeilded. La prochaine fois que vous appellerez la fonction next () sur le générateur, elle continuera là où le rendement s'est arrêté.

C'est de loin plus propre que le code de fonction de rappel. Nous avons un code plus propre, un code plus petit, et sans parler de code beaucoup plus fonctionnel (Python autorise des entiers arbitrairement grands).

La source

Brian R. Bondy
la source
3

Je crois que la première apparition d'itérateurs et de générateurs a eu lieu dans le langage de programmation Icon, il y a environ 20 ans.

Vous pouvez profiter de la vue d'ensemble d'Icône , qui vous permet d'envelopper votre tête autour d'eux sans vous concentrer sur la syntaxe (puisque l'Icône est une langue que vous ne connaissez probablement pas, et Griswold expliquait les avantages de sa langue aux personnes venant d'autres langues).

Après avoir lu quelques paragraphes, l'utilité des générateurs et des itérateurs pourrait devenir plus apparente.

Nosredna
la source
2

L'expérience des compréhensions de liste a montré leur utilité généralisée dans Python. Cependant, la plupart des cas d'utilisation n'ont pas besoin d'avoir une liste complète créée en mémoire. Au lieu de cela, ils n'ont qu'à répéter les éléments un par un.

Par exemple, le code de sommation suivant va créer une liste complète des carrés en mémoire, itérer sur ces valeurs et, lorsque la référence n'est plus nécessaire, supprimer la liste:

sum([x*x for x in range(10)])

La mémoire est conservée en utilisant une expression de générateur à la place:

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

Des avantages similaires sont conférés aux constructeurs d'objets conteneurs:

s = Set(word  for line in page  for word in line.split())
d = dict( (k, func(k)) for k in keylist)

Les expressions de générateur sont particulièrement utiles avec des fonctions telles que sum (), min () et max () qui réduisent une entrée itérable à une seule valeur:

max(len(line)  for line in file  if line.strip())

plus

Saqib Mujtaba
la source
1

J'ai mis en place ce morceau de code qui explique 3 concepts clés sur les générateurs:

def numbers():
    for i in range(10):
            yield i

gen = numbers() #this line only returns a generator object, it does not run the code defined inside numbers

for i in gen: #we iterate over the generator and the values are printed
    print(i)

#the generator is now empty

for i in gen: #so this for block does not print anything
    print(i)
Stefan Iancu
la source