Du code, du communisme

Parcourir un itérable par morceaux en Python

Parcourir un itérable par morceaux signifie qu’on le traite petit bout par petit bout. On parle aussi de fenêtre glissante.
Par exemple, on a une liste, et on veut traiter les éléments par lot de 3 :

>>> ["a", "b", "c", "d", "e", "f", "g"]
["a", "b", "c", "d", "e", "f", "g"]
>>> ("a", "b", "c")
("a", "b", "c")
>>> ("d", "e", "f")
("d", "e", "f")
>>> ("g",)
("g",)
>>>

Pour les gens pressés

Il n’y a pas de fonction dans la bibliothèque standard de Python qui permette de le faire, mais on peut créer une très jolie solution à base de générateurs :

from itertools import chain, islice
def morceaux(iterable, taille, format=tuple):
    it = iter(iterable)
    while True:
        yield format(chain((next(it),), islice(it, taille - 1)))

Et on l’utilise ainsi :

>>> l = ["a", "b", "c", "d", "e", "f", "g"]
>>> for morceau in morceaux(l, 3):
...         print(morceau)
...
("a", "b", "c")
("d", "e", "f")
("g",)

Usage avancé

Grâce au troisième paramètre, on peut récupérer une sortie sous un format différent, par exemple une chaine de caractères :

>>> for morceau in morceaux(l, 3, ''.join):
        print(morceau)
...
abc
def
g

Le résultat retourné par morceaux() est un générateur :

>>> morceaux(l, 3)

>>> list(morceaux(l, 3))
[('a', 'b', 'c'), ('d', 'e', 'f'), ('g',)]

Et la fonction accepte n’importe quel itérable en paramètre, pas uniquement des listes. Par exemple une chaine de caractères :

>>> list(morceaux('123456789', 3, tuple))
[('1', '2', '3'), ('4', '5', '6'), ('7', '8', '9')]

Ou un fichier :

>>> f = open('/tmp/test', 'w', encoding='ascii')
>>> f.write('1\n2\n3\n4\n5\n6\n7\n8\n9\n10')
>>> f.close()
>>> list(morceaux(open('/tmp/test'), 3))
[('1\n', '2\n', '3\n'), ('4\n', '5\n', '6\n'), ('7\n', '8\n', '9\n'), ('10',)]

Comment ça marche ?

Cette fonction est un concentré d’astuces propres à Python : module itertools, mot-clé yield, iterable, passage de fonction en paramètre…
D’abord, on utilise la fonction built-in iter() :

it = iter(iterable)

Sur l’itérable passé en paramètre. Elle retourne un itérateur, c’est à dire un objet qui peut être passé à la fonction next(). next() permet d’accéder à la prochaine valeur de l’itérable jusqu’à épuisement de ce dernier :

>>> l = (1, 2, 3, 4, 5)
>>> iterateur = iter(l)
>>> next(iterateur)
1
>>> next(iterateur)
2
>>> next(iterateur)
3
>>> next(iterateur)
4
>>> next(iterateur)
5
>>> next(iterateur)
Traceback (most recent call last):
  File "", line 1, in 
    next(iterateur)
StopIteration

On crée ensuite une boucle infinie :

while True:

Cela permet de ne pas se soucier de la taille de l’itérable. Quand un itérateur arrive au bout d’un itérable, il lève l’exception StopIteration (c’est le mécanisme standard par lequel les boucles for itèrent, ce qui prouve une fois de plus que les exceptions s’utilisent partout en Python, et non juste dans la gestion des erreurs). Cette exception cassera la boucle infinie au moment opportun.
Ensuite on utilise deux fonctions du module itertools (un module spécialisé dans la manipulation des itérables) :

chain((next(it),), islice(it, taille - 1))

chain() prend deux itérables et retourne un générateur qui permet d’itérer sur l’un puis l’autre. Par exemple :

>>> l1 = (1, 2, 3)
>>> l2 = (4, 5, 6)
>>> chain(l1, l2)

>>> list(chain(l1, l2))
[1, 2, 3, 4, 5, 6]

islice() est comme la syntaxe [:], mais applicable à un itérable dont on ne connait pas la taille :

>>> l3 = (1, 2, 3, 4, 5, 6)
>>> islice(l3, 2)

>>> list(islice(l3, 2))
[1, 2]
>>> list(islice(l3, 2, 4))
[3, 4]

chain((next(it),), islice(it, taille - 1)) signifie donc « chainer un tuple qui contient la valeur suivante de l’itérable avec un autre itérable qui lui récupèrera la slice du reste du morceau extrait de l’itérable« .
Ouf.
Puis on applique :

format(...)

Sur le résultat. Ce qui permet de choisir dans quel format on souhaite avoir les morceaux (chaine, tuple, etc). Le comportement par défaut est de retourner des tuples.
Et enfin on utilise yield :

yield format(...)

Cela assure que morceaux() retourne un générateur qui créera chaque morceau à la volée, et non tout d’un coup en mémoire. Très utile si vous avez une grande liste :

>>> une_grande_liste = range(100000000)
>>> par_morceaux = morceaux(une_grande_liste, 3)
>>> next(par_morceaux)
(0, 1, 2)
>>> next(par_morceaux)
(3, 4, 5)
>>> next(par_morceaux)
(6, 7, 8)
>>> next(par_morceaux)
(9, 10, 11)

Malgré la taille de la liste, le résultat est presque instantané. Ce n’est pas parce que votre ordinateur est une bête de course. C’est parce que (3, 4, 5) n’est pas généré juste après (0, 1, 2). Il est généré au second appel de next(), à la volée.

Mais pourquoi faire si compliqué ?

Les bénéfices de cette approche sont :

  • La possibilité de parcourir par morceaux n’importe quel itérable : des chaines, des tuples, des listes, des dictionnaires, des querysets Django, des fichiers, etc.
  • La fonction accepte un itérable de n’importe quelle taille. En fait, elle accepte même un itérable de taille inconnu, par exemple un flux de données issu d’internet.
  • Cela consomme très peu de mémoire : on utilise des générateurs partout (merci à yield et au module itertools), donc toutes les valeurs sont générées uniquement quand on les demande, et jamais stockées pour rien.
  • Et d’ailleurs, comme on retourne un générateur, on peut passer le résultat à un processus utilisant des générateurs sans casser son empreinte mémoire. Faire des pipes d’un générateur à un autre est en effet un point fort de Python.
  • Mais comme le générateur est itérable, toute fonction qui accepte un itérable pourra utiliser le résultat : les fonctions de tri, les fonctions max, etc. La boucle for et les listes en intension l’acceptent aussi.
  • Le troisième paramètre garantit que chaque morceau est dans le format que l’on souhaite, pas quelque chose de figé qu’on devra caster : c’est un bonheur pour les one-liners.

C’est une solution d’une rare élégance car elle tient en quelques lignes et assure une gigantesque flexibilité, sans manger beaucoup de mémoire vive. Le seul défaut étant que la lecture enclenche le mécanisme de génération, qui est plus lent que de lire une structure de données, donc la lecture complète de toute la séquence est globalement plus lente que dans la plupart des autres approches.
Dans 90 % des cas, vous pouvez utiliser morceaux() sans souffrir de sa vitesse. Ceux qui bossent sur les 10 % restant ont un niveau tel qu’ils savent avec certitude s’ils peuvent utiliser cette approche ou non, donc si vous vous posez la question, c’est que vous n’en faites pas partie.