Concepts Python avancés

Itérateurs et générateurs

GALODE Alexandre

Il est des concepts en Python que l'on utilise sans réellement le savoir. Et pourtant, pour une bonne maîtrise de notre langage préféré, et pour optimiser notre code, il est indispensable de savoir comment ces concepts « camouflés » fonctionnent.

Je vous invite ici à en découvrir un de plus.

Commentez

- Titre : Concepts Python avancés

- Auteur : GALODE Alexandre

- Parution : 9 décembre 2015

- Public visé :

- Licence : Le contenu de cet article est rédigé par Alexandre GALODE et est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 non transposé. Les logos Developpez.com, en-tête, pied de page, css, et look & feel de l'article sont Copyright ® 2013 Developpez.com.

Sommaire

- I. Introduction

- II. Les itérateurs

- II-A. Présentation

- II-B. La fonction iter() et la méthode next()

- II-C. Créons notre propre itérateur

- III. Les générateurs

- III-A. Présentation

- III-B. Le mot clé « yield »

- IV. Le module itertools

- IV-A. Présentation

- IV-B. Possibilités offertes

- IV-B-1. Itérateurs infinis

- IV-B-2. Itérateurs finis

- IV-B-3. Générateurs combinatoires

- IV-C. Le cas product()

- V. Conclusion

- VI. Remerciements

I - Introduction

Les itérateurs et les générateurs sont les concepts qui se cachent derrière la possibilité de parcourir une liste dans une boucle for, les caractères d'une chaîne de caractères, etc.

Si l'on peut se contenter de se servir des fonctionnalités de base, il arrive toujours un moment dans la vie du développeur où il devra passer au stade supérieur et se plonger dans le fonctionnement de ces fonctionnalités.

Je vous propose ici de passer ce stade et d'approfondir la compréhension du fonctionnement des itérateurs et générateurs.

II - Les itérateurs

II-A - Présentation

Un itérateur est un objet permettant de parcourir tout autre objet dit « itérable ». Les exemples les plus connus d'objets itérables sont les chaines de caractères, les listes, les fichiers… Bref tout objet que l'on peut parcourir via un index (appelés séquences : cf. documentation officielle).

Les itérateurs sont très présents dans Python, et toute personne ayant codé un minimum en Python les a déjà rencontrés.

Le plus grand avantage des itérateurs est leur faible consommation ressource.

II-B - La fonction iter() et la méthode next()

1. chaine = 'hello world'

2. for lettre in chaine:

3. print(lettre)

Voici un exemple typique de code s'appuyant sur un itérateur. Dans cet exemple, la boucle FOR récupère l'itérateur de la liste et l'utilise afin de parcourir la liste.

Python possède une fonction faisant partie des Built-In (fonctions de base) nommée « iter() ». Cette fonction permet de créer un itérateur sur un objet itérable.

Dans notre cas, je vous invite à saisir le code suivant.

1. chaine = 'hello world'

2. iterateur = iter(chaine)

3. print(iterateur)

Certains objets tels les listes possèdent déjà leur propre itérateur accessible via __iter__(). On obtient alors un itérateur plus spécifique. Le code vu à l'instant peut ainsi s'écrire :

1. chaine = ['h','e','l','l','o',' ','w','o','r','l','d']

2. iterateur = chaine.__iter__()

3. print(iterateur)

Vous voyez ici que vous avez bien récupéré un objet de type « iterator ». L'ensemble des objets de type « iterator » possède une fonction « next() », qui permet de se déplacer dans l'objet itérable.

Reprenons notre code initial, en le modifiant légèrement.

1. chaine = 'Hello World'

2. iterateur = iter(chaine)

3. for i in range(len(chaine)):

4. print(iterateur.next())

Si vous exécutez ce code, vous vous rendrez compte que le résultat est identique au code initial. Que se passe-t-il donc dans ce code ? Et à quoi correspond la méthode next() ?

Tout d'abord, nous créons un itérateur sur notre chaîne de caractères. Dans la boucle FOR, le seul lien que nous prenons en compte est la longueur de cette chaîne de caractères.

Au niveau du print, nous utilisons une fonctionnalité des itérateurs : la méthode « next() ». Cette méthode permet de déplacer l'index de l'itérateur sur l'objet.

À la création de l'itérateur, cet index peut être considéré comme valant « -1 ». L'appel à la méthode « next() » déplace le curseur d'une unité, puis renvoie la valeur lue à cet index.

