Python--在嵌套字典中查找特定值的父键 [英] Python--Finding Parent Keys for a specific value in a nested dictionary

问题描述

我正在努力处理嵌套字典，并为特定值返回嵌套的父键，当该值在嵌套字典中可能存在多次时.例如:

example_dict = { 'key1' : 'value1','key2':'值2'，'key3' : { 'key3a': 'value3a' },'key4':{'key4a':{'key4aa':'value4aa'，'key4ab': 'value4ab','key4ac': 'value1'},'key4b': 'value4b'}}

您会注意到value1"在上述字典中出现了两次，我想创建一个函数，该函数返回单个列表或一系列列表，用于标识不同的父键，在这种情况下是 'key1' 和 ('key4', 'key4a', key4ac).

这种类型的问题在本网站的其他地方已经处理过，当时寻找的值只出现一次，并且可以通过以下递归函数轻松处理:

def find_key(d,key):对于 d.items() 中的 k,v:如果 isinstance(v,dict):p = find_key(v,key)如果 p:返回 [k] + pelif v == 键:返回 [k]打印 find_key(example_dict,'value4ac').

如果你在字典上运行上面的代码，我只能得到一个父键的答案.任何帮助将非常感激，谢谢！

解决方案

除非你只是做一个单一的搜索(或者你的内存非常有限但有 CPU 时间来消耗......)，你会想要构建一个反向查找字典，然后你就可以使用它了.

<小时>

为了使这更容易，我将分两步完成.首先，将嵌套字典转换为键路径字典:

def 键路径(嵌套):对于键，nested.iteritems() 中的值:如果 isinstance(value, collections.Mapping):对于子键，键路径中的子值(值):yield [key] + subkey, subvalue别的:产量[键]，值

打印出list(keypaths(example_dict))，如果它的作用不明显.

<小时>

现在，如何创建反向字典?对于一对一映射，您可以这样做:

reverse_dict = {value: keypath for keypath, value in keypaths(example_dict)}

但是对于像您这样的多对一映射，相反的是一对多，因此我们需要将每个值映射到一个键列表.所以:

reverse_dict = {}对于 keypath，keypaths(example_dict) 中的值:reverse_dict.setdefault(value, []).append(keypath)

现在你不需要任何花哨的东西；只需在 reverse_dict 上做一个普通的 dict 查找:

<预><代码>>>>reverse_dict['value2'][('key2',)]>>>reverse_dict['value1'][('key1',), ('key4', 'key4a', 'key4ac')]>>>reverse_dict['value3']键错误:'value3'

<小时>

如果您希望最后一个返回 [] 而不是引发 KeyError，您可以使用 defaultdict(list)而不是一个普通的dict，然后你就不需要setdefault.

<小时>

无论如何，构建这个反向映射所花费的时间只比用蛮力进行单次搜索所花费的时间长一点，所以如果你进行 100 次搜索，它会快近 100 倍方式，以及更简单.

I am struggling to process a nested dictionary, and return the nested Parent Keys, for a specific Value, when the Value may exist more than once in the nested dictionary. For example:

example_dict = { 'key1' : 'value1',
                 'key2' : 'value2',
                 'key3' : { 'key3a': 'value3a' },
                 'key4' : { 'key4a': { 'key4aa': 'value4aa',
                                       'key4ab': 'value4ab',
                                       'key4ac': 'value1'},
                            'key4b': 'value4b'}
                }

You will notice that 'value1' appears twice in the above dictionary, and I would like to create a function that returns either a single list, or a series of lists, that identify the different Parent Keys, which in this case would be 'key1' and ('key4', 'key4a', key4ac).

This type of problem was dealt with elsewhere on this site, when the Value one was looking for only appeared once, and was readily handled by the following recursive function:

def find_key(d,key):
    for k,v in d.items():
        if isinstance(v,dict):
            p = find_key(v,key)
            if p:
                return [k] + p
        elif v == key:
            return [k]

print find_key(example_dict,'value4ac').

If you run the above code on the dictionary, I only get one answer for the parent keys. Any help would be much appreciated, Thanks!

解决方案

Unless you're just doing a single search (or you're incredibly constrained on memory but have CPU time to burn…), you'll want to build a reverse-lookup dictionary, and then you can just use that.

---

To make that easier, I'm going to do it in two steps. First, convert a nested dictionary to a key-path dictionary:

def keypaths(nested):
    for key, value in nested.iteritems():
        if isinstance(value, collections.Mapping):
            for subkey, subvalue in keypaths(value):
                yield [key] + subkey, subvalue
        else:
            yield [key], value

Print out list(keypaths(example_dict)) if it isn't obvious what this does.

---

Now, how do you create a reverse dictionary? For a one-to-one-mapping, you can just do this:

reverse_dict = {value: keypath for keypath, value in keypaths(example_dict)}

But for a many-to-one mapping like yours, the reverse is one-to-many, so we need to map each value to a list of keys. So:

reverse_dict = {}
for keypath, value in keypaths(example_dict):
    reverse_dict.setdefault(value, []).append(keypath)

And now you don't need anything fancy; just do a normal dict lookup on reverse_dict:

>>> reverse_dict['value2']
[('key2',)]
>>> reverse_dict['value1']
[('key1',), ('key4', 'key4a', 'key4ac')]
>>> reverse_dict['value3']
KeyError: 'value3'

---

If you'd prefer the last one to return [] instead of raising a KeyError, you can use a defaultdict(list) instead of a plain dict, and then you don't need setdefault.

---

At any rate, the time taken to construct this reverse mapping is only a little longer than the time taken to do a single search by brute force, so if you're doing 100 searches, it'll be nearly 100x faster this way, as well as simpler.

这篇关于Python--在嵌套字典中查找特定值的父键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！