Aplatissement des dictionnaires imbriqués, compression des clés

Question

Supposons que vous ayez un dictionnaire comme :

{'a': 1,
 'c': {'a': 2,
       'b': {'x': 5,
             'y' : 10}},
 'd': [1, 2, 3]}

Comment ferais-tu pour aplatir ça en quelque chose comme :

{'a': 1,
 'c_a': 2,
 'c_b_x': 5,
 'c_b_y': 10,
 'd': [1, 2, 3]}

Answer 1

En gros, c'est la même chose que d'aplatir une liste imbriquée, vous devez juste faire le travail supplémentaire pour itérer le dict par clé/valeur, créer de nouvelles clés pour votre nouveau dictionnaire et créer le dictionnaire à l'étape finale.

import collections

def flatten(d, parent_key='', sep='_'):
    items = []
    for k, v in d.items():
        new_key = parent_key + sep + k if parent_key else k
        if isinstance(v, collections.MutableMapping):
            items.extend(flatten(v, new_key, sep=sep).items())
        else:
            items.append((new_key, v))
    return dict(items)

>>> flatten({'a': 1, 'c': {'a': 2, 'b': {'x': 5, 'y' : 10}}, 'd': [1, 2, 3]})
{'a': 1, 'c_a': 2, 'c_b_x': 5, 'd': [1, 2, 3], 'c_b_y': 10}

Pour Python >= 3.3, changez l'import en from collections.abc import MutableMapping pour éviter un avertissement de dépréciation et modifier collections.MutableMapping pour juste MutableMapping .

Answer 2

Ou si vous utilisez déjà pandas, vous pouvez le faire avec json_normalize() comme ça :

import pandas as pd

d = {'a': 1,
     'c': {'a': 2, 'b': {'x': 5, 'y' : 10}},
     'd': [1, 2, 3]}

df = pd.json_normalize(d, sep='_')

print(df.to_dict(orient='records')[0])

Sortie :

{'a': 1, 'c_a': 2, 'c_b_x': 5, 'c_b_y': 10, 'd': [1, 2, 3]}

Answer 3

Il y a deux grandes considérations que l'affiche originale doit prendre en compte :

