Есть два больших соображения, которые должен учитывать оригинальный плакат:
- Существуют ли проблемы с блокировкой пространства клавиш? Например,
{'a_b':{'c':1}, 'a':{'b_c':2}} приведет к {'a_b_c':???}. Приведенное ниже решение уклоняется от проблемы, возвращая повторяющиеся пары.
- Если производительность является проблемой, требуется ли функции ключа-редуктора (которую я здесь называю «объединением») доступ ко всему пути ключа, или она может просто выполнить O (1) на каждом узле в дерево? Если вы хотите сказать «1008», это будет стоить вам 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 функцией. Мы предварительно обрабатываем каждый 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
... вздох, не думай, что это моя вина ...
[неважная историческая справка из-за проблем с модерацией]
Относительно предполагаемого дубликата Свести словарь словарей (глубиной 2 уровня) списков в Python :
Решение этого вопроса можно реализовать с помощью этого sorted( sum(flatten(...),[]) ). Обратное невозможно: хотя верно то, что значения из flatten(...) могут быть восстановлены из предполагаемого дубликата путем сопоставления аккумулятора более высокого порядка, ключи не могут быть восстановлены. (редактировать: также выясняется, что вопрос о предполагаемом дубликате владельца совершенно другой, поскольку он касается только словарей ровно 2-уровневого уровня, хотя один из ответов на этой странице дает общее решение.)