使用软连接逻辑加速字典合并

Question

我有一个查找 table，其中包含 <word: dictionary> 对。然后，给定一个单词列表，我可以使用此查找生成字典列表 table。（每一次，这个词表的长度是不固定的）。这些字典中的值表示某些键的对数概率。

这是一个例子：

给定一个单词列表

['fruit','animal','plant'],

我们可以检查查找 table 并有

dict_list = [{'apple':-1, 'flower':-2}, {'apple':-3, 'dog':-1}, {'apple':-2, 'flower':-1}].

我们从列表中可以看出我们有一组键：{'apple', 'flower', 'dog'}

对于每个键，我想给出 dict_list 中每个值的总和。而如果一个key在一个字典中不存在，那么我们给这个值加上一个小值-10（你可以把-10看成一个很小的对数概率）。

结果字典如下所示： dict_merge = {'apple':-6, 'flower':-13, 'dog':-21}, 因为 'apple' = (-1) + (-3) + (-2)、'flower' = (-2) + (-10) + (-1)、'dog' = (-10) + (-1) + (-10)

这是我的 python3 代码：

dict_list = [{'apple':-1, 'flower':-2}, {'apple':-3, 'dog':-1}, {'apple':-2, 'flower':-1}]

key_list = []
for dic in dict_list:
    key_list.extend(dic.keys())

dict_merge = dict.fromkeys(key_list, 0)
for key in dict_merge:
    for dic in dict_list:
        dict_merge[key] += dic.get(key, -10)

这段代码有效，但是如果dict_list中的某些词典的大小非常大（例如100,000），那么它可能需要200ms以上，这是不可接受的table 在实践中。

主要计算在for key in dict_merge循环中，假设它是一个大小为100,000的循环。

有什么加速的办法吗？谢谢！还有，感谢阅读~可能太长太烦人了...

P.S。查找中只有少数词典table超大。所以这里可能会有一些机会。

Answer 1

据我了解，sum(len(d) for d in dict_list) 比 len(key_list) * len(dict_list) 小得多。

from collections import defaultdict

dict_list = [{'apple':-1, 'flower':-2}, {'apple':-3, 'dog':-1}, {'apple':-2, 'flower':-1}]

default_value = len(dict_list) * (-10)
dict_merge = defaultdict(lambda: default_value)
for d in dict_list:
    for key, value in d.items():
        dict_merge[key] += value + 10

使用软连接逻辑加速字典合并

Speed up dictionary merging with soft conjunction logic

python

dictionary

boolean-logic

nlp

search-engine