Znajdź wszystkie wystąpienia klucza w zagnieżdżonych słownikach i listach

87

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.

Matt Swain
źródło
Większość twoich rozwiązań wybuchnie, jeśli przejdziemy Nonejako dane wejściowe. Zależy Ci na solidności? (ponieważ jest to teraz używane jako pytanie kanoniczne)
smci

Odpowiedzi:

74

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 timeitmoduł 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 do findfunkcji 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_itemsjest niesamowicie powolny i daleko od drugiego najwolniejszego, get_recursivleypodczas gdy reszta, z wyjątkiem dict_extract, jest blisko siebie. Funkcje funi keyHoledziałają tylko wtedy, gdy szukasz ciągów.

Ciekawy aspekt uczenia się tutaj :)

oprogramowanie hexerei
źródło
1
Jeśli chcesz wyszukać wiele kluczy, tak jak ja, po prostu: (1) zmień na gen_dict_extract(keys, var)(2) wstaw for key in keys:jako wiersz 2 i yield {key: v}
dodaj
6
Porównujesz jabłka do pomarańczy. Uruchomienie funkcji zwracającej generator zajmuje mniej czasu niż uruchomienie funkcji zwracającej wynik końcowy. Wypróbuj czas next(functionname(k, o)dla wszystkich rozwiązań generatorów.
kaleissin
6
hasattr(var, 'items')dla pythona3
gobrewers14
1
Czy rozważałeś usunięcie if hasattrczęści dla wersji używającej trydo przechwytywania wyjątku w przypadku niepowodzenia wywołania (zobacz pastebin.com/ZXvVtV0g dla możliwej implementacji)? Zmniejszyłoby to podwojone wyszukiwanie atrybutu iteritems(raz hasattr()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.
Alfe
2
Dla każdego, kto odwiedza tę stronę teraz, gdy Python 3 przejął kontrolę, pamiętaj, że iteritemstak się stało items.
Mike Williamson
46
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']
kev
źródło
Jedyną rzeczą, którą chciałbym zmienić to for k in d, aby for k,value in d.items()z późniejszego wykorzystania valuezamiast d[k].
ovgolovin
Dzięki, to działa świetnie. Wymagana bardzo niewielka modyfikacja, ponieważ moje listy mogą zawierać zarówno ciągi znaków, jak i dykty (o których nie wspomniałem), ale poza tym doskonałe.
Matt Swain,
1
To pasuje do bardzo wąskiego przypadku, jesteś winien sobie rozważyć odpowiedź od "hexerei software" o nazwiegen_dict_extract
Bruno Bronosky
Pojawił się błąd „TypeError: argument typu„ NoneType ”nie jest
iterowalny
2
Wydaje się, że to rozwiązanie nie obsługuje list
Alex R
23
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')))
arainchi
źródło
1
Ten przykład działał z każdym złożonym słownikiem, który testowałem. Dobra robota.
Powinna to być akceptowana odpowiedź, może znaleźć klucze, które znajdują się w słownikach zagnieżdżonych na listach list itp.
Anthon
Działa to również w Python3, o ile instrukcja print na końcu jest zmodyfikowana. Żadne z powyższych rozwiązań nie działało w przypadku odpowiedzi API z listami zagnieżdżonymi w dyktach wymienionych na listach itp., Ale to działało pięknie.
Andy Forceno
21
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ą.

Alfe
źródło
1
Działa to również świetnie, ale również napotyka problemy, jeśli napotka listę, która bezpośrednio zawiera ciąg (którego zapomniałem uwzględnić w moim przykładzie). Myślę, że dodanie isinstanceczeku na a, dictzanim ostatnie dwie linie to rozwiązują.
Matt Swain,
1
Dziękuję za pochwały, ale byłbym bardziej dumny z ich otrzymania za czystość mojego kodu niż za jego szybkość.
Alfe
1
W 95% przypadków tak. Pozostałe (rzadkie) sytuacje to te, w których pewne ograniczenia czasowe mogą zmusić mnie do wybrania szybszej wersji niż czystszej. Ale mi się to nie podoba. To zawsze oznacza obciążenie mojego następcy, który będzie musiał utrzymywać ten kod. Jest to ryzyko, ponieważ mój następca może się pomylić. Będę musiał wtedy napisać wiele komentarzy, może cały dokument wyjaśniający moje motywacje, czas eksperymentów, ich wyniki itp. To o wiele więcej pracy dla mnie i wszystkich kolegów, aby zrobić to dobrze. Czystsze jest o wiele prostsze.
Alfe
2
@Alfe - dzięki za tę odpowiedź. Musiałem wyodrębnić wszystkie wystąpienia ciągu w zagnieżdżonym dyktandzie dla konkretnego przypadku użycia Elasticsearch i ten kod był przydatny z niewielką modyfikacją - stackoverflow.com/questions/40586020/…
Saurabh Hirani
1
To całkowicie zrywa na listach bezpośrednio zawartych w listach.
Anthon
5

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
Dolan Antenucci
źródło
5

Chciałem tylko powtórzyć doskonałą odpowiedź @ hexerei-software, używając yield fromi 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)
Chris
źródło
Doskonały mod do odpowiedzi @ hexerei-software: zwięzły i zezwala na listy poleceń! Używam tego wraz z sugestiami @ bruno-bronosky w jego komentarzach for key in keys. Dodałem również do drugiego, isinstanceaby (list, tuple)uzyskać jeszcze większą różnorodność. ;)
Cometsong,
4

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.

def get_recursively (search_dict, field):
    "" "Pobiera dyktando z zagnieżdżonymi listami i dyktami,
    i przeszukuje wszystkie dykty pod kątem klucza pola
    opatrzony.
    „”
    fields_found = []

    dla klucza, wartość w search_dict.iteritems ():

        if key == pole:
            fields_found.append (wartość)

        elif isinstance (wartość, dict):
            wyniki = get_recursively (wartość, pole)
            dla wyniku w wynikach:
                fields_found.append (wynik)

        elif isinstance (wartość, lista):
            dla pozycji wartościowej:
                if isinstance (item, dict):
                    more_results = get_recursively (pozycja, pole)
                    for another_result w more_results:
                        fields_found.append (another_result)

    return fields_found
Becca Petrin
źródło
1
Możesz użyć fields_found.extend (more_results) zamiast uruchamiać kolejną pętlę. Moim zdaniem wyglądałby nieco czystszy.
sapit
0

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]
AX Labs
źródło
0

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.

João Henriques
źródło