3

我有一个巨大的字典，里面有很多嵌套的字典——就像一棵巨树，深度未知。

我需要一个函数，比如find_value()，它接受dict, value (as string)并返回列表列表，它们中的每一个都是“路径”（从第一个键到键（或键值）的键的顺序链与找到的值）。如果没有找到，则返回空列表。

我写了这段代码：

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打印正确的东西（它总是这样，我检查了！），结果莫名其妙地损坏了。也许是因为递归魔法？

谁能帮我解决这个问题？也许我的任务有一个简单的解决方案？

4

2 回答 2

2

当你写的时候result.append(current_path)，你不是在复制current_path，它会继续变异。将其更改为result.append(current_path[:]).

于 2013-04-29T21:01:30.550 回答
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']]
于 2013-04-29T21:01:43.683 回答