Aplatir un iterable like a boss en Python

This entry was posted in Programmation and tagged generator nesting python on by

Des structures un peu imbriquées ne sont pas trop difficiles à traiter en Python.

Par exemple, avec une liste en intention imbriquée :

>>> l = [(1, 2), (3, 4), (5, 6)]
>>> [y for x in l for y in x]
[1, 2, 3, 4, 5, 6]

Mais quand on a beaucoup de niveaux, par exemple…

a = []
for i in xrange(500):
    a = [a, i]
print(a)

[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[], 0], 1], 2], 3], 4], 5], 6], 7], 8], 9], 10], 11], 12], 13], 14], 15], 16], 17], 18], 19], 20], 21], 22], 23], 24], 25], 26], 27], 28], 29], 30], 31], 32], 33], 34], 35], 36], 37], 38], 39], 40], 41], 42], 43], 44], 45], 46], 47], 48], 49], 50], 51], 52], 53], 54], 55], 56], 57], 58], 59], 60], 61], 62], 63], 64], 65], 66], 67], 68], 69], 70], 71], 72], 73], 74], 75], 76], 77], 78], 79], 80], 81], 82], 83], 84], 85], 86], 87], 88], 89], 90], 91], 92], 93], 94], 95], 96], 97], 98], 99], 100], 101], 102], 103], 104], 105], 106], 107], 108], 109], 110], 111], 112], 113], 114], 115], 116], 117], 118], 119], 120], 121], 122], 123], 124], 125], 126], 127], 128], 129], 130], 131], 132], 133], 134], 135], 136], 137], 138], 139], 140], 141], 142], 143], 144], 145], 146], 147], 148], 149], 150], 151], 152], 153], 154], 155], 156], 157], 158], 159], 160], 161], 162], 163], 164], 165], 166], 167], 168], 169], 170], 171], 172], 173], 174], 175], 176], 177], 178], 179], 180], 181], 182], 183], 184], 185], 186], 187], 188], 189], 190], 191], 192], 193], 194], 195], 196], 197], 198], 199], 200], 201], 202], 203], 204], 205], 206], 207], 208], 209], 210], 211], 212], 213], 214], 215], 216], 217], 218], 219], 220], 221], 222], 223], 224], 225], 226], 227], 228], 229], 230], 231], 232], 233], 234], 235], 236], 237], 238], 239], 240], 241], 242], 243], 244], 245], 246], 247], 248], 249], 250], 251], 252], 253], 254], 255], 256], 257], 258], 259], 260], 261], 262], 263], 264], 265], 266], 267], 268], 269], 270], 271], 272], 273], 274], 275], 276], 277], 278], 279], 280], 281], 282], 283], 284], 285], 286], 287], 288], 289], 290], 291], 292], 293], 294], 295], 296], 297], 298], 299], 300], 301], 302], 303], 304], 305], 306], 307], 308], 309], 310], 311], 312], 313], 314], 315], 316], 317], 318], 319], 320], 321], 322], 323], 324], 325], 326], 327], 328], 329], 330], 331], 332], 333], 334], 335], 336], 337], 338], 339], 340], 341], 342], 343], 344], 345], 346], 347], 348], 349], 350], 351], 352], 353], 354], 355], 356], 357], 358], 359], 360], 361], 362], 363], 364], 365], 366], 367], 368], 369], 370], 371], 372], 373], 374], 375], 376], 377], 378], 379], 380], 381], 382], 383], 384], 385], 386], 387], 388], 389], 390], 391], 392], 393], 394], 395], 396], 397], 398], 399], 400], 401], 402], 403], 404], 405], 406], 407], 408], 409], 410], 411], 412], 413], 414], 415], 416], 417], 418], 419], 420], 421], 422], 423], 424], 425], 426], 427], 428], 429], 430], 431], 432], 433], 434], 435], 436], 437], 438], 439], 440], 441], 442], 443], 444], 445], 446], 447], 448], 449], 450], 451], 452], 453], 454], 455], 456], 457], 458], 459], 460], 461], 462], 463], 464], 465], 466], 467], 468], 469], 470], 471], 472], 473], 474], 475], 476], 477], 478], 479], 480], 481], 482], 483], 484], 485], 486], 487], 488], 489], 490], 491], 492], 493], 494], 495], 496], 497], 498], 499]

Là je désactive la coloration syntaxique du blog parce que le snippet a fait planté sublime :-D Heureusement, il reste VI.

Bref, quand on a ce genre de truc, comment on fait ? Pire, comment on traite un flux de données de types hétérogènes, et dont on ne connait pas la taille, ou de longueur infinie ? C’est une caractéristique de Python : on a des générateurs plein de duck typing partout !

Voici un petit snippet un peu tordu, mais qui fait des merveilles :

