Skip to content

TD12. Redonnons la main

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.

Introduction

Vidéo d'introduction à regarder avant de commencer le TD :

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
#!/usr/bin/env python3

import sys

def traite_fichier(nom_fichier):
    fichier = open(nom_fichier, "r")
    resultats = []
    for ligne in fichier:
        ligne_decoupee = ligne.split(" ")
        prenom = ligne_decoupee[0]
        note = int(ligne_decoupee[1])
        resultats.append((prenom, note))
    fichier.close()
    return resultats

def cherche_note(prenom, prenoms_notes):
    for resultat in prenoms_notes:
        if resultat[0] == prenom:
            return resultat[1]
    return None

def get_note():
    if len(sys.argv) != 3:
        print("Usage :", sys.argv[0], "nom_fichier prenom")
        return
    prenoms_notes = traite_fichier(sys.argv[1])
    prenom = sys.argv[2]
    print("La note de", prenom, "est", cherche_note(prenom, prenoms_notes))

if __name__ == "__main__":
    get_note()

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
#!/usr/bin/env python3

import sys

def traite_fichier(nom_fichier):
    fichier = open(nom_fichier, "r")
    resultats = []
    for ligne in fichier:
        ligne_decoupee = ligne.split(" ")
        prenom = ligne_decoupee[0]
        note = int(ligne_decoupee[1])
        resultats.append((prenom, note))
    fichier.close()
    return resultats

def calcule_moyenne(prenoms_notes):
    somme = 0
    nb_etudiants = 0
    for resultat in prenoms_notes:
        somme += resultat[1]
        nb_etudiants += 1
    return somme / nb_etudiants

def teste():
    """Teste les fonctions ci-dessus."""
    if len(sys.argv) != 2:
        print("Usage :", sys.argv[0], "nom_fichier")
    else:
        prenoms_notes = traite_fichier(sys.argv[1])
        print("La note moyenne est", calcule_moyenne(prenoms_notes))

if __name__ == "__main__":
    teste()

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, il peut y avoir un problème de mémoire car une list de tous les étudiants est construite.

Dans le programme précédent cherchant un étudiant dans un fichier, il y a également le problème de mémoire.

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 ?

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
#!/usr/bin/env python3

"""Cherche la note d'un étudiant depuis son prénom"""

import sys

def cherche_note(nom_fichier, prenom_a_chercher):
    """Traitement fichier et recherche fusionnés"""
    fichier = open(nom_fichier, "r")
    for ligne in fichier:
        ligne_decoupee = ligne.split(" ")
        prenom = ligne_decoupee[0]
        note = int(ligne_decoupee[1])
        if prenom == prenom_a_chercher:
            fichier.close()
            return note
    fichier.close()
    return None

def get_note():
    if len(sys.argv) != 3:
        print("Usage :", sys.argv[0], "nom_fichier prenom")
        return
    fichier = sys.argv[1]
    prenom = sys.argv[2]
    print("La note de", prenom, "est", cherche_note(fichier, prenom))

if __name__ == "__main__":
    get_note()

Question 4

Quel est l'inconvénient de cette solution ?

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 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
#!/usr/bin/env python3

import sys

def traite_fichier(fichier):
    for ligne in fichier:                                      # tf1 (bof, non ?)
        ligne_decoupee = ligne.split(" ")                      # tf2
        prenom = ligne_decoupee[0]                             # tf3
        note = int(ligne_decoupee[1])                          # tf4
        yield (prenom, note)                                   # tf5

def cherche_note(prenom, resultats):
    for resultat in resultats:                                 # cn1
        if resultat[0] == prenom:                              # cn2
            return resultat[1]                                 # cn3
    return None                                                # cn4

def get_note():
    if len(sys.argv) != 3:                                     # gn1
        print("Usage :", sys.argv[0], "nom_fichier prenom")    # gn2
        return                                                 # gn3
    fichier = open(sys.argv[1], "r")                           # gn4
    iterateur_prenoms_notes = traite_fichier(fichier)          # gn5
    prenom = sys.argv[2]                                       # gn6
    note = cherche_note(prenom, iterateur_prenoms_notes)       # gn7
    print("La note de", prenom, "est", note)                   # gn8
    fichier.close()                                            # gn9

if __name__ == "__main__":                                     # 1
    get_note()                                                 # 2

Question 1

Analyser attentivement le code ci-dessus. 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.

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.

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é. 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 tel sorte que le numéro de la prochaine ligne de code à exécuter soit le numéro de la ligne suivant le yield.

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 ?

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
#!/usr/bin/env python3

