Sam & Max » nesting http://sametmax.com Du code, du cul Sat, 07 Nov 2015 10:56:13 +0000 en-US hourly 1 http://wordpress.org/?v=4.1 Aplatir un iterable like a boss en Python 4 http://sametmax.com/applatir-un-iterable-like-a-boss-en-python/ http://sametmax.com/applatir-un-iterable-like-a-boss-en-python/#comments Fri, 23 Aug 2013 10:08:55 +0000 http://sametmax.com/?p=7172 >>> 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...]]> 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.

]]>
http://sametmax.com/applatir-un-iterable-like-a-boss-en-python/feed/ 4