Znalezienie klucza rekurencyjnie w słowniku

Question

Próbuję napisać bardzo prostą funkcję rekursywnie przeglądać ewentualnie zagnieżdżone (w najbardziej skrajnych przypadkach głębokich dziesięć poziomów) słownika Python i powrócić pierwszej wartości stwierdzi z danego klawisza .

Nie mogę zrozumieć, dlaczego mój kod nie działa dla zagnieżdżonych słowników.

def _finditem(obj, key): 
    if key in obj: return obj[key] 
    for k, v in obj.items(): 
     if isinstance(v,dict): 
      _finditem(v, key) 

print _finditem({"B":{"A":2}},"A") 

Zwraca None.

To działa, jednak dla _finditem({"B":1,"A":2},"A"), wracając 2.

Jestem pewien, że to prosty błąd, ale nie mogę go znaleźć. Czuję, że może być coś takiego w standardowej bibliotece lub collections, ale nie mogę tego znaleźć.

Answer 1

gdy rekursja, trzeba return wynik _finditem

def _finditem(obj, key): 
    if key in obj: return obj[key] 
    for k, v in obj.items(): 
     if isinstance(v,dict): 
      return _finditem(v, key) #added return statement 

Aby rozwiązać rzeczywiste algorytm, trzeba zdać sobie sprawę, że _finditem powraca None jeśli nie znaleźliśmy niczego, więc trzeba sprawdzić jawnie, aby zapobiec wczesnego powrotu:

def _finditem(obj, key): 
    if key in obj: return obj[key] 
    for k, v in obj.items(): 
     if isinstance(v,dict): 
      item = _finditem(v, key) 
      if item is not None: 
       return item 

oczywiście, że nie powiedzie się, jeśli masz None wartości w dowolnych słowników. W takim przypadku możesz ustawić funkcję wartownika object() dla tej funkcji i zwrócić ją w przypadku, gdy niczego nie znajdziesz - Następnie możesz sprawdzić w stosunku do sentinel, aby dowiedzieć się, czy coś znalazłeś, czy nie.

Answer 2

Oto funkcja, która przeszukuje słownika, który zawiera zarówno zagnieżdżonych słowniki i listy. Tworzy listę wartości wyników.

def get_recursively(search_dict, field): 
    """ 
    Takes a dict with nested lists and dicts, 
    and searches all dicts for a key of the field 
    provided. 
    """ 
    fields_found = [] 

    for key, value in search_dict.iteritems(): 

     if key == field: 
      fields_found.append(value) 

     elif isinstance(value, dict): 
      results = get_recursively(value, field) 
      for result in results: 
       fields_found.append(result) 

     elif isinstance(value, list): 
      for item in value: 
       if isinstance(item, dict): 
        more_results = get_recursively(item, field) 
        for another_result in more_results: 
         fields_found.append(another_result) 

    return fields_found 

Answer 3

Oto sposób to zrobić za pomocą "stos" oraz "stack of iterators" pattern (kredyty na Gareth Rees):

def search(d, key, default=None): 
    """Return a value corresponding to the specified key in the (possibly 
    nested) dictionary d. If there is no item with that key, return 
    default. 
    """ 
    stack = [iter(d.items())] 
    while stack: 
     for k, v in stack[-1]: 
      if isinstance(v, dict): 
       stack.append(iter(v.items())) 
       break 
      elif k == key: 
       return v 
     else: 
      stack.pop() 
    return default 

print(search({"B": {"A": 2}}, "A")) będzie drukować 2.