Parcourir un itérable par morceaux en Python

This entry was posted in Programmation and tagged iteration python on by

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)
<generator object morceaux at 0x9e31414>
>>> 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 "<ipython-input-64-56409f08fc48>", line 1, in <module>
    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)
<itertools.chain object at 0x9e7c72c>
>>> 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)
<itertools.islice object at 0x9e822ac>
>>> 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.

21 thoughts on “Parcourir un itérable par morceaux en Python”

  • Sam Post author

    Avant qu’on me pose la question: si vous passer un itérable infini à la fonction:

    – soit c’est le comportement attendu, et il n’y a rien à faire: laissez le process boucler indéfiniement.
    – soit vous devez arrêter l’itération sous une condition, auquel cas vous DEVEZ boucle sur le résultat de morceaux avec une boucle for dans laquelle vous avez la condition de sortie.
    – soit vous pensez que l’itérable devrait être fini, mais vous suspectez que la source de donnée n’est pas fiable, auquel cas vous pouvez limiter la sortie en utilisant un des outils d’itertools. Par exemple:

    list(islice(morceaux(xrange(100000000), 3, tuple), 5))
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13, 14)]
  • Luigi

    Dernier paragraphe : “si ils peuvent utiliser cette approchent où non” => “si ils peuvent utiliser cette approche ou non”.

    • Sam Post author

      Ok, donc les lecteurs lisent les articles jusqu’au bout. C’est bon à savoir !

  • Sam Post author

    Au passage, si vous vous foutez du format de sortie, on peut aussi utiliser le bien plus court:

    from itertools import izip
 
def morceaux(iterable, taille):
    return izip(*([iter(iterable)] * taille))

    Le comportement de la première implémentation quand taille dépasse la taille de l’itérable est légèrement plus cohérente que celui de la deuxième: celle-ci s’arrête au dernier morceau complet, l’autre déborde sur le morceau le plus petit.

  • Cladmi

    Je trouve que tu passes très vite sur cette ligne avec le ‘chain’, alors que pour moi, elle n’est pas si évidente que ça.

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

    – Première question qui m’est venue: pourquoi on fait it.next() et islice(), au lieu de faire que islice() ?
    J’ai testé et c’est parce que islice() ne lève pas de ‘StopIteration’, on doit donc faire le it.next() pour que la boucle puisse s’arrêter.

    – Et l’autre question: pourquoi tu refais un générateur avec le it.next() ?
    J’ai testé sans pour voir, ça marchait, j’ai testé avec des print partout, et j’ai l’impression que les lectures sont réalisées dans le même ordre avec et sans le générateur. Du coup, là je sais pas.

  • Sam Post author

    Bonjour Cladmi. Je n’ai pas compris la seconde question. Qu’entends tu par “refaire un générateur”. Et par “sans” ?

  • Cladmi

    Oui erreur de ma part, c’est un tuple et non un générateur.
    J’ai confondu avec la syntaxe avec les parenthèses pour faire un générateur quand on utilise les listes en intention.

    Et donc en fait, je me demandais pourquoi tu faisais chain((it.next(),),...) au lieu de chain(it.next(),...) directement.

  • Sam Post author

    Parce que le premier paramètre de chain() doit être un itérable.

    >>> list(chain(1, [2, 3]))
Traceback (most recent call last):
  File "<ipython-input-2-af20e950e88c>", line 1, in <module>
    list(chain(1, [2, 3]))
TypeError: 'int' object is not iterable
>>> list(chain((1,), [2, 3]))
[1, 2, 3]
  • Cladmi

    Bien joué, c’est pour ça que quand je testais avec une liste de string ça marchait, j’étais dans un cas particulier.

    Donc cette ligne était encore plus compliquée que ce que je pensais.

    Merci pour les réponses.

  • Lujeni

    Hello Sam,

    dans ton commentaire pour parcourir un iterable tu reprends la syntaxe de type:
    izip(*[iter(s)]*n)

    Question un peu idiote, j’ai du mal a bien comprendre cette syntaxe, les etoiles ont elles une signification?

    Merci et encore bravo pour le boulot :)

  • Lujeni

    Merci Sam ! Enfin compris, la syntaxe étant un peu tordu pour moi et l’unpacking complètement zappé. Un petit refresh ne m’a pas fait de mal :)

  • Atrament

    Il y a une phrase qui n’en est pas une là :

    “Elle retourne un itérateur, c’est à dire un objet qui possède qui peut être passé à la fonction next()”

    Je soupçonne qu’il devrait y être écrit :

    “Elle retourne un itérateur, c’est à dire un objet qui peut être passé à la fonction next()”

    merci pour les mises à jour !

  • Anne Onyme

    Et voici les quelques petites erreurs que j’ai remarquées:

    * “chain() prends” -> “chain() prend”;

    * “de taille inconnu” -> “de taille inconnue”;

    * “et jamais stockées pour rien” -> “et ne sont jamais stockées pour rien”;

    * “les listes en intention” -> “les listes en intension”;

    * “pas quelque chose figé” -> “pas quelque chose de figé”;

    * “s’ils peuvent utiliser cette approchent” -> “s’ils peuvent utiliser cette approche”;

    * “où non” -> “ou non”.

    Les “erreurs” “paramètre vs argument” (http://sametmax.com/la-difference-entre-parametres-et-arguments/):

    * “accepte n’importe quel itérable en paramètre” -> “accepte n’importe quel itérable en argument”;

    * “passage de fonction en paramètre” -> “passage de fonction en argument”.

    Et enfin, parce que ça me démange de faire mon grammar-nazi:

    “C’est une solution d’une rare élégance, car elle tient en quelques lignes, et assure une gigantesque flexibilité” -> pas de virgule avant une conjonction de coordination (2 fois).

    Au plaisir.

  • Léa

    Bonjour,

    Et si on veut traiter par lot de trois mais avancer d’un caractère à chaque fois, tel qu’on voudrait obtenir ‘123’, ‘234’, ‘345’, etc… ?

    Je travaille sur des chaines de caractères donc dès que j’ai voulu enlever le premier élément par .pop(0) ça me mets :

    ‘str’ object has no attribute ‘pop’. Du coup je ne sais pas comment faire,

    Sauriez-vous m’aider ?

    Merci !

  • Sam Post author

    Le premier exemple sous “Usage avancé” te permettra de faire ta première tache.

    Pour la seconde, les chaines sont immutables (on ne peut les modifier), donc on ne peut pas retirer un élément. Il faut créer une nouvelle chaine, par exemple avec du slicing ou strip():

    >>> "o_o/ ohhhh nooon"[:-6]
    'o_o/ ohhhh'
 
>>> "o_o/ ohhhh nooon".strip("no")
    'o_o/ ohhhh '

    Si tu as d’autres questions, pose les sur indexerror.net, ce sera plus adapté pour y répondre que les commentaires du blog.

  • 7c

    Salut,

    Petite question: j’ai vu dans un changelog 3.x que les generateurs ne devaient pas/plus etre stoppés avec stopiteration (meme si ils sont des iterateurs) mais via un return (explicite ou implicite).

    Dans ce cas le code deviendrait un truc comme ca?

    it = iter(iterable)

    while True:

    try:

    value = next(it)

    except StopIteration:

    return (ou break)

    else:

    yield format(itertools.chain((value,), itertools.islice(it, taille -1)))

  • Sam Post author

    Tu peux, mais perso je préfère utiliser le deuxième paramètre de next()

Comments are closed.

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.