python - 字典：如何列出包含特定值的每个键路径？(Dictionary: How to list every key path that contains a certain value?)

Question

Let's say I've got a nested dictionary of the form:

(假设我有以下形式的嵌套字典：)

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

How can you work your way through that dict and make a list of each complete key path that contains the value 'white' ?

(如何处理该字典，并列出包含值'white'的每个完整键路径的列表？)

Using a function defined by user jfs in the post Search for a value in a nested dictionary python lets you check whether or not 'white' occurs at least one time and also returns the path:

(使用帖子中的用户jfs定义的功能在嵌套字典python中搜索值可让您检查'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')

But 'white' occurs other places too, like in :

(但是“白色”也发生在其他地方，例如：)

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

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

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

(2： d['geo']['caxis']['gridcolor'])

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

(3： d['yaxis']['linecolor'])

How can I make sure that the function finds all paths?

(我如何确保该功能找到所有路径？)

I've tried applying the function above until it returns none while eliminating found paths one by one, but that quickly turned into an ugly mess.

(我尝试应用上面的函数，直到它none同时一一消除找到的路径，但是很快就变成了一个丑陋的混乱局面。)

Thank you for any suggestions!

(感谢您的任何建议！)

  ask by vestland translate from so

Answer 1

This is a perfect use case to write a generator:

(这是编写生成器的完美用例：)

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)

You can use it as follows:

(您可以按以下方式使用它：)

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))

The generator approach has the advantage that it doesn't need to create an object to keep all paths in memory at once;

(生成器方法的优点是无需创建对象即可一次将所有路径保留在内存中；)

they can be processed one by one and immediately discarded.

(可以将它们一一处理并立即丢弃。)

In this case, the memory savings would be rather modest, but in others they may be significant.

(在这种情况下，内存节省将是相当有限的，但在其他情况下，它们可能是可观的。)

Also, if a loop iterating over a generator is terminated early, the generator is not going to keep searching for more paths that would be later discarded anyway.

(同样，如果在生成器上进行迭代的循环提前终止，则生成器将不会继续搜索更多路径，无论如何这些路径以后都会被丢弃。)