Выравнивание вложенных словарей, сжатие ключей
Предположим, у вас есть словарь типа:
{'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]}
Переведено автоматически
Ответ 1
В основном так же, как вы сглаживаете вложенный список, вам просто нужно выполнить дополнительную работу по повторению dict по ключу / значению, созданию новых ключей для вашего нового словаря и созданию словаря на заключительном шаге.
from collections.abc import MutableMapping
def flatten(dictionary, parent_key='', separator='_'):
items = []
for key, value in dictionary.items():
new_key = parent_key + separator + key if parent_key else key
if isinstance(value, MutableMapping):
items.extend(flatten(value, new_key, separator=separator).items())
else:
items.append((new_key, value))
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}
Ответ 2
Или, если вы уже используете pandas, вы можете сделать это с помощью json_normalize() вот так:
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])
Вывод:
{'a': 1, 'c_a': 2, 'c_b_x': 5, 'c_b_y': 10, 'd': [1, 2, 3]}
Ответ 3
Есть два важных соображения, которые необходимо учитывать при создании исходного плаката:
- Существуют ли проблемы с перегрузкой пространства ключей? Например,
{'a_b':{'c':1}, 'a':{'b_c':2}}это приведет к{'a_b_c':???}. Приведенное ниже решение позволяет избежать проблемы, возвращая повторяющиеся пары. - Если возникает проблема с производительностью, требует ли функция преобразования ключей (которую я здесь называю "join") доступа ко всему пути к ключу, или она может просто выполнять O (1) работу в каждом узле дерева? Если вы хотите иметь возможность говорить
joinedKey = '_'.join(*keys), это будет стоить вам O (N ^ 2) времени выполнения. Однако, если вы готовы говоритьnextKey = previousKey+'_'+thisKey, это даст вам O (N) времени. Приведенное ниже решение позволяет вам сделать и то, и другое (поскольку вы могли бы просто объединить все ключи, а затем обработать их после обработки).
(Производительность вряд ли является проблемой, но я подробнее остановлюсь на втором пункте на случай, если кого-то еще это волнует: при реализации этого существует множество опасных вариантов. Если вы делаете это рекурсивно и выдаете и повторно выдаете, или что-нибудь эквивалентное, которое затрагивает узлы более одного раза (что довольно легко случайно сделать), вы выполняете потенциально O (N ^ 2) работы, а не O (N). Это потому, что, возможно, вы вычисляете ключ 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=...) которая может быть адаптирована для многих целей и может делать то, что вы хотите. К сожалению, довольно сложно создать отложенную версию этой функции без вышеуказанных потерь производительности (многие встроенные в python функции, такие как chain.from_iterable, на самом деле неэффективны, что я понял только после тщательного тестирования трех разных версий этого кода, прежде чем остановиться на этой).
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 функция. Мы предварительно обрабатываем каждое kn с помощью 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)
Демонстрация (которую я бы в противном случае поместил в 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}
Производительность:
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
... вздох, не думай, что это моя вина...
[незначительная историческая справка из-за проблем с модерацией]
Что касается предполагаемого дубликата Сглаживания словаря словарей (глубиной 2 уровня) списков
Решение этого вопроса может быть реализовано в терминах этого, выполнив sorted( sum(flatten(...),[]) ). Обратное невозможно: хотя верно, что значения из flatten(...) могут быть восстановлены из предполагаемого дубликата путем сопоставления накопителя более высокого порядка, ключи восстановить невозможно. (редактировать: также оказывается, что вопрос предполагаемого владельца дубликата полностью отличается тем, что он имеет дело только со словарями глубиной ровно в 2 уровня, хотя один из ответов на этой странице дает общее решение.)
Ответ 4
Если вы используете pandas, в pandas.io.json._normalize1 есть функция, скрытая под названиемnested_to_record, которая делает именно это.
from pandas.io.json._normalize import nested_to_record
flat = nested_to_record(my_dict, sep='_')
1 В версиях pandas 0.24.x и более старых используется pandas.io.json.normalize (без _)