Mam taki słownik:
{ "id" : "abcde",
"key1" : "blah",
"key2" : "blah blah",
"nestedlist" : [
{ "id" : "qwerty",
"nestednestedlist" : [
{ "id" : "xyz",
"keyA" : "blah blah blah" },
{ "id" : "fghi",
"keyZ" : "blah blah blah" }],
"anothernestednestedlist" : [
{ "id" : "asdf",
"keyQ" : "blah blah" },
{ "id" : "yuiop",
"keyW" : "blah" }] } ] }
Zasadniczo słownik z zagnieżdżonymi listami, słownikami i ciągami znaków o dowolnej głębokości.
Jaki jest najlepszy sposób na przejście przez to w celu wyodrębnienia wartości każdego klucza „id”? Chcę uzyskać odpowiednik kwerendy XPath, taki jak „// id”. Wartość „id” jest zawsze ciągiem.
Z mojego przykładu wynik, którego potrzebuję, to w zasadzie:
["abcde", "qwerty", "xyz", "fghi", "asdf", "yuiop"]
Porządek nie jest ważny.
python
recursion
dictionary
traversal
Matt Swain
źródło
źródło
None
jako dane wejściowe. Zależy Ci na solidności? (ponieważ jest to teraz używane jako pytanie kanoniczne)Odpowiedzi:
Wydaje mi się, że to pytanie / odpowiedzi jest bardzo interesujące, ponieważ zawiera kilka różnych rozwiązań tego samego problemu. Wziąłem wszystkie te funkcje i przetestowałem je na złożonym obiekcie słownikowym. Musiałem usunąć dwie funkcje z testu, ponieważ miały wiele wyników niepowodzeń i nie obsługiwały zwracania list lub dyktowania jako wartości, co uważam za niezbędne, ponieważ funkcja powinna być przygotowana dla prawie wszystkich danych, które mają nadejść.
Więc przepompowałem inne funkcje w 100.000 iteracjach przez
timeit
moduł i wyjście dało następujący wynik:0.11 usec/pass on gen_dict_extract(k,o) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 6.03 usec/pass on find_all_items(k,o) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0.15 usec/pass on findkeys(k,o) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1.79 usec/pass on get_recursively(k,o) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0.14 usec/pass on find(k,o) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0.36 usec/pass on dict_extract(k,o) - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Wszystkie funkcje miały tę samą igłę do wyszukiwania („logowanie”) i ten sam obiekt słownikowy, który jest zbudowany w następujący sposób:
o = { 'temparature': '50', 'logging': { 'handlers': { 'console': { 'formatter': 'simple', 'class': 'logging.StreamHandler', 'stream': 'ext://sys.stdout', 'level': 'DEBUG' } }, 'loggers': { 'simpleExample': { 'handlers': ['console'], 'propagate': 'no', 'level': 'INFO' }, 'root': { 'handlers': ['console'], 'level': 'DEBUG' } }, 'version': '1', 'formatters': { 'simple': { 'datefmt': "'%Y-%m-%d %H:%M:%S'", 'format': '%(asctime)s - %(name)s - %(levelname)s - %(message)s' } } }, 'treatment': {'second': 5, 'last': 4, 'first': 4}, 'treatment_plan': [[4, 5, 4], [4, 5, 4], [5, 5, 5]] }
Wszystkie funkcje dały ten sam wynik, ale różnice czasowe są dramatyczne! Funkcja
gen_dict_extract(k,o)
jest moją funkcją zaadaptowaną z funkcji tutaj, w rzeczywistości jest prawie podobna dofind
funkcji z Alfe, z tą główną różnicą, że sprawdzam, czy dany obiekt ma funkcję iteritems, w przypadku, gdy ciągi są przekazywane podczas rekurencji:def gen_dict_extract(key, var): if hasattr(var,'iteritems'): for k, v in var.iteritems(): if k == key: yield v if isinstance(v, dict): for result in gen_dict_extract(key, v): yield result elif isinstance(v, list): for d in v: for result in gen_dict_extract(key, d): yield result
Więc ten wariant jest najszybszą i najbezpieczniejszą z funkcji tutaj. I
find_all_items
jest niesamowicie powolny i daleko od drugiego najwolniejszego,get_recursivley
podczas gdy reszta, z wyjątkiemdict_extract
, jest blisko siebie. Funkcjefun
ikeyHole
działają tylko wtedy, gdy szukasz ciągów.Ciekawy aspekt uczenia się tutaj :)
źródło
gen_dict_extract(keys, var)
(2) wstawfor key in keys:
jako wiersz 2 iyield {key: v}
next(functionname(k, o)
dla wszystkich rozwiązań generatorów.hasattr(var, 'items')
dla pythona3if hasattr
części dla wersji używającejtry
do przechwytywania wyjątku w przypadku niepowodzenia wywołania (zobacz pastebin.com/ZXvVtV0g dla możliwej implementacji)? Zmniejszyłoby to podwojone wyszukiwanie atrybutuiteritems
(razhasattr()
i raz dla wywołania), a tym samym prawdopodobnie skróciło czas wykonywania (co wydaje się ważne). Nie wykonałem jednak żadnych testów porównawczych.iteritems
tak się stałoitems
.d = { "id" : "abcde", "key1" : "blah", "key2" : "blah blah", "nestedlist" : [ { "id" : "qwerty", "nestednestedlist" : [ { "id" : "xyz", "keyA" : "blah blah blah" }, { "id" : "fghi", "keyZ" : "blah blah blah" }], "anothernestednestedlist" : [ { "id" : "asdf", "keyQ" : "blah blah" }, { "id" : "yuiop", "keyW" : "blah" }] } ] } def fun(d): if 'id' in d: yield d['id'] for k in d: if isinstance(d[k], list): for i in d[k]: for j in fun(i): yield j
>>> list(fun(d)) ['abcde', 'qwerty', 'xyz', 'fghi', 'asdf', 'yuiop']
źródło
for k in d
, abyfor k,value in d.items()
z późniejszego wykorzystaniavalue
zamiastd[k]
.gen_dict_extract
d = { "id" : "abcde", "key1" : "blah", "key2" : "blah blah", "nestedlist" : [ { "id" : "qwerty", "nestednestedlist" : [ { "id" : "xyz", "keyA" : "blah blah blah" }, { "id" : "fghi", "keyZ" : "blah blah blah" }], "anothernestednestedlist" : [ { "id" : "asdf", "keyQ" : "blah blah" }, { "id" : "yuiop", "keyW" : "blah" }] } ] } def findkeys(node, kv): if isinstance(node, list): for i in node: for x in findkeys(i, kv): yield x elif isinstance(node, dict): if kv in node: yield node[kv] for j in node.values(): for x in findkeys(j, kv): yield x print(list(findkeys(d, 'id')))
źródło
def find(key, value): for k, v in value.iteritems(): if k == key: yield v elif isinstance(v, dict): for result in find(key, v): yield result elif isinstance(v, list): for d in v: for result in find(key, d): yield result
EDYCJA: @Anthon zauważył, że to nie zadziała w przypadku list zagnieżdżonych bezpośrednio. Jeśli masz to w swoim wejściu, możesz użyć tego:
def find(key, value): for k, v in (value.iteritems() if isinstance(value, dict) else enumerate(value) if isinstance(value, list) else []): if k == key: yield v elif isinstance(v, (dict, list)): for result in find(key, v): yield result
Ale myślę, że oryginalna wersja jest łatwiejsza do zrozumienia, więc zostawię ją.
źródło
isinstance
czeku na a,dict
zanim ostatnie dwie linie to rozwiązują.Inna odmiana, która zawiera zagnieżdżoną ścieżkę do znalezionych wyników ( uwaga: ta wersja nie uwzględnia list ):
def find_all_items(obj, key, keys=None): """ Example of use: d = {'a': 1, 'b': 2, 'c': {'a': 3, 'd': 4, 'e': {'a': 9, 'b': 3}, 'j': {'c': 4}}} for k, v in find_all_items(d, 'a'): print "* {} = {} *".format('->'.join(k), v) """ ret = [] if not keys: keys = [] if key in obj: out_keys = keys + [key] ret.append((out_keys, obj[key])) for k, v in obj.items(): if isinstance(v, dict): found_items = find_all_items(v, key, keys=(keys+[k])) ret += found_items return ret
źródło
Chciałem tylko powtórzyć doskonałą odpowiedź @ hexerei-software, używając
yield from
i akceptując listy najwyższego poziomu.def gen_dict_extract(var, key): if isinstance(var, dict): for k, v in var.items(): if k == key: yield v if isinstance(v, (dict, list)): yield from gen_dict_extract(v, key) elif isinstance(var, list): for d in var: yield from gen_dict_extract(d, key)
źródło
for key in keys
. Dodałem również do drugiego,isinstance
aby(list, tuple)
uzyskać jeszcze większą różnorodność. ;)Ta funkcja rekurencyjnie przeszukuje słownik zawierający zagnieżdżone słowniki i listy. Tworzy listę o nazwie fields_found, która zawiera wartość dla każdego znalezionego pola. „Pole” to klucz, którego szukam w słowniku oraz jego zagnieżdżonych listach i słownikach.
źródło
Oto moja próba:
def keyHole(k2b,o): # print "Checking for %s in "%k2b,o if isinstance(o, dict): for k, v in o.iteritems(): if k == k2b and not hasattr(v, '__iter__'): yield v else: for r in keyHole(k2b,v): yield r elif hasattr(o, '__iter__'): for r in [ keyHole(k2b,i) for i in o ]: for r2 in r: yield r2 return
Dawny.:
>>> findMe = {'Me':{'a':2,'Me':'bop'},'z':{'Me':4}} >>> keyHole('Me',findMe) <generator object keyHole at 0x105eccb90> >>> [ x for x in keyHole('Me',findMe) ] ['bop', 4]
źródło
Postępując zgodnie z odpowiedzią oprogramowania @hexerei i komentarzem @ bruno-bronosky, jeśli chcesz iterować listę / zestaw kluczy:
def gen_dict_extract(var, keys): for key in keys: if hasattr(var, 'items'): for k, v in var.items(): if k == key: yield v if isinstance(v, dict): for result in gen_dict_extract([key], v): yield result elif isinstance(v, list): for d in v: for result in gen_dict_extract([key], d): yield result
Zauważ, że przekazuję listę z jednym elementem ([klucz]} zamiast klucza ciągu.
źródło