[python] 중첩 된 사전을 병합하여 키 압축

Program / 글쓴이

다음과 같은 사전이 있다고 가정하십시오.

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

다음과 같이 평평하게 만드는 방법은 무엇입니까?

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

답변

기본적으로 중첩 목록을 평평하게하는 것과 같은 방식으로 키 / 값으로 dict를 반복하고 새 사전에 대한 새 키를 만들고 최종 단계에서 사전을 만들기 위해 추가 작업을 수행하면됩니다.

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}

답변

원본 포스터에서 고려해야 할 두 가지 큰 고려 사항이 있습니다.

  1. 키 스페이스 클로버 링 문제가 있습니까? 예를 들어 {'a_b':{'c':1}, 'a':{'b_c':2}}결과는 다음과 같습니다 {'a_b_c':???}. 아래 솔루션은 반복 가능한 쌍을 반환하여 문제를 피합니다.
  2. 성능이 문제인 경우 키 감소 기 기능 (여기서 ‘결합’이라고 함)은 전체 키 경로에 액세스해야합니까, 아니면 트리의 모든 노드에서 O (1)이 작동합니까? 을 말하고 joinedKey = '_'.join(*keys)싶다면 O (N ^ 2) 실행 시간이 걸립니다. 그러나 기꺼이 말하면 nextKey = previousKey+'_'+thisKeyO (N) 시간을 얻습니다. 아래의 솔루션을 사용하면 두 키를 모두 수행 할 수 있습니다 (모든 키를 연결 한 후 사후 처리 할 수 ​​있기 때문에).

(성능은 가능성이 문제가되지 않습니다,하지만 난 경우 다른 사람 걱정에서 두 번째 점에 정교합니다 :.이 구현에서, 수많은 위험한 선택이있다이 반복적으로 수율 및 재 수율, 또는 않으면 아무것도 하는 터치 동등한 실수로하기 쉬운 노드를 두 번 이상 사용하면 O (N) 대신 O (N ^ 2) 작업을 수행 할 수 있습니다. 키 a를 계산 한 a_1다음 a_1_i…을 계산하고 계산하기 때문일 수 있습니다. a그런 a_1다음 a_1_ii…, 그러나 실제로 a_1다시 계산할 필요는 없습니다. 다시 계산하지 않아도 다시 계산하는 것 ( ‘레벨 별’접근 방식)도 나쁩니다. 에 대한 성능을 생각하기 위해 {1:{1:{1:{1:...(N times)...{1:SOME_LARGE_DICTIONARY_OF_SIZE_N}...}}}})

아래는 내가 작성한 기능 flattenDict(d, join=..., lift=...)으로 많은 목적에 적합하고 원하는 것을 할 수 있습니다. 슬프게도 위의 성능 저하를 유발하지 않고이 기능의 게으른 버전을 만드는 것은 상당히 어렵습니다 (chain.from_iterable과 같은 많은 Python 내장 기능은 실제로 효율적이지 않습니다. 이 하나).

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

무슨 일이 일어나고 있는지 더 잘 이해하기 위해, 아래는 reduce“왼쪽”에 익숙하지 않은 사람들을위한 다이어그램입니다 . 때로는 k0 (목록의 일부가 아닌 함수에 전달됨) 대신 초기 값으로 그려집니다. 여기, J우리의 join기능이 있습니다. 각 k n을 로 사전 처리합니다 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

이것은 실제로와 동일 functools.reduce하지만 함수가 트리의 모든 키 경로에이를 수행합니다.

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

데모 (문서 문자열에 넣을 것) :

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

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

>>> pp(dict( flattenDict(testData, join=lambda a,b:a+'_'+b) ))
{'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}

공연:

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

… 한숨, 내 잘못이라고 생각하지 마십시오 …

[조정 문제로 인한 중요하지 않은 기록]

Flatten의 중복 주장과 관련하여 Python의 사전 사전 (2 레벨) 사전 :

이 질문의 솔루션은을 수행 하여이 문제의 관점에서 구현할 수 있습니다 sorted( sum(flatten(...),[]) ). 그 반대의 경우는 불가능합니다. 고차 누산기를 매핑하여 의심되는 복제본에서 값 을 flatten(...)복구 할 수 있지만 키를 복구 할 수는 없습니다. (편집 : 또한 중복 된 소유자의 질문은 완전히 다른 것으로 나타났습니다. 단, 해당 페이지의 답변 중 하나가 일반적인 해결책을 제공하지만 정확히 2 단계 깊이의 사전 만 처리한다는 점입니다.)

답변

또는 이미 팬더를 사용하고 있다면 다음과 json_normalize()같이 할 수 있습니다 .

import pandas as pd

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

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

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

산출:

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

답변

당신이 사용하는 경우 pandas에 숨겨진 기능이 pandas.io.json._normalize하나 라는 nested_to_record정확히이 일을합니다.

from pandas.io.json._normalize import nested_to_record

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

1 에서 판다 버전 0.24.x이상을 사용 pandas.io.json.normalize합니다 (없는 _)

답변

다음은 일종의 “기능적”, “한 줄짜리”구현입니다. 재귀 적이며 조건식과 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 }

테스트:

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}

답변

암호:

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

def parse_dict(init, lkey=''):
    ret = {}
    for rkey,val in init.items():
        key = lkey+rkey
        if isinstance(val, dict):
            ret.update(parse_dict(val, key+'_'))
        else:
            ret[key] = val
    return ret

print(parse_dict(test,''))

결과 :

$ python test.py
{'a': 1, 'c_a': 2, 'c_b_x': 5, 'd': [1, 2, 3], 'c_b_y': 10}

python3.2를 사용하고 있습니다. 파이썬 버전을 업데이트하십시오.

답변

Python3.5 의 기능 및 성능 솔루션은 어떻습니까?

from functools import reduce


def _reducer(items, key, val, pref):
    if isinstance(val, dict):
        return {**items, **flatten(val, pref + key)}
    else:
        return {**items, pref + key: val}

def flatten(d, pref=''):
    return(reduce(
        lambda new_d, kv: _reducer(new_d, *kv, pref),
        d.items(),
        {}
    ))

이것은 훨씬 더 성능이 좋습니다.

def flatten(d, pref=''):
    return(reduce(
        lambda new_d, kv: \
            isinstance(kv[1], dict) and \
            {**new_d, **flatten(kv[1], pref + kv[0])} or \
            {**new_d, pref + kv[0]: kv[1]},
        d.items(),
        {}
    ))

사용:

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

print(flatten(my_obj))
# {'d': [1, 2, 3], 'cby': 10, 'cbx': 5, 'ca': 2, 'a': 1}