{{tag>cours python}} ====== Expressions et fonctions génératrices ====== Précédemment nous avons vu les notions de compréhensions, compréhensions de liste, de *set* et de dictionnaire. Et nous savons que les compréhensions constituent un moyen extrêmement simple et expressif de parcourir des itérables et d'appliquer des traitements sur ces itérables. Ces compréhensions cependant ont un inconvénient majeur, c'est qu'elles créent des structures de données temporaires; une compréhension de liste va créer une liste temporaire. Or, si par exemple, on veut juste calculer, au final, uniquement la somme des éléments composant cette compréhension, on a créé une liste pour rien. Pour répondre à ce type de problématique il existe l' **expression génératrice**. Une **expression génératrice** utilise une syntaxe très proche d'une compréhension de liste, mais la différence, c'est que ce qui sera retourné sera un **itérateur** et non pas une liste, un set ou un dictionnaire. C'est donc quelque chose qui permet d'économiser énormément de mémoire tout en gardant toute la fonctionnalité d'une compréhension. Nous aborderons également la généralisation des expressions génératrices que l'on appelle **fonctions génératrices**. ===== Expression génératrice ===== # compréhension de liste simple # produit une liste en mémoire >>> carre = [x**2 for x in range(1000)] Cette liste est créée en mémoire et contient les carrés de tous les entiers allant de 0 à 999. Mais supposons maintenant que je veuille simplement calculer la somme de ces carrés. Pour calculer la somme des éléments d'un **itérable**, on peut utiliser la fonction *built-in* ''sum'': >>> sum(carre) 332833500 Pour calculer la somme de ces éléments, on peut éviter de créer une liste temporaire qui contient tous ces éléments. Pour cela on va utiliser une **expression génératrice**. # cette fois carre référence une expression génératrice. # L'expression génératrice est encadrée par des parenthèses >>> carre = ( x**2 for x in range(1000) ) # on peut s'en assurer >>> type(carre) generator À la place d'une liste, on obtient un objet *carré* qui s'appelle ''generator_object''. C'est en fait un itérateur qui va calculer à la volée le carré de chaque élément retourné par *range* de 1000. Comme *range* est également un objet qui ne crée pas de liste temporaire mais qui retourne, à chaque fois qu'on l'appelle, l'entier suivant, en fait, on va parcourir tous les éléments de cette expression génératrice sans jamais créer de structure temporaire. Maintenant, on peut calculer la somme de *carré* et l' on va obtenir le même résultat qu'avec la liste mais la grande différence, c'est qu' on ne créé pas de liste temporaire. On insistera sur le fait que cette expression génératrice est un **itérateur** ; par conséquent, si on calcule de nouveau somme de *carré*, on va obtenir 0 puisque cet itérateur a été consommé une première fois, il ne génère plus aucun élément. Mais comme la création d'un **générateur** est une opération extrêmement peu coûteuse puisque, lorsque je crée mon générateur, je ne fais absolument aucun calcul, et que les calculs seront faits à la volée, lorsque j'en ai besoin, je peux très facilement recréer un générateur et de nouveau calculer la somme des carrés. # l'expression génératrice est un itérateur # l'appel de la fonction sum le consomme >>> total = sum(carre) >>> print(total) 332833500 # un second appel sur le meme iterateur ne produira # plus de calcul >>> sum(carre) 0 Un intérêt des expressions génératrices, c'est qu'on peut les **chaîner**. Ça nous permet donc d'avoir une succession de traitements qui peut s'exécuter sans jamais avoir besoin de créer des objets temporaires. Imaginons un exemple: trouver tous les palindromes pour les carrés des nombres entre 0 et 999. Un palindrome, pour un nombre, c'est un nombre qu'on peut lire de gauche à droite ou de droite à gauche. Par exemple, 121 est un palindrome, qu'on le lise de gauche à droite ou de droite à gauche, ça fait toujours 121. # une première expression génératrice produisant les carrés # entre 0 et 999 >>> gen_carre = ( x**2 for x in range(1000) ) # une seconde expression génératrice, exploitant la première # elle identifiera les palindromes >>> palin = (x for x in gen_carre if str(x) == str(x)[::-1]) La seconde expression génératrice convertit l' entier en chaîne de caractères et compare si l'entier reversé est le même. Le renversement d'une chaîne de caractère est obtenu avec un slice de pas -1. %%[::-1]%%. Maintenant, si l'on souhaite obtenir ces palindromes dans une liste, on peut créer la liste de manière explicite: # a ce stade palin est une expression génératrice, # c'est un itérable mais aucun calcul n'a encore été fait >>> palin is iter(palin) True # Pour obtenir les palindromes, on crée la liste, ce qui # déclenche les calculs et produit les résultats >>> liste_palindromes = list(palin) >>> print(liste_palindromes) [0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, 69696, 94249, 698896] ===== Fonctions génératrices ===== Cette notion d'expression génératrice est très puissante et extrêmement souple. La bonne pratique en Python est de toujours manipuler des itérateurs le plus loin possible sans créer de structure de données temporaire et de ne créer la structure de données qu' à la fin par exemple, pour stocker les résultats. Évidemment, cette logique est de dire qu'en Python, tout est un objet donc tout prend de la place et il est inutile de créer des objets si on n'en a pas besoin; on ne les crée que quand c'est strictement nécessaire. Cependant, l'expression génératrice a une limitation, c'est que dans une expression génératrice exactement comme dans une compréhension de liste, on ne peut mettre qu'une expression. Or, certains traitements plus sophistiqués réclameront plus qu'une expression. Les expressions génératrices ont été généralisées dans un concept qu'on appelle **fonctions génératrices**. Vous pouvez créer des fonctions qui vont se comporter comme des expressions génératrices. Mais comme ce sera défini à l'intérieur d'une fonction, vous aurez toute la souplesse de ce que vous pouvez définir dans une fonction. Revenons sur la notion de **fonction**. Lorsque vous définissez une fonction, votre fonction retourne forcément une valeur. Si vous ne mettez pas d'instruction ''return'', elle va retourner l'objet *None* ; si vous mettez une instruction ''return'', elle va retourner le résultat de l'expression qui suit le mot clé ''return''. Une fonction, lorsqu'elle a retourné, détruit toutes ses **variables locales** et par conséquent, ne conserve aucun état entre deux appels. **Une fonction génératrice a un comportement qui est différent**. On définit une fonction génératrice comme toute autre fonction avec la même syntaxe, on lui donne ici le nom *gen* mais au lieu d'écrire un ''return'', on utilise l'instruction ''yield''. # définition d'une fonction génératrice >>> def gen(): ... print('instructions lues au premier appel') ... yield 10 ... print('instructions lues au deuxième appel') ... yield 20 ... print('instructions lues au troisième appel') ... yield 30 Regardons ce qu'est cet objet *gen*. *gen* est une fonction et lorsque on appelle cette fonction un **objet générateur** est produit. # un appel de la fonction instancie un objet generator # qui est un itérable >>> gen() # on peut vérifier facilement que generator est un itérable >>> g = gen() >>> g is iter(g) True >>> next(g) instructions lues au premier appel 10 >>> next(g) instructions lues au deuxième appel 20 >>> next(g) instructions lues au troisième appel 30 >>> next(g) StopIteration Traceback (most recent call last) in L'appel de la fonction *gen* a créée un objet. Cet objet est un **itérateur** que l'on manipule dans l'exemple ci-dessus comme tout autre itérateur. On peut directement le parcourir par appel de la fonction buil-tin *next*. On voit alors apparaître les premières instructions et la valeur retournée est celle présente après la première instruction *yield* rencontrée. Lors du rappelle de *next*, l'execution reprends là où elle s'était arrêtée, c'est-à-dire au *yield* de 10, et continue jusqu' à la prochaine instruction *yield* ou jusqu' à la fin du bloc d'instruction de la fonction génératrice et retourne alors l'exception *StopIteration* exactement comme un itérateur normal. Évidemment, en pratique, vous n'allez pas mettre une multitude de `yield` ; ça serait absolument peu pratique. En pratique, vous allez faire plutôt une **boucle** par exemple, une boucle `for` ou un `while`. Regardons maintenant un exemple un peu plus réaliste. Définissons un générateur que l'on appellera *carre*, et qui prend deux arguments *a* et *b*. Ce générateur produira les carrés entre les bornes a et b via une boucle for. # définition de la fonction génératrice (générateur) >>> def carre(a, b): ... for i in range(a,b+1): ... yield i**2 # on pourra produire les carrés au moment voulu ainsi >>> [ x for x in carre(0,10) ] [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100] Dans ce cas d'école extrêmement simple d'un générateur qui produit juste les carrés, on aurait pu mettre ça dans une expression génératrice. Passons à un cas un peu plus sophistiqué où il serait moins commode d'écrire ce fonctionnement dans une expression génératrice. Pour cela, on va créer un générateur nommé *palindrome* qui prend en argument directement un itérateur (ou **objet itérable**) et qui à l'aide d'une boucle vérifiera pour chaque élément si celui-ci est un palindrome. >>> def palindrome(it): ... for i in it: ... if( isinstance(i, (str, int)) and (str(i) == str(i)[::-1]) ): ... yield i Pour détailler un peu le code, l'appel à *isinstance* permet de vérifier que *i* est un objet de type chaîne de caractères ou entier. Si c'est bien le cas, une chaîne peut être produite par transtypage et comme précédemment la chaîne produite et renversée via le slice est comparée à la chaîne initiale. Si la correspondance est vérifiée, on retourne l'élément via l'instruction *yield*. # Comme le générateur accepte un itérable, on peut passer # en paramètre n'importe quel objet itérable comme une liste >>> p = palindrome([121, 10, 12321, 'abc', 'abba']) # Ou une expression génératrice >>> p2 = palindrome( x**2 for x in range(101) ) Évidemment, l'intérêt principal de la **fonction génératrice** n'est pas de prendre une liste temporaire comme proposé dans la première instruction de l'exemple ci-dessus mais de travailler directement sur un **itérateur** comme proposé dans la seconde instruction. Pour autre exemple, on aurait pu ouvrir un fichier qui contient, sur chaque ligne, un nombre ou une chaîne de caractères et passer directement cet objet fichier (qui est un itérateur) au générateur palindrome. Dans ce cas, aucune structure temporaire n'est créée, le générateur palindrome extrait les palindromes contenus dans ce fichier pour les placer dans la structure de données souhaitée. Lorsqu'on passe un **expression génératrice**, aucune structure de données temporaire n' est créée ; l' expression génératrice va générer les carrés un à un, elle va les passer un à un au générateur palindrome qui va ensuite produire les palindromes qui sont contenus dedans. Lorsque on passe une expression génératrice à une fonction, les parenthèses sont facultatives. ===== En résumé ===== Rappelons qu'en Python tout est un objet, donc tout a un surcoût mémoire. Python vous encourage à ne jamais créer de structure de données temporaire. C'est pourquoi nous avons ces notions **d'expression génératrice** ou de **fonction génératrice**. Comme ces objets produisent des *itérateurs* et que le protocole d'itération est universel en Python, vous pouvez utiliser ces expressions ou ces fonctions génératrices absolument dans tous les mécanismes d'itération en Python, les boucles *for* ou d'autres mécanismes d'itération. ===== Cascader deux générateurs avec 'yield from' ===== Commençons par définir une fonction génératrice: par exemple ici nous listons les diviseurs d'un entier, en excluant 1 et l'entier lui-même: def divs(n, verbose=False): for i in range(2, n): if n % i == 0: if verbose: print(f'trouvé diviseur {i} de {n}') yield i Maintenant supposons que l'on veuille écrire une fonction génératrice qui énumère tous les diviseurs de tous les diviseurs d'un entier. Il s'agit donc, en sorte, d'écrire une fonction génératrice qui en appelle une autre: ici elle même. Le code suivant est une proposition naïve qui ne fonctionne pas: # proposition d'implementation ne fonctionannt pas >>> def divdivs(n): ... for i in divs(n): ... divs(i) # L'appel de ce code lève une exception >>> for i in divdis(28): ... print(i) TypeError: 'NoneType' object is not iterable Ici *divdivs* est perçue comme une fonction normale, en effet son code ne contient pas d'instruction yield caractéristique des fonctions génératrices, lorsqu'on l'appelle elle ne retourne rien, donc None ; et c'est sur ce None qu'on essaie de faire la boucle for qui donc échoue. Si maintenant on essaye d'utiliser juste *yield*, le résultat n'est pas celui que l'on souhaite. En effet, c'est logique, chaque yield dans divdivs() correspond à une itération de la boucle. Bref, il nous manque quelque chose dans le langage pour arriver à faire ce qu'on veut. >>> def divdivs(n): ... for i in divs(n): ... yield divs(i) >>> for i in divdivs(28): ... print(i) La construction du langage qui permet de faire ceci s'appelle **yield from**. >>> def divdivs(n): ... for i in divs(n): ... yield from divs(i, verbose=True) >>> for i in divdivs(28): ... print(i)