import sys

def traite_fichier(nom_fichier):
    fichier = open(nom_fichier, "r")
    for ligne in fichier:
        ligne_decoupee = ligne.split(" ")
        prenom = ligne_decoupee[0]
        note = int(ligne_decoupee[1])
        yield (prenom, note)
    fichier.close()

def calcule_moyenne(resultats):
    somme = 0
    nb_etudiants = 0
    for resultat in resultats:
        somme += resultat[1]
        nb_etudiants += 1
    return somme / nb_etudiants

def teste():
    """Teste les fonctions ci-dessus."""
    if len(sys.argv) != 2:
        print("Usage :", sys.argv[0], "nom_fichier")
    else:
        iterateur_prenoms_notes = traite_fichier(sys.argv[1])
        print("La note moyenne est", calcule_moyenne(iterateur_prenoms_notes))

if __name__ == "__main__":
    teste()

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.

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
#!/usr/bin/env python3

"""On peut avoir uen fonction génératrice n'utilisant pas de boucles."""

def get_jours_semaine():
    """Fonction génératrice des jours de la semaine."""
    yield "lundi"
    yield "mardi"
    yield "mercredi"
    yield "jeudi"
    yield "vendredi"
    yield "samedi"
    yield "dimanche"

def affiche_jours():
    """Affiche les jours de la semaine."""
    iterateur_jours = get_jours_semaine()
    for jour in iterateur_jours:
        print(jour)

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
#!/usr/bin/env python3

"""Petit exemple pour illustrer le contexte de CHAQUE itérateur 1 et 2"""

def get_first_five():
    """Fonction génératrice des 5 premiers nombres."""
    yield "one"
    yield "two"
    yield "three"
    yield "four"
    yield "five"

def affiche():
    """Affiche des trucs en utilisant DEUX itérateurs."""
    iterateur_1 = get_first_five()
    iterateur_2 = get_first_five()

    print("De l'itérateur 1", next(iterateur_1))
    print("De l'itérateur 1", next(iterateur_1))
    print("De l'itérateur 2", next(iterateur_2))
    print("De l'itérateur 1", next(iterateur_1))

if __name__ == "__main__":
    affiche()

Cliquez ici pour révéler la correction. Pour répondre à la question il faut bien avoir en tête :

  • le fait que la fonction next permet de récupérer le prochain élément d'un itérateur ;
  • 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.

Voici donc ce qu'affiche le code ci-dessus :

1
2
3
4
De l'itérateur 1 one
De l'itérateur 1 two
De l'itérateur 2 one
De l'itérateur 1 three

Exercice 4 : analyse de code

Question

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
#!/usr/bin/env python3

"""Train reading someone else (bad) code"""

def mystery_function(first_parameter, second_parameter, everything):
    """What am I doing?"""
    for variable in first_parameter:
        everything.append(variable[second_parameter])
        yield variable[second_parameter]

def main():
    """Script's entry point"""
    a_list = []
    something = mystery_function([("to", 12), ("ti", 17), ("ta", 47)],
                                 1, a_list)
    print("type of something is", type(something))
    for element in something:
        print(element, end=' ')
    print()
    something_else = mystery_function(("to", "ti", "\ufdfd what is that?"),
                                      0, a_list)
    print("type of something_else is", type(something_else))
    for element in something_else:
        print(element, end=' ')
    print()
    print(a_list)
    other_thing = mystery_function({(1, 2, 3), (4, 5, 6), (7, 8)},
                                   2, a_list)
    print("type of other_thing is", type(other_thing))
    for element in other_thing:
        print(element, end=' ')
    print()

if __name__ == "__main__":
    main()

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
type of something is <class 'generator'>
12 17 47
type of something_else is <class 'generator'>
t t ﷽
[12, 17, 47, 't', 't', '﷽']
type of other_thing is <class 'generator'>
3 Traceback (most recent call last):
  File "./mystery.py", line 32, in <module>
    main()
  File "./mystery.py", line 27, in main
    for element in other_thing:
  File "./mystery.py", line 8, in mystery_function
    everything.append(variable[second_parameter])
IndexError: tuple index out of range

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, les tuple et les set sont tous "parcourables" avec une boucle for. Cela veut dire que l'on peut récupérer un itérateur sur leur contenu. Techniquement en Python, on dit que ces objets sont des iterables ;

  • en Python tout est référence via le paramètre everything ;

  • 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

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 ?

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.