II-C - Créons notre propre itérateur

Maintenant que nous avons vu les bases des itérateurs, je vous propose de créer notre propre itérateur afin de comprendre, entre autres, comment ce dernier sait quand s'arrêter.

Répondons déjà à cette dernière interrogation. Lorsque nous avons atteint le dernier élément, un nouvel appel à « next() » provoquera simplement une exception de type « StopIteration ». Il suffit alors d'intercepter cette exception pour arrêter l'itération.

1. class MonIterateur(object):

2. def __init__(self, obj):

3. self.obj = obj

4. self.length = len(obj)

5. self.count = 0

7. def __iter__(self):

8. return self

10. def next(self):

11. if self.count > self.length:

12. raise StopIteration

14. else:

15. result = self.obj[self.count]

17. self.count += 2

18. return result

20. if __name__ == "__main__":

21. chaine = "hello_world"

22. ma_classe_iterateur = MonIterateur(chaine)

23. iterateur = ma_classe_iterateur.__iter__()

24. try:

25. for idx in range(len(chaine)):

26. print(iterateur.next())

27. except StopIteration:

28. print("fin d'iteration")

Cet exemple montre comment arrêter une itération. Outre cela, nous pouvons également voir qu'au sein de la fonction « next » de notre itérateur maison, nous avons choisi d'utiliser un pas de deux caractères.

De même, nous aurions pu effectuer un traitement sur la donnée lue avant de la renvoyer.

Enfin, notez que l'on peut simplifier le code du « if __name__... » avec les lignes suivantes.

1. if __name__ == "__main__":

2. chaine = "hello_world"

3. ma_classe_iterateur = MonIterateur(chaine)

4. try:

5. for lettre in ma_classe_iterateur:

6. print(lettre)

7. except StopIteration:

8. print("fin d'iteration")

III - Les générateurs

III-A - Présentation

Les générateurs sont des objets Python permettant de créer et de manipuler plus aisément les itérateurs, en plaçant une couche d'abstraction supplémentaire au niveau code.

Il existe deux façons de créer des générateurs. Ils consomment peu de ressources mémoire. Cette faible consommation est due au fait que lorsqu'une valeur est demandée au générateur, il va la « générer », puis simplement la retourner, sans rien conserver en mémoire.

Ils ont été introduits par la PEP 255 et se basent sur l'utilisation du mot clé « yield ».

III-B - Le mot clé « yield »

Le mot clé « yield » est à la base des générateurs. C'est grâce à lui qu'un générateur peut fonctionner.

Il peut être assimilé à un « return », à deux principales différences près. Alors qu'un return vous renverra un ensemble de valeurs (sous forme de liste, chaine de caractères…) et mettra fin à l'exécution de la procédure/fonction/..., un yield vous retournera une valeur, puis se mettra en pause, en attendant l'appel suivant.

Je vous invite à exécuter le code suivant afin de mieux comprendre.

1. def mon_generateur():

2. yield 'h'

3. yield 'e'

4. yield 'l'

5. yield 'l'

6. yield 'o'

7. yield ' '

8. yield 'w'

9. yield 'o'

10. yield 'r'

11. yield 'l'

12. yield 'd'

14. if __name__ == ('__main__'):

15. generateur = mon_generateur()

16. print generateur

17. for value in generateur:

18. print(value)

Que constatons-nous ? Tout d'abord generateur est bien un objet de type « generator ». Ensuite, au niveau du for, nous appelons une première fois notre objet generateur.

Rappelons que l'objet generateur fonctionne selon notre générateur défini dans « mon_generateur ».

Au niveau de la boucle for, au premier appel, il exécute la première ligne, qu'il faut ici interpréter comme « retourne la valeur h », puis le générateur se met en pause. Au second appel, il se réveille de sa position et exécute la ligne suivante, l'équivalent d'un « retourne la valeur e » puis se met en pause. Et ainsi de suite jusqu'à la fin.

Cela est simplifiable de la manière suivante :

1. def mon_generateur(data):

2. for value in data:

3. yield value

5. if __name__ == ('__main__'):

6. generateur = mon_generateur("hello world")

7. print generateur

8. for value in generateur:

9. print(value)

Maintenant, faisons la liaison avec les itérateurs.

1. def mon_generateur(data):

2. iterateur = iter(data)

3. for idx in range(len(data)):

4. yield iterateur.next()

6. if __name__ == ('__main__'):

