python - 字典:如何列出包含某个值的每个关键路径？

Question

假设我有一个以下形式的嵌套字典:

{'geo': {'bgcolor': 'white','lakecolor': 'white','caxis': {'gridcolor': 'white', 'linecolor': 'white',}},
 'title': {'x': 0.05},
 'yaxis': {'automargin': True,'linecolor': 'white','zerolinecolor': 'white','zerolinewidth': 2}
 }

如何通过该字典工作并列出包含值'white'的每个完整关键路径？使用帖子 Search for a value in a nested dictionary python 中用户 jfs 定义的函数让您检查 'white' 是否至少出现一次并返回路径:

# dictionary
    d={'geo': {'bgcolor': 'white','lakecolor': 'white','caxis': {'gridcolor': 'white', 'linecolor': 'white',}},
    'title': {'x': 0.05},
    'yaxis': {'automargin': True,'linecolor': 'white','ticks': '','zerolinecolor': 'white','zerolinewidth': 2}
  }

# function:
def getpath(nested_dict, value, prepath=()):
    for k, v in nested_dict.items():
        path = prepath + (k,)
        if v == value: # found value
            return path
        elif hasattr(v, 'items'): # v is a dict
            p = getpath(v, value, path) # recursive call
            if p is not None:
                return p
getpath(d,'white')

# out:
('geo', 'bgcolor')

但是“白色”也出现在其他地方，例如:

1. d['geo']['lakecolor']

2: d['geo']['caxis']['gridcolor']

3: d['yaxis']['linecolor']

如何确保该函数找到所有路径？

我尝试应用上面的函数，直到它返回none，同时逐一消除找到的路径，但这很快就变得一团糟。

谢谢您的建议!

Answer 1

这是编写生成器的完美用例:

def find_paths(haystack, needle):
    if haystack == needle:
        yield ()
    if not isinstance(haystack, dict):
        return
    for key, val in haystack.items():
        for subpath in find_paths(val, needle):
            yield (key, *subpath)

您可以按如下方式使用它:

d = {
    'geo': {'bgcolor': 'white','lakecolor': 'white','caxis': {'gridcolor': 'white', 'linecolor': 'white',}},
    'title': {'x': 0.05},
    'yaxis': {'automargin': True,'linecolor': 'white','ticks': '','zerolinecolor': 'white','zerolinewidth': 2}
}

# you can iterate over the paths directly...
for path in find_paths(d, 'white'):
    print('found at path: ', path)

# ...or you can collect them into a list:
paths = list(find_paths(d, 'white'))
print('found at paths: ' + repr(paths))

生成器方法的优点是它不需要创建一个对象来一次将所有路径保留在内存中；它们可以被一一处理并立即丢弃。在这种情况下，内存节省将相当有限，但在其他情况下，它们可能会很大。此外，如果对生成器进行迭代的循环提前终止，则生成器将不会继续搜索更多随后将被丢弃的路径。