如何有效地在 defaultdict 中进行反向查找？

Question

我在发布这个问题之前做了一些搜索，似乎有几种不同的方法可以完成这个。

但是目前最有效的方法是什么（使用 Python 3）根据 defaultdict 中的特定值搜索键，看起来像这样：

defaultdict(list,
            {'a': [[2, 3], [1, 2]],
             'b': [[5, 6]],
             'w': [[]],
             'x': [[9]],
             'z': [[5, 6]]})

我想找到所有值为 6 的键。一种解决方案是编写一个嵌套的 for 循环来迭代键，defaultdict 的值，但我确信有一个更好的方法来完成这个。

Answer 1

您可以使用 itertools 模块中的 chain.from_iterable，就像这个例子：

from itertools import chain 

a = defaultdict(list,
            {'a': [[2, 3], [1, 2]],
             'b': [[5, 6]],
             'w': [[]],
             'x': [[9]],
             'z': [[5, 6]]})

keys =  [k for k, v in a.items() if 6 in chain.from_iterable(v)]
print(keys)

或者，以更紧凑的方式，您可以定义一个函数来查找 defaultdict 的值：

def get_keys(a, key=6):
    return [k for k, v in a.items() if key in chain.from_iterable(v)]

keys = get_keys(a)
print(keys)

输出：

['b', 'z']

Answer 2

如果您正在进行多次查找（并且您计划进行多次查找），实际创建反向默认值可能会很有用：

from collections import defaultdict

inp = defaultdict(list, {'a': [[2, 3], [1, 2]], 'b': [[5, 6]], 'w': [[]], 'x': [[9]], 'z': [[5, 6]]})

res = defaultdict(set)

for key, vallist in inp.items():
    for valsublist in vallist:
        for val in valsublist:
            res[val].add(key)

然后只需访问 res 进行查找。

例如：

>>> res[6]
{'z', 'b'}

>>> res[2]
{'a'}

您将始终需要遍历所有 defaultdicts 值中的所有项目（需要 O(n)，其中 n 是所有值列表中所有项目的数量）。但是在字典中查找关键字（大部分）是 O(1)。因此，如果您计划进行多次查询，比如 k，那么多次迭代需要 O(n*k)，但将其转换为另一个字典只需 O(n + k)。至少如果假设 set.add 操作是 O(1)，情况应该是这样（除了一些 - 非常罕见 - 病理情况）。

如何有效地在 defaultdict 中进行反向查找？

how to efficiently do a reverse look up in defaultdict?

python

performance

python-3.x

defaultdict