TD12. Redonnons la main
Le sujet de ce TD est disponible au format pdf ici.
L'objectif de ce TD est d'introduire les générateurs Python, c'est à dire le mot-clef yield
, et le concept fondamental d'itérateur qui se cache derrière ainsi que le concept d'itérable spécifique à Python.
Exercice 1 : quel est le problème ?
Question 1
Analysez attentivement le code ci-dessous. Combien de lignes du fichier d'entrée faut-il lire pour que le programme affiche la note de l'étudiant situé en toute première position dans le fichier ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
Correction question 1
Cliquez ici pour révéler la correction.
Le problème de ce code vient du fait que tout le fichier doit être traité avant de commencer la recherche. Si ce dernier est gigantesque alors que l'étudiant cherché se trouve au début, on perd du temps pour rien.
Question 2
Cette fois, on cherche à calculer la moyenne des notes se trouvant dans le fichier. Que peut-on dire sur l'espace mémoire occupé par ce programme ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
Correction question 2
Cliquez ici pour révéler la correction.
Ici il n'y a plus le problème de perte de temps car dans tous les cas l'intégralité du fichier doit être traité.
Néanmoins, une list
de tous les étudiants est construite alors que cela n'est pas nécessaire.
On utilise donc de la mémoire pour stocker tous les étudiants dans cette liste alors que cela n'est pas nécessaire.
Dans le programme précédent cherchant un étudiant dans un fichier, il y a également de l'utilisation mémoire inutile..
Question 3
Comment corriger le problème de calculs inutiles et de mémoire dans le cas de la recherche d'un étudiant uniquement avec ce que nous avons vu jusqu'ici, c'est-à-dire sans avoir recours à yield
?
Correction question 3
Cliquez ici pour révéler la correction.
Il suffit de fusionner la recherche avec le traitement du fichier.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
Question 4
Quel est l'inconvénient de cette solution ?
Correction question 4
Cliquez ici pour révéler la correction.
Le code est moins bien structuré car le traitement du fichier et la recherche sont mélangés dans une même fonction. Ici ce n'est pas trop grave car le code est simple, mais dans du vrai code ça peut vite devenir très gênant pour la lisibilité/maintenance.
Exercice 2 : il n'y a pas de problème, il n'y a que des solutions
Voici donc comment, à l'aide de l'utilisation d'un yield
Python, avoir une recherche d'étudiant dans laquelle :
- nous ne faisons aucun calcul pour rien ;
- nous ne créons pas de
list
d'étudiants, donc utilisation mémoire constante ; - le traitement du fichier et la recherche sont séparés dans deux fonctions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
Question 1
Analyser attentivement le code ci-dessus.
En essayant de "deviner" ce que fait le yield
, prendre quelques minutes pour dérouler le programme sur papier en écrivant les numéros de lignes successivement exécutées dans le cas d'un appel correct, c'est à dire avec un fichier qui existe et un nom d'étudiant qui existe en troisième position du fichier.
Correction question 1
Cliquez ici pour révéler la correction.
Voici l'ordre d'exécution :
- 1 2 gn1 gn4 gn5 gn6 gn7
- cn1 tf1 tf2 tf3 tf4 tf5 cn2
- cn1 tf1 tf2 tf3 tf4 tf5 cn2
- cn1 tf1 tf2 tf3 tf4 tf5 cn2 cn3
- gn8 gn9
Maintenant que nous avons vu le mot clef yield
ainsi que son fonctionnement, il nous faut définir la notion fondamentale d'itérateur qui se cache derrière.
DÉFINITION D'UN ITÉRATEUR : état + fonction permettant d'avoir le prochain élément. Ce concept existe on delà du langage python.
DÉFINITION D'UN ITÉRABLE : instance Python à partir de laquelle on peut récupérer un itérateur, et donc que l'on peut parcourir. Les boucles for Python travaillent sur un itérable. Et les itérateurs sont eux-mêmes des itérables.
DÉFINITION D'UN GÉNÉRATEUR : fonction Python avec un yield
, permettant de créer très facilement des itérateurs (contrairement à d'autres langages comme Java, C++ ou encore plus difficile C).
Les générateurs Python sont aussi appelés des fonctions génératrices. À chaque fois qu'une telle fonction est appelée, son code n'est pas exécuté ; un nouvel itérateur est simplement créé et renvoyé. Conceptuellement, l'état de cet itérateur contient le numéro de la prochaine ligne de code à exécuter. Initialement, ce numéro désigne la première ligne de la fonction génératrice.
Ensuite, à chaque fois que le prochain élément de l'itérateur est demandé, ce qui est fait par exemple dans notre dos quand on écrit for elem in mon_iterateur
, alors le code de la fonction génératrice est exécuté jusqu'au prochain yield
et son état est mis à jour de telle sorte que le numéro de la prochaine ligne de code à exécuter soit le numéro de la ligne suivant le yield
.
Voici également deux vidéos qui peuvent vous éclairer.
Elles présentent de deux manières différentes le mot-clef yield
et les concepts qui se cachent derrière :
Question 2
À l'aide d'un générateur, réécrire le programme qui calcule la moyenne des notes. Quel est l'avantage par rapport au calcul de moyenne de l'exercice 1 ?
Correction question 2
Cliquez ici pour révéler la correction.
Voici le code de correction :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
L'avantage est que dans cette version il n'y pas de création de la list
de tous les étudiants en mémoire.
Vidéo de correction complète des exercices 1 et 2 :
Exercice 3 : générer les jours de la semaine.
Question 1
Écrire une fonction génératrice renvoyant un itérateur sur les chaînes de caractères représentant les jours de la semaine.
Correction question 1
Cliquez ici pour révéler la correction.
L'objectif de cet exercice est d'enfoncer encore le clou sur le yield
, en montrant qu'il n'y a pas forcément de boucle dans une fonction génératrice (c'est à dire une fonction avec des yield
).
La preuve en regardant la correction ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
Vidéo de correction de l'exercice 3 :
Question 2
Qu'affiche le programme suivant ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
Correction question 2
Cliquez ici pour révéler la correction.
Pour répondre à la question il faut :
- savoir que la fonction
next
permet de récupérer le prochain élément d'un itérateur ; - avoir compris le principe d'une fonction génératrice qui renvoie un nouvel itérateur à chaque fois qu'elle est appelée et qui sera exécutée morceaux par morceaux quand les éléments de cet itérateur seront demandés via là fonction
next
appelée explicitement ou implicitement si l'itérateur est utilisé dans une boucle.
Voici donc ce qu'affiche le code ci-dessus :
1 2 3 4 |
|
Exercice 4 : analyse de code
Question 1
Qu'affiche le programme ci-dessous ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
Correction question 1
Cliquez ici pour révéler la correction.
Voici ce qu'affiche ce programme :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Et voici ce qu'il faut en retenir :
-
pour bien comprendre la notion des fonctions génératrice il faut dérouler le code ligne par ligne ;
-
on voit bien qu'un appel à une fonction génératrice n'exécute pas la fonction mais renvoie simplement un itérateur (qui en pratique est de type
class 'generator
comme l'indique le programme, mais ceci est un détail d'implémentation, il faut juste retenir que c'est un itérateur tel que nous les avons définit dans ce TD) ; -
les
list
, lestuple
et lesset
sont tous des itérables et donc "parcourables" avec une bouclefor
comme nous le savons déjà. Cela veut donc dire que l'on peut récupérer un itérateur sur leur contenu. -
il faut continuer à s'entraîner à lire les messages d'erreur ;
-
il existe de très nombreux caractères unicode.
Vidéo de correction de l'exercice 4 :
Exercice 5 : quand aurions nous pu/dû utiliser yield
? (pour aller plus loin)
Question 1
Chercher dans ses notes, sa mémoire, son ordinateur, à quels endroits nous aurions pu/dû utiliser yield
dans le cadre des TD et TP BPI en justifiant pourquoi ?
Correction question 1
Cliquez ici pour révéler la correction.
Voici une liste (à compléter), des endroits ou on aurait du faire du yield
:
- dans nos listes chaînées pour récupérer toutes les cellules ;
- dans blobwar quand on récupère les voisins pour ne pas créer toute la
list
des voisins ; - dans les sous-suite monotones pour avoir du code plus lisible ;
- dans mots suivants pour ne pas créer la
list
de tous les voisins.