L3 MIASHS, Algorithme et Programmation 3, année 2024

Iterateur

Un itérateur en Python est un objet qui représente une séquences (possiblement infinie) qui est déroulée. Cet objet possède deux méthodes:

Une méthode __next__: va retourner l’élément suivant dans la séquence.
Une méthode __iter__: va retourner self (on verra plus tard pourquoi)

Ces méthodes sont reliés aux fonctions standard (builtin) next et iter.

Pour un itérateur, la fonction iter doit nécessairement retourner self. La fonction next doit retourner l’élément suivant.

L’exemple suivant va implémenter un itérateurs pour les nombres entiers.

class SuiteEntiers:
    def __init__(self):
        self.index = 0 # on commence à 0
    def __iter__(self):
        return self
    def __next__(self):
        i = self.index
        self.index += 1
        return i

On peut définir un itérateur en appelant la classe.

N = SuiteEntiers()
print(next(N))
print(next(N))
print(next(N))

0
1
2

Un itérateurs peut être utiliser dans les constructions de boucles for ... in``` ou dans les fonctionsmap,filter` qui retourne a leur tour des itérateurs.

for i in N:
    if i > 8:
        break # sinon on boucle a l'infinie
    print(i)

Un itérateurs peut ou non se terminer. Pour se terminer il faut que la méthode __next__ émette une erreur StopIteration.

On peut ainsi réimplémenter range facilement:

class MonRange:
    def __init__(self, min, max):
        self.min = min
        self.max = max
        self.index = min
    def __iter__(self):
        return self
    def __next__(self):
        if self.index == self.max:
            raise StopIteration()
        i = self.index
        self.index += 1
        return i
for i in MonRange(4, 7):
    print(i)

4
5
6

C’est une très mauvaise idée de faire ça, range est optimisé à bas niveau, mais c’est pour illustrer l’usage de StopIteration.

La boucle `for`

Il est possible de décrire le fonctionnement de la boucle for:

for i in I:
    f(i)

est équivalent à

I = iter(I)
while True:
    try:
        i = next(I)
        f(i)
    except StopIteration:
        break

Les itérables

Un itérables est n’importe quel objet qui implemente __iter__.

Il s’agit de générateurs d’itérateurs. Le retour de la méthode __iter__ doit alors être un itérateur. Les itérateurs sont des cas particuliers de générateurs.

On peut réaliser une boucle sur un générateur ou appeler toutes les fonctions qui manipule des itérateurs: map, filter, ect…

La plupart des classes standards de Python sont des itérables, ce qui explique pourquoi on peut utiliser avec les constructions for ... in:

les tuples

T = (1, 2, 3)
i = iter(T)
print(next(i))
print(next(i))
print(next(i))

1
2
3

les listes

L = [1, 2, 3]
i = iter(L)
print(next(i))
print(next(i))
print(next(i))

1
2
3

les dicts:

D = {1: "a", 2: "b", 3: "c" } 
i = iter(D)
print(next(i))
print(next(i))
print(next(i))

1
2
3

Les chaines:

s = "123"
i = iter(s)
print(next(i))
print(next(i))
print(next(i))

1
2
3

Exemples

On peut construire un itérable qui va représenter les entiers

class Entiers:
    def __iter__(self):
        return SuiteEntiers()

On peut maintenant faire autant de boucle qu’on le souhaite dessus sans consommer l’itérateur:

N = Entiers()
for i in N:
    if i<3:
        break
    print(i)
for i in N:
    if i>1000:
        print(i)
    if i>1003:
        break

On peut appliquer des opérateurs sur les entiers:

Carrés = map(lambda e:e*e, Entiers())
for i in Carrés:
    if i>10:
        break
print(i)

Les générateurs

On peut également définir des itérateurs à l’aide de générateurs: il s’agit de fonctions particulières qui retournent des itérateurs. Pour définir un générateur, il suffit de définir une fonction qui contient dans son code le mot clef yield (emettre).

def un_generateur():
    yield "poulet"
    yield "roti"
    yield "avec"
    yield "des frites"
it = un_generateur()
print(type(it))

<class 'generator'>

On peut dérouler l’itérateur:

print(next(it))
print(next(it))
print(next(it))
print(next(it))

poulet
roti
avec
des frites

Une fois que le dernier yield de l’execution de la fonction est atteint, une erreur StopIteration est émise avec la valeur du type de retour.

def un_generateur_vide():
    if False:
        yield 3 # ceci ne sera jamais atteint
    return "Truc"

it = un_generateur_vide()
next(it)

Traceback (most recent call last):
  File "/var/www/cha/check_py_md", line 81, in repl
    exec(code, env)
  File "<string>", line 7, in <module>
StopIteration: Truc

Un exemple: les nombres premiers

On définit un générateur qui va fournir un itérateur sur les nombres premiers:

def premiers():
    S = list() 
    n = 1
    while True:
        n += 1
        if any(n % p == 0 for p in S):
            continue
        S.append(n)
        yield n

P = premiers()
print(", ".join(str(next(P)) for _ in range(20)))

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

On peut ainsi s’amuser et énumérer tous les nombres premiers jumeaux (i.e. les nombres \((n, n+2)\) tel que \(n\) et \(n+2\) sont premiers.)

def dist2(e):
    return True if abs(e[0]-e[1]) == 2 else False

P1 = premiers()
P2 = premiers()
next(P2) # on introduit un décalage
it = zip(P1, P2) # on construit l'itérateur des paires sur P1 et P2
it = filter(dist2, it)
print(", ".join(str(next(it)) for _ in range(20)))

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193), (197, 199), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313)

L’opérateur yield from

Il est possible d’émettre toutes les valeurs d’un itérateurs dans un générateur à l’aide de yield from

def un_generateur_bis():
    yield from ["poulet", "roti", "avec", "des frites"]

it = un_generateur_bis()
print(next(it))
print(next(it))
print(next(it))
print(next(it))

poulet
roti
avec
des frites

On peut ainsi définir des modificateurs d’itérateurs à l’aide de générateurs. Par exemple, on peut rédéfinir une fonction qui chaine les itérateurs:

def chaine(*iterators):
    for it in iterators:
        yield from it

it = chaine(["a", "b"], ["c", "d"], ["e", "f"])
print(", ".join(it))

a, b, c, d, e, f

Le module itertools contient déja des opérateurs d’itérateurs et entre autre chaine. Mieux vos utiliser ce module qui est optimisé que du code improvisé.

Compiled the: mar. 26 nov. 2024 11:44:00 CET