Значение поиска в дереве dicts в python

Question

У меня есть гигантский dict с множеством вложенных dicts - как гигантское дерево, и глубина в неизвестности.

мне нужна функция, что-то вроде find_value(), который принимает Dict, значение (как строка) и возвращает список списков, каждый из них является «путь» (последовательная цепочка ключей от первого ключа к ключ (или значение ключа) с найденным значением). Если ничего не найдено, возвращает пустой список.

Я написал этот код:

def find_value(dict, sought_value, current_path, result): 
    for key,value in dict.items(): 
     current_path.pop() 
     current_path.append(key) 
     if sought_value in key: 
      result.append(current_path) 
     if type(value) == type(''): 
      if sought_value in value: 
       result.append(current_path+[value]) 
     else: 
      current_path.append(key) 
      result = find_value(value, sought_value, current_path, result) 
    current_path.pop() 
    return result 

Я называю эту функцию для проверки:

result = find_value(self.dump, sought_value, ['START_KEY_FOR_DELETE'], []) 
if not len(result): 
    print "forgive me, mylord, i'm afraid we didn't find him.." 
elif len(result) == 1: 
    print "bless gods, for all that we have one match, mylord!" 

Для некоторых необъяснимых причин, моя реализация этой функции не удается некоторые из моих тестов. Я начал отлаживать и узнавать, что даже если current_path печатает правильные вещи (это всегда делает, я проверил!), Результат необъяснимо искажен. Может быть, это из-за рекурсивной магии?

Может ли кто-нибудь помочь мне с этой проблемой? Может быть, есть простое решение для моих задач?

Answer 1

Когда вы пишете result.append(current_path), вы не копируете current_path, который продолжает мутировать. Измените его на result.append(current_path[:]).

Answer 2

Я сомневаюсь, что вы можете многое сделать для оптимизации рекурсивного поиска. Предполагая, что есть много на поиски того же словаря, и словарь не изменяется после загрузки, то вы можете индексировать его, чтобы получить O (1) Lookups ...

def build_index(src, dest, path=[]): 
    for k, v in src.iteritems(): 
     fk = path+[k] 
     if isinstance(v, dict): 
      build_index(v, dest, fk) 
     else: 
      try: 
       dest[v].append(fk) 
      except KeyError: 
       dest[v] = [fk] 

>>> data = {'foo': {'sub1': 'blah'}, 'bar': {'sub2': 'whatever'}, 'baz': 'blah'} 
>>> index = {} 
>>> build_index(data, index) 
>>> index 
{'blah': [['baz'], ['foo', 'sub1']], 'whatever': [['bar', 'sub2']]} 
>>> index['blah'] 
[['baz'], ['foo', 'sub1']]