在Python中搜索字典树中的值

Question

我有一个巨大的字典，其中包含许多嵌套的字典——就像一棵巨大的树，深度未知。

我需要一个函数，类似于 `find_value()`，它接受 `dict` 和 `value`（作为字符串），并返回一个列表，其中每个列表都是“路径”（从第一个键到找到值的键或键值的连续链）。如果没有找到，则返回空列表。

我编写了以下代码：

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打印出正确的结果（我已经检查过了！），但结果仍然不可解释地损坏了。也许是递归魔法导致的？

有人能帮我解决这个问题吗？也许有一个简单的解决方案可以完成我的任务？

- Bruno Gelb

---

你为什么更喜欢非递归？你预计树的深度会很深，以至于你担心会发生堆栈溢出吗？ - Gabe

问题是，如果你的树没有某些属性，你就必须扫描整个树。在我看来，你的函数有点过于复杂了，因为它是递归的，并且试图用堆栈来模拟递归。你应该选择其中一种方法 :) 参见这里以了解模拟的方法。 - Laur Ivan

这应该是递归的。 - piokuc

你想让我为你调试它还是正式证明它的正确性？ - piokuc

我不知道为什么，但现在我都不想做这两件事。我只能给你一个建议 - 睁开你的眼睛！递归很酷！;) - piokuc

Answer 1

我觉得你不太可能对这样的递归搜索进行优化。如果假设在同一个字典上有很多查找，并且一旦加载字典就不会再改变，那么你可以对其进行索引以获得O(1)的查找效率...

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']]

- Aya

---

谢谢，亲切的先生，如果我以后需要性能，我一定会使用您的想法 :) - Bruno Gelb

Answer 2

当您编写result.append(current_path)时，您并没有复制current_path，它将继续发生变异。请将其更改为result.append(current_path[:])。

- David Eisenstat

---

我真是太惊讶了。你找到了那个 bug！！！现在它通过了所有的测试！你就是上帝创造的美丽之作。 - Bruno Gelb