from collections import deque, OrderedDict, MutableSet, defaultdict
 
 
class Flattener(object):
 
    # les types qu'on va aplatir, c'est à dire la plupart
    # des iterables sauf les hashmaps
    DEFAULT_FLATTEN_TYPES = (
        list,
        tuple,
        set,
        (x for x in ()).__class__,
        xrange,
        deque,
        MutableSet,
    )
 
    # par défaut, on utilise DEFAULT_FLATTEN_TYPES et
    # aucun iterable_getters (on verra ce que c'est plus bas)
    # puisque c'est le cas le plus courant d'utilisation
    def __init__(self, flatten_types=None, iterable_getters={}):
        self.flatten_types = flatten_types or self.DEFAULT_FLATTEN_TYPES
        self.iterable_getters = iterable_getters
 
 
    # Retourne True si on doit aplatir l'objet.
    # Par défaut, vérifie dans si l'objet est d'un des types
    # DEFAULT_FLATTEN_TYPE.
    def should_flatten(self, obj):
        return isinstance(obj, self.flatten_types)
 
    # Si avant d'aplatir l'objet, l'objet a besoin d'une transformation
    # (par exemple appeler items() sur un dico), on l'applique. 
    # Par défaut il n'y a aucune transformation appliquée, quelque soit le 
    # type.
    def transform_iterable(self, obj):
        if obj.__class__ in self.iterable_getters:
            return self.iterable_getters[obj.__class__](obj)
        return obj
 
 
    # Permet d'appeler une instance de Flatener, comme si c'était une fonction
    def __call__(self, iterable):
        for e in:
            # Si un élément est à aplatir, on fait un appel récursif
            if self.should_flatten(e):
                # Appel récursif, et yielding du résultat de cet appel.
                for f in self(self.transform_iterable(e)):
                    yield f
            # On ne doit pas aplatir l'element (genre un int, un str...)
            # donc on le yield directement
            else:
                yield e
 
 
# fabrique un flattener, ici on prend la config par défaut
flatten = Flattener()
 
# et pouf
 
a = []
for i in xrange(500):
    a = [a, i]
 
applatie = list(flatten(a))
 
print(len(applatie))
print(applatie[:10])
5500
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Ca gère une longeur infinie, et une imbrication de centaines de niveaux. Comme Python a une limite de recursions (1000 par défaut), on est quand même bridé, mais c’est une situation rare d’avoir autant de nesting. Et dans les cas extrêmes, on peut allouer une plus grande stack avec sys.setrecursionlimit().

Via flatten_types, on peut créer différentes politiques d’aplatissement, bien que celle par défaut soit assez saine. Par exemple décider d’aplatir les strings, ou ne pas aplatir les tuples : il suffit de passer la bonne liste de types en paramètres. Comme le Flattener est une classe qui permet de créer flatten(), on peut la sous-classer et mettre à disposition plusieurs aplatisseurs personnalisés dans sa lib.

La partie :

                if e.__class__ in self.iterable_getters:
                    e = self.iterable_getters[e.__class__](e)

Permet de gérer des cas ambigüs, comme par exemple les dicos. Comment itérer dessus ? Par clé, par valeur ? Par défaut on ne les aplatit pas

On peut par exemple choisir d’aplatir complètement les dictionnaires. :

a = []
for i in xrange(2):
    a = [a, i] + [{'a': 1., 'b': {'c': 3.}}]
print(a)
 
[[[], 0, {'a': 1.0, 'b': {'c': 3.0}}], 1, {'a': 1.0, 'b': {'c': 3.0}}]
 
# on rajoute les dictionnaires aux types à aplatir
new_ft = Flattener.DEFAULT_FLATTEN_TYPES + (dict,)
 
dico_flatten = Flattener(flatten_types=new_ft,
                         # on dit qu'un dico rencontré doit être transformé
                         # via items() avant iteration
                         iterable_getters={dict: lambda x: x.items()})
 
print(list(dico_flatten(a)))
 
[0, u'a', 1.0, u'b', u'c', 3.0, 1, u'a', 1.0, u'b', u'c', 3.0]

On peut même overrider should_flatten et transform_iterable si des besoins plus importants se font sentir.

Attention tout de même à ce que vous mettez dans flatten_types. Par exemple, une string d’un caractère est à la fois yieldable comme valeur et itérable, ce qui va provoquer une recursion infinie. Adaptez toujours iterable_getters en conséquence.

Hop, dans batbelt.

5 thoughts on “Aplatir un iterable like a boss en Python”

  • foxmask

    Ça m’a fait pas à la tête en ce vendredi après midi :) Mais j’aime ce que ça fait en tout cas.

  • roro

    hé ben mon vieux, je sais pas d’où il les sort…
    Mais il nous en sort de vraiment étonnantes…

  • Sam Post author

    En général je récupère des trucs sur stackoverflow, activepython et github, je les nettoies, j’emballe le tout dans un code réutilisable et ça me fait un article.

  • Yahya Abou Imran

    Je vois bien que c’est un article qui date un peu, mais bon, juste pour dire:

    On peut remplacer l’histoire des flatten_types par quelque chose d’un peu plus simple si ce qu’on veut c’est juste accepter n’importe quel itétrable à l’exclusion des mappings :

    from collections.abc import Iterable, Mapping

    def should_flatten(self, obj):

    return isinstance(obj, Iterable) and not isinstance(obj, Mapping)

    C’est même l’une des raisons de l’existence des ABCs : avant, distinguer un mapping d’un “simple” itérable n’avait pas de solution propre (c’est la parole de Guido lui-même dans la PEP sur les ABCs).

    En outre, avoir set et MutablesSet dans les flatten_types en même temps est redondant…

    Quoiqu’il en soit, merci pour vos articles, à chaque fois que j’en lis un j’apprends plein de choses.

Comments are closed.

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