Iterators, map, reduce
De très nombreux algorithmes consistent à appliquer un traitement à une séquence de données. Les langages de programmation modernes proposent des itérateurs afin d’écrire le parcours des collections de données de manière concise et efficace (en temps comme en mémoire).
Ces itérateurs permettent d’abstraire l’implémentation de la séquence (liste, chaîne de caractères, ensemble, etc). Un même parcours pourra donc s’appliquer à différentes structures de données. Par exemple:
def print_all(s):
for x in s:
print(x)
print_all(range(1, 10, 2))
print_all([0,1,2,3,4])
print_all({5,6,7,8,9})
print_all('abcdef')
Par ailleurs, un itérateur permet de parcourir une séquence sans nécessairement la stocker entièrement en mémoire. Il est ainsi possible de parcourir des collections qui ne peuvent pas être stockées dans la mémoire disponible (par exemple, de très gros fichiers).
Parcourir une séquence
Intervalle d’entiers
On considère les deux programmes Python suivants, iter_list.py:
x = -1
for i in list(range(100000000)):
if i == x:
print("Trouvé")
break
et iter_range.py:
x = -1
for i in range(100000000):
if i == x:
print("Trouvé")
break
Lancer successivement les deux scripts dans un terminal, en utilisant la commande shell time pour observer leurs temps d’exécution, par exemple:
$ time ./iter_list.py
./iter_list.py 4.15s user 1.15s system 92% cpu 5.727 total
$ time ./iter_range.py
./iter_range.py 3.81s user 0.04s system 99% cpu 3.854 total
On observe une grande variabilité sur les temps d’exécution. En moyennant sur plusieurs exécutions, on observe que les temps d’exécution de ./iter_range.py et ./iter_list.py sont proches.
Ouvrir deux terminaux à l’écran. Lancer la commande top dans le premier, et le script iter_list.py dans le second. Estimer la quantité de mémoire consommée par le script iter_list.py. Procéder de même pour iter_range.py. Que pouvez-vous en déduire?
Un fichier
Obtenir le fichier dp.txt à l’aide de la commande suivante:
$ curl -fL https://raw.githubusercontent.com/kkrypt0nn/wordlists/refs/heads/main/wordlists/passwords/dutch_passwords.txt -o db.txt
ATTENTION: pensez à effacer le fichier
db.txtà la fin du TP car celui-ci fait plus de 40MB.
Les deux programmes ci-dessous parcourent entièrement le fichier db.txt.
iter_read.py
import time
secret = ''
f = open("db.txt")
lines = f.read().split("\n")
for word in lines:
if word == secret:
print("Trouvé!")
break
time.sleep(5)
f.close()
iter_readline.py
import time
secret = ''
f = open("db.txt")
while True:
line = f.readline()
if line == "": # fin de fichier
break
word = line.strip()
if word == secret:
print("Trouvé")
break
time.sleep(5)
f.close()
Comparer la quantité de mémoire utilisée par chacun des deux programmes à l’aide de l’utilitaire top. Que stocke chacun des deux scripts en mémoire?
Créer des itérateurs
Générateurs: (x for x in S if p)
Combien de listes sont créées en mémoire par chacun des code suivants:
A = [2**i for i in range(100) if i % 3 == 0]
sum(A)
B = (2**i for i in range(100) if i % 3 == 0)
sum(B)
Quel est le type de B? L’objet B peut-il être indexé ou slicé? Quelles sont les opérations possibles sur B (voir help(B))?
Fonctions génératrices: yield
Le mot clé yield est utilisé à la place de return dans une fonction pour que celle-ci génère une séquence de valeurs plutôt qu’une seule valeur.
def gennumbers(n):
for i in range(n):
if i % 3 == 0:
yield 2**i
for x in gennumbers(100):
print(x)
sum(gennumbers(100))
Combien de fois la fonction gennumbers est-elle appelée? Comment la boucle sur x s’exécute-t-elle?
On souhaite pouvoir parcourir un fichier ligne à ligne, en utilisant un générateur, et sans charger le fichier entièrement en mémoire. Implémenter al fonction lines ci-dessous comme un générateur qui énumère les lignes du fichier f.
def lines(f):
pass
if __name__ == '__main__':
secret = 'thisisnotapassword'
with open('db.txt') as f:
for line in lines(f):
if line == secret:
print('Trouvé')
break
Solution
def lines(f):
line = f.readline()
while (line != ''):
yield line.strip()
line = f.readline()
Écrire une fonction iter_fibonacci(n) qui génère succésivement les n premiers termes de la suite de Fibonacci sous la forme d’une séquence itérable. Afficher les 10 premiers termes de la suite en utilisant la fonction print_all ci-dessus.
Solution
def iter_fibonacci(n):
u0 = 0
u1 = 1
yield u0
yield u1
for i in range(n-2):
u2 = u0 + u1
yield u2
u0 = u1
u1 = u2
Définir une fonction iter_IP qui génère la séquence itérable des adresses IPv4. Chaque adresse sera retournée sous la forme d’un tuple de 4 valeurs.
Solution
def iter_IP():
for a in range(256):
for b in range(256):
for c in range(256):
for d in range(256):
yield (a, b, c, d)
Utiliser la fonction islice du module itertools (cf. documentation) pour afficher certaines des valeurs, par exemple:
>>> import itertools as it
>>> for ip in it.islice(iter_IP(), 20, 30):
... print(ip)
...
(0, 0, 0, 20)
(0, 0, 0, 21)
(0, 0, 0, 22)
(0, 0, 0, 23)
(0, 0, 0, 24)
(0, 0, 0, 25)
(0, 0, 0, 26)
(0, 0, 0, 27)
(0, 0, 0, 28)
(0, 0, 0, 29)
Objets itérateurs (avancé)
Enfin, il est possible de définir un itérateur qui est un objet, qui implémente une certaine interface permettant d’énumérer les éléments d’une séquence.
La classe interval ci-dessous représente l’intervalle $[first, last]$. Son constructeur __init__ permet d’initialiser les deux bornes de l’intervalle.
class interval:
first = 0
last = 0
def __init__(self, first, last):
self.first = first
self.last = last
L’objectif est d’implémenter un itérateur pour la classe interval qui permet d’énumérer un à un les entiers compris entre first et last. Pour cela, vous pourrez vous appuyer sur la documentation du type itérateur. On attend le résultat suivant:
>>> for i in interval(2, 7):
... print(i)
...
2
3
4
5
6
7
>>> for i in interval(7, 7):
... print(i)
...
7
>>> for i in interval(7, 5):
... print(i)
...
>>>
Combiner des itérateurs ou générateurs
Le module itertools (cf. documentation) définit plusieurs fonctions utilitaires sur les itérateurs et générateurs. Les exercices ci-dessous ont pour objectif d’en programmer certains.
Composition séquentielle
Compléter la fonction iter_sequence ci-dessous qui énumère les éléments de la séquence s1, suivis de ceux de la séquence s2.
def iter_sequence(s1, s2):
pass
Solution
def iter_sequence(s1, s2):
for x in s1:
yield x
for y in s2:
yield y
Tester votre fonction en lui passant différents conteneurs itérables (list, set, str, tuple, etc) ainsi que des fonctions génératrices:
>>> for i in iter_sequence(range(3), range(7)):
... print(i)
...
0
1
2
0
1
2
3
4
5
6
>>> for i in iter_sequence(range(2,6), ['a','b','c']):
... print(i)
...
2
3
4
5
a
b
c
Produit cartésien
Compléter la fonction iter_cartesian ci-dessous qui énumère les tuples de valeurs du produit cartésien s1 * s2.
def iter_cartesian(s1, s2):
pass
Solution
def iter_cartesian(s1, s2):
for x in s1:
for y in s2:
yield (x, y)
Tester votre fonction en lui passant différents conteneurs itérables (list, set, str, tuple, etc) ainsi que des fonctions génératrices:
>>> for x in iter_cartesian([1,2,3], {'a', 'b'}):
... print(x)
...
(1, 'a')
(1, 'b')
(2, 'a')
(2, 'b')
(3, 'a')
(3, 'b')
Extension à un nombre quelconque de séquences (avancé)
En utilisant les listes d’arguments et les fonctions iter_sequence et iter_cartesian ci-dessus, programmer deux fonctions qui composent un nombre quelconque de sequences, l’une séquentiellement, l’autre comme un produit cartésien.
Écrire une nouvelle version de la fonction iter_IP utilisant le produit cartesian généralisé.
Manipuler les séquences
La bibliothèque standard Python, ainsi que le module itertools fournissent des fonctions permettant de manipuler les séquences.
Énumérer les éléments d’une séquence avec leur indice: enumerate
La fonction enumerate permet d’énumérer les éléments d’une séquence, associés à leur indice dans la séquence:
>>> for i, x in enumerate(['a', 'b', 'c']):
... print(f"{x} à l'indice {i}")
...
a à l'indice 0
b à l'indice 1
c à l'indice 2
Écrire une fonction find(x, s) qui cherche un élément x dans une séquence s et retourne son indice si x est dans s et None sinon.
Solution
def find(x, s):
for i, y in enumerate(s):
if y == x:
return i
return None
Programmer une fonction myenumerate qui se comporte comme la fonction enumerate.
Solution
def myenumerate(s):
i = 0
for x in s:
yield (i, x)
i += 1
Appliquer une transformation à une séquence avec map
La fonction map (cf. help(map)) applique une fonction à chaque élément d’une séquence, et fournit la séquence transformée. Par exemple:
def double(x):
return 2*x
l = [1,2,3,4,5]
for n in map(double, l):
print(n)
Quel est le type de map(double, l)? Qu’est-ce qui est stocké en mémoire?
La fonction apliquée à l peut être définie directement à l’appel de map sous la forme d’une fonction anonyme (cf. lambdas):
for n in map(lambda x : 2*x, l):
print(n)
Écrire une fonction to_int qui prend en paramètre une séquence s de chaînes de caractères représentant des nombres entiers (ex: '12', '-218', '348') et qui retourne la séquence des entiers correspondants (ex: 12, -218, 348).
Solution
def to_int(s):
return map(int, s)
Proposer une fonction mymap qui se comporte comme la fonction map.
Solution
def mymap(f, s):
for x in s:
yield f(x)
Aggréger un calcul sur une séquence avec reduce
La fonction reduce du module functools (cf. help(functools.reduce)) permet d’aggréger les résultats d’un calcul sur une séquence.
>>> import functools as ft
>>> ft.reduce(lambda x,y: x+y, [1,2,3,4], 0)
10
À quoi correspondent chacun des paramètres de reduce?
Comment calculer le produit des éléments d’une liste plutôt que la somme?
Solution
ft.reduce(lambda x,y: x*y, [1,2,3,4], 1)
Proposer une implémentation de la fonction myreduce qui se comporte comme la fonction reduce ci-dessus.
Solution
def myreduce(f, s, i):
current = i
for x in s:
current = f(current, x)
return current
Filtrer les éléments d’une séquence avec filter
La fonction standard filter (cf. help(filter)) génère la sous-séquence des éléments d’une séquence donnée, qui satisfont un certain prédicat.
>>> print_all(filter(lambda x : x%2 == 0, [1,2,3,4,5,6,7]))
2
4
6
Écrire une fonction included qui prend deux séquences s1 et s2 en paramètres et qui génère la sous-séquence des éléments de s1 qui appartiennent à s2.
Solution
def included(s1, s2):
return filter(lambda x: x in s2, s1)
Écrire une fonction myfilter qui se comporte comme la fonction standard filter.
Solution
def myfilter(f, s):
for x in s:
if f(x):
yield x
Histogramme
On veut créer un histogramme du nombre de mots de chaque longueur dans une séquence de chaînes de caractères.
En utilisant map et reduce, programmer la fonction histogramme qui retourne le dictionnaire associant à chaque longueur le nombre des mots dans la séquence s qui ont cette longueur.
def histogramme(s):
pass
Compter le nombre de mots de 1 à 5 caractères (inclus), de 6 à 10 caractères (inclus), de 11 à 15 caractères (inclus) et de plus de 15 caractères présents dans la séquence de caractères s. Le résultat sera renvoyé sous la forme d’un tuple de 4 entiers.