1. Y a-t-il des problèmes d'encombrement du clavier ? Par exemple, {'a_b':{'c':1}, 'a':{'b_c':2}} aurait pour conséquence {'a_b_c':???} . La solution ci-dessous contourne le problème en retournant un itérable de paires.
2. Si les performances sont un problème, la fonction de réduction des clés (que j'appellerai par la suite "join") doit-elle avoir accès à l'ensemble du chemin des clés, ou peut-elle simplement effectuer un travail O(1) à chaque nœud de l'arbre ? Si vous voulez être capable de dire joinedKey = '_'.join(*keys) qui vous coûtera O(N^2) en temps de fonctionnement. Cependant, si vous êtes prêt à dire nextKey = previousKey+'_'+thisKey ce qui vous donne un temps O(N). La solution ci-dessous vous permet de faire les deux (puisque vous pourriez simplement concaténer toutes les clés, puis les post-traiter).

(Les performances ne sont probablement pas un problème, mais je vais m'étendre sur le second point au cas où cela intéresserait quelqu'un d'autre : Dans la mise en œuvre de ce système, il existe de nombreux choix dangereux. Si vous faites cela de manière récursive et que vous céder et re-céder, ou tout ce qui est qui touche les nœuds plus d'une fois (ce qui est assez facile à faire accidentellement), vous effectuez potentiellement O(N^2) plutôt que O(N). Ceci est dû au fait que vous calculez peut-être une clé a puis a_1 puis a_1_i ..., puis en calculant a puis a_1 puis a_1_ii ..., mais vous ne devriez vraiment pas avoir à calculer a_1 encore. Même si vous ne le recalculez pas, le redonner (une approche "niveau par niveau") est tout aussi mauvais. Un bon exemple est de penser à la performance sur {1:{1:{1:{1:...(N times)...{1:SOME_LARGE_DICTIONARY_OF_SIZE_N}...}}}} )

Voici une fonction que j'ai écrite flattenDict(d, join=..., lift=...) qui peut être adapté à de nombreux usages et peut faire ce que vous voulez. Malheureusement, il est assez difficile de faire une version paresseuse de cette fonction sans encourir les pénalités de performance mentionnées ci-dessus (de nombreux buildins python comme chain.from_iterable ne sont pas vraiment efficaces, ce que je n'ai réalisé qu'après avoir testé trois versions différentes de ce code avant de me décider pour celle-ci).

from collections import Mapping
from itertools import chain
from operator import add

_FLAG_FIRST = object()

def flattenDict(d, join=add, lift=lambda x:(x,)):
    results = []
    def visit(subdict, results, partialKey):
        for k,v in subdict.items():
            newKey = lift(k) if partialKey==_FLAG_FIRST else join(partialKey,lift(k))
            if isinstance(v,Mapping):
                visit(v, results, newKey)
            else:
                results.append((newKey,v))
    visit(d, results, _FLAG_FIRST)
    return results

Afin de mieux comprendre ce qui se passe, voici un diagramme pour ceux qui ne sont pas familiers avec le système d'alerte précoce. reduce (gauche), autrement appelé "pli gauche". Parfois, il est dessiné avec une valeur initiale à la place de k0 (qui ne fait pas partie de la liste, passée dans la fonction). Ici, J est notre join fonction. Nous pré-traitons chaque k _n con lift(k) .

               [k0,k1,...,kN].foldleft(J)
                           /    \
                         ...    kN
                         /
       J(k0,J(k1,J(k2,k3)))
                       /  \
                      /    \
           J(J(k0,k1),k2)   k3
                    /   \
                   /     \
             J(k0,k1)    k2
                 /  \
                /    \
               k0     k1

C'est en fait la même chose que functools.reduce mais où notre fonction le fait pour tous les chemins-clés de l'arbre.

>>> reduce(lambda a,b:(a,b), range(5))
((((0, 1), 2), 3), 4)

Démonstration (que j'aurais autrement mis dans la docstring) :

>>> testData = {
        'a':1,
        'b':2,
        'c':{
            'aa':11,
            'bb':22,
            'cc':{
                'aaa':111
            }
        }
    }
from pprint import pprint as pp

>>> pp(dict( flattenDict(testData) ))
{('a',): 1,
 ('b',): 2,
 ('c', 'aa'): 11,
 ('c', 'bb'): 22,
 ('c', 'cc', 'aaa'): 111}

>>> pp(dict( flattenDict(testData, join=lambda a,b:a+'_'+b, lift=lambda x:x) ))
{'a': 1, 'b': 2, 'c_aa': 11, 'c_bb': 22, 'c_cc_aaa': 111}    

>>> pp(dict( (v,k) for k,v in flattenDict(testData, lift=hash, join=lambda a,b:hash((a,b))) ))
{1: 12416037344,
 2: 12544037731,
 11: 5470935132935744593,
 22: 4885734186131977315,
 111: 3461911260025554326}

---

Performance :

from functools import reduce
def makeEvilDict(n):
    return reduce(lambda acc,x:{x:acc}, [{i:0 for i in range(n)}]+range(n))

import timeit
def time(runnable):
    t0 = timeit.default_timer()
    _ = runnable()
    t1 = timeit.default_timer()
    print('took {:.2f} seconds'.format(t1-t0))

>>> pp(makeEvilDict(8))
{7: {6: {5: {4: {3: {2: {1: {0: {0: 0,
                                 1: 0,
                                 2: 0,
                                 3: 0,
                                 4: 0,
                                 5: 0,
                                 6: 0,
                                 7: 0}}}}}}}}}

import sys
sys.setrecursionlimit(1000000)

forget = lambda a,b:''

>>> time(lambda: dict(flattenDict(makeEvilDict(10000), join=forget)) )
took 0.10 seconds
>>> time(lambda: dict(flattenDict(makeEvilDict(100000), join=forget)) )
[1]    12569 segmentation fault  python

... soupir, je ne pense pas que celle-là soit de ma faute...

---

[note historique sans importance en raison de problèmes de modération].

En ce qui concerne le prétendu double emploi de Aplatir un dictionnaire de dictionnaires (2 niveaux de profondeur) de listes

La solution de cette question peut être implémentée en termes de celle-ci en faisant sorted( sum(flatten(...),[]) ) . L'inverse n'est pas possible : s'il est vrai que la valeurs de flatten(...) peut être récupéré à partir du prétendu doublon en mappant un accumulateur d'ordre supérieur, on ne peut pas récupérer les clés. (edit : Il s'avère également que la question du propriétaire du prétendu duplicata est complètement différente, en ce sens qu'elle ne traite que des dictionnaires d'une profondeur d'exactement 2 niveaux, bien qu'une des réponses sur cette page donne une solution générale).

Answer 4

Si vous utilisez pandas il y a une fonction cachée dans pandas.io.json._normalize 1 appelé nested_to_record qui fait exactement cela.

from pandas.io.json._normalize import nested_to_record    

flat = nested_to_record(my_dict, sep='_')

---

1 Dans les versions de pandas 0.24.x et plus âgés utilisent pandas.io.json.normalize (sans le _ )

Answer 5

Voici une sorte d'implémentation "fonctionnelle", "one-liner". Elle est récursive, et basée sur une expression conditionnelle et une compréhension de dict.

def flatten_dict(dd, separator='_', prefix=''):
    return { prefix + separator + k if prefix else k : v
             for kk, vv in dd.items()
             for k, v in flatten_dict(vv, separator, kk).items()
             } if isinstance(dd, dict) else { prefix : dd }

Test :

In [2]: flatten_dict({'abc':123, 'hgf':{'gh':432, 'yu':433}, 'gfd':902, 'xzxzxz':{"432":{'0b0b0b':231}, "43234":1321}}, '.')
Out[2]: 
{'abc': 123,
 'gfd': 902,
 'hgf.gh': 432,
 'hgf.yu': 433,
 'xzxzxz.432.0b0b0b': 231,
 'xzxzxz.43234': 1321}