7. generateur = mon_generateur("hello world")

8. print generateur

9. for value in generateur:

10. print(value)

Ce code réalise la même chose que précédemment, mais en mettant explicitement en vue l'itérateur.

Avouez tout de même que les générateurs permettent de simplifier l'écriture du code. Qui plus est, étant un niveau plus bas dans le fonctionnement du code, nous pourrions réaliser des traitements plus en amont (exemple ici : remplacer les lettres L par le chiffre 1).

À tout moment, vous pouvez interrompre le générateur via la méthode « close() ».

1. def mon_generateur(data):

2. for value in data:

3. yield value

5. if __name__ == ('__main__'):

6. generateur = mon_generateur("hello world")

7. print generateur

8. for value in generateur:

9. if value == 'w':

10. generateur.close()

11. else:

12. print(value)

IV - Le module itertools

Maintenant que nous avons vu itérateurs et générateurs, il faut mettre en évidence ce qui constitue à la fois leur principal avantage et principal défaut : rien n'est gardé en mémoire, tout est volatil.

De fait, il peut s'avérer difficile dans certains cas de prendre conscience de l'ampleur du travail à effectuer et de savoir comment l'optimiser proprement.

C'est là qu'intervient le module itertools.

IV-A - Présentation

Comme son nom l'indique, le module itertools fournit un ensemble d'outils pour itérateurs. Plus précisément, il met à disposition un ensemble de fonctionnalités permettant de simplifier tout un ensemble d'opérations, comme une double boucle for imbriquée.

Il est natif en Python et est disponible du moment que Python l'est.

IV-B - Possibilités offertes

IV-B-1 - Itérateurs infinis

Itérateurs

Arguments

Description

Exemple applicatif

count()

start [,step]

Compte à partir de start, par pas de « step » (par défaut à 1)

1. from itertools import *

3. a = count(10, 2)

4. print(a.next())

5. print(a.next())

6. print(a.next())

cycle()

p

Boucle indéfiniment sur p

1. from itertools import *

3. a = cycle('ABC')

4. print(a.next())

5. print(a.next())

6. print(a.next())

7. print(a.next())

8. print(a.next())

9. print(a.next())

repeat()

element [, n]

Répète n fois l'élément

1. from itertools import *

3. a = repeat(10, 3)

4. print(a.next())

5. print(a.next())

6. print(a.next())

7. print(a.next())

IV-B-2 - Itérateurs finis

Itérateurs

Arguments

Description

Exemple applicatif

chain()

p, q, ...

Enchaîne les différentes séquences les unes à la suite des autres

1. from itertools import *

3. a = chain('ABC', 'DEF')

4. print(a.next())

5. print(a.next())

6. print(a.next())

7. print(a.next())

8. print(a.next())

9. print(a.next())

compress()

data, selectors

Permet d'effectuer un filtrage. Plus précisément, cette fonction effectue un ET logique entre les deux listes. Pour rappel, en Python, est considérée comme « vrai » toute valeur différente de 0 et de False.

1. from itertools import *

3. a = compress('ABCDEF', [2,0,True,0,1,1])

4. print(a.next())

5. print(a.next())

6. print(a.next())

7. print(a.next())

dropwhile()

pred, seq

Ne renvoie rien tant que le prédicat est vrai

1. from itertools import *

3. a = dropwhile(lambda x: x<5, [1,4,6,4,1])

4. print(a.next())

5. print(a.next())

6. print(a.next())

ifilter()

pred, seq

Renvoie des éléments vérifiant le prédicat

1. from itertools import *

3. a = ifilter(lambda x: x%2, range(10))

4. print(a.next())

5. print(a.next())

6. print(a.next())

7. print(a.next())

8. print(a.next())

ifilterfalse()

pred, seq

Renvoie des éléments ne vérifiant pas le prédicat

1. from itertools import *

3. a = ifilterfalse(lambda x: x%2, range(10))

4. print(a.next())

5. print(a.next())

6. print(a.next())

7. print(a.next())

8. print(a.next())

islice()

seq, [start,] stop [, step]

Renvoie les données respectant les instructions start, stop, step fournies

1. from itertools import *

3. start = 2

4. stop = 5

5. step = 2

6. a = islice('AHCDEFG', start, stop, step)

7. print(a.next())

8. print(a.next())

9. print(a.next())

imap()

func, p, q

Effectue un func(px,qx)

1. from itertools import *

2. from math import *

