Istnieją dwie ważne kwestie, które należy wziąć pod uwagę przy oryginalnym plakacie:
- Czy występują problemy z blokowaniem przestrzeni klawiszy? Na przykład
{'a_b':{'c':1}, 'a':{'b_c':2}}spowoduje to {'a_b_c':???}. Poniższe rozwiązanie pozwala uniknąć problemu, zwracając iterowalne pary.
- Jeśli wydajność jest problemem, czy funkcja redukcji klucza (którą tutaj nazywam „złączeniem”) wymaga dostępu do całej ścieżki klucza, czy może po prostu wykonać O (1) działanie w każdym węźle w drzewie? Jeśli chcesz móc powiedzieć
joinedKey = '_'.join(*keys), będzie cię to kosztować O (N ^ 2) czasu pracy. Jeśli jednak chcesz to powiedzieć nextKey = previousKey+'_'+thisKey, masz czas O (N). Poniższe rozwiązanie pozwala ci zrobić jedno i drugie (ponieważ możesz po prostu połączyć wszystkie klucze, a następnie przetworzyć je ponownie).
(Wydajność nie jest prawdopodobnie problemem, ale omówię drugi punkt na wypadek, gdyby ktokolwiek inny się tym przejmował: wdrażając to, istnieje wiele niebezpiecznych wyborów. Jeśli robisz to rekurencyjnie i dajesz i ponownie dajesz, lub cokolwiek równoważnego, co dotyka węzłów więcej niż raz (co jest dość łatwe do przypadkowego zrobienia), potencjalnie wykonujesz pracę O (N ^ 2) zamiast O (N). To dlatego, że być może obliczasz klucz, aa a_1potem a_1_i..., a potem obliczasz anastępnie a_1następnie a_1_ii..., ale tak naprawdę nie powinno mieć obliczyć a_1ponownie. Nawet jeśli nie są przeliczania go ponownie otrzymując go (podejście „poziom po poziomie”) jest tak źle. dobrym przykładem jest myśleć o występie na {1:{1:{1:{1:...(N times)...{1:SOME_LARGE_DICTIONARY_OF_SIZE_N}...}}}})
Poniżej znajduje się funkcja, którą napisałem, flattenDict(d, join=..., lift=...)która może być dostosowana do wielu celów i może robić, co chcesz. Niestety, dość trudno jest stworzyć leniwą wersję tej funkcji bez ponoszenia powyższych kar za wydajność (wiele wbudowanych funkcji Pythona, takich jak chain.from_iterable, nie jest w rzeczywistości wydajnych, co zdałem sobie sprawę dopiero po szeroko zakrojonych testach trzech różnych wersji tego kodu, zanim zdecydowałem się na ten).
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
Aby lepiej zrozumieć, co się dzieje, poniżej znajduje się diagram dla osób niezaznajomionych z reduce(po lewej), znanym również jako „złóż w lewo”. Czasami jest rysowany z wartością początkową zamiast k0 (nie jest częścią listy, przekazywana do funkcji). Oto Jnasza joinfunkcja. Przetwarzamy wstępnie każdy k n z 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
W rzeczywistości jest to to samo, co functools.reduce, ale gdzie nasza funkcja robi to ze wszystkimi kluczowymi ścieżkami drzewa.
>>> reduce(lambda a,b:(a,b), range(5))
((((0, 1), 2), 3), 4)
Demonstracja (którą w innym przypadku umieściłbym w dokumentacji):
>>> 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}
Występ:
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
... westchnij, nie myśl, że to moja wina ...
[nieważna notatka historyczna z powodu problemów z moderacją]
Odnośnie domniemanego duplikatu Flatten słownika słowników (głęboki na 2 poziomy) list w Pythonie :
Rozwiązanie tego pytania można zaimplementować w ramach tego przez działanie sorted( sum(flatten(...),[]) ). Odwrotna nie jest możliwe: ile jest prawdą, że wartość z flatten(...)może być odzyskany z domniemanym podwójnie przez akumulator mapowania wyższego rzędu, to nie można odzyskać kluczy. (edytuj: Okazuje się również, że pytanie domniemanego powielonego właściciela jest zupełnie inne, ponieważ dotyczy tylko słowników o głębokości dokładnie 2 poziomów, chociaż jedna z odpowiedzi na tej stronie daje ogólne rozwiązanie.)