4. a = imap(pow, (2,3,10), (5,2,3))

5. print(a.next())  # revient a faire pow(2,5)

6. print(a.next())  # revient a faire pow(3,2)

7. print(a.next())  # revient a faire pow(10,3)

takewhile()

pred, seq

Renvoie des éléments tant que le prédicat est vérifié

1. from itertools import *

3. a = takewhile(lambda x: x<5, [1,4,6,4,1])

4. print(a.next())

5. print(a.next())

6. print(a.next())

izip()

p, q, ...

Renvoie des tuples (px,qx) tant que des paires peuvent être formées

1. from itertools import *

3. a = izip('ABCD', 'xy')

4. print(a.next())

5. print(a.next())

6. print(a.next())

izip_longest()

p, q, …, fillvalue='-'

Renvoie des tuples (px,qx) en utilisant une valeur de substitution en cas de besoin.

1. from itertools import *

3. a = izip_longest('ABCD', 'xy', fillvalue='-')

4. print(a.next())

5. print(a.next())

6. print(a.next())

IV-B-3 - Générateurs combinatoires

Itérateurs

Arguments

Description

Exemple applicatif

product()

p, q, ...[repeat=1]

Permet de générer des combinaisons, par exemple entre deux listes, remplaçant ainsi une double boucle FOR

1. from itertools import *

3. list_01 = ['A', 'B', 'C', 'D']

4. list_02 = ['E', 'F', 'G', 'H']

6. for value in product(list_01, list_02):

7. print(value)

permutations()

p[, r]

Permet de générer des tuples de longueur r, sans répétition

1. from itertools import *

3. for value in permutations('ABCD', 2):

4. print(value)

combinations()

p, r

Permet de générer des tuples de longueur r, triés, sans répétition

1. from itertools import *

3. for value in combinations('ABCD', 2):

4. print(value)

De prime abord, les fonctions permutations() et combinations() peuvent sembler similaires. Cependant, l'exécution de l'exemple suivant vous donnera un meilleur aperçu des différences.

1. from itertools import *

3. for value in permutations('ABCD', 2):

4. print(value)

7. print("**********************************")

8. for value in combinations('ABCD', 2):

9. print(value)

Vous constaterez que permutations() vous renvoie l'ensemble des permutations possibles, en tenant compte de l'ordre (ex. : ('A','B') et ('B','A') seront tous deux renvoyés), alors que combinations() ne tiendra pas compte de l'ordre (ex. : ('A','B') et ('B','A') seront considérés comme équivalents et seul l'un d'eux sera renvoyé).

IV-C - Le cas product()

« product() » fait partie des fonctions que vous verrez souvent. En effet, il permet de remplacer avantageusement une double boucle for imbriquée.

Pour mieux comprendre l'intérêt d'utiliser le module itertools, je vous propose d'exécuter le code suivant.

1. from itertools import *

2. import time

4. list_01 = ['A', 'B', 'C', 'D']

5. list_02 = ['E', 'F', 'G', 'H']

7. start_01 = time.time()

8. for value in product(list_01, list_02):

9. print(value)

10. stop_01 = time.time()

12. start_02 = time.time()

13. for value_01 in list_01:

14. for value_02 in list_02:

15. print(value_01, value_02)

16. stop_02 = time.time()

18. print(stop_01-start_01)

19. print(stop_02-start_02)

Comme on peut le constater, le code avec itertools.product() est plus rapide d'environ 20 %. À l'échelle de notre exemple, cela est négligeable. Mais dans des traitements de masse, cela peut changer énormément les choses. Sans parler du gain en lisibilité et en simplicité.

V - Conclusion

Comme nous venons de le voir ensemble, le fonctionnement des itérateurs et des générateurs est élémentaire, et n'a rien de complexe.

En revanche, si un débutant peut très bien se passer de les connaître, ce n'est pas le cas des développeurs confirmés.

En effet, ce concept Python pourra leur permettre d'optimiser profondément leur code et s'avérer indispensable dans certains cas.

Côté module, itertools est un grand classique dont il faut au minimum connaître le nom et les possibilités. D'autant plus que dans certains algorithmes, il se révélera vite incontournable. Sans compter que, comme vu il y a peu, le code n'en devient que plus lisible.

J'espère que ce petit tutoriel vous permettra désormais d'améliorer votre code et d'appréhender plus facilement certaines erreurs que vous pourriez commettre.

VI - Remerciements

- Lolo78

- ClaudeLELOUP