从多个 collections.Counter 对象中累积加权计数的最快方法？

Question

我想合并多个 collections.Counter 对象，其中计数在添加之前用浮点因子加权（参见代码）。每个计数器对象有大约 5000 个键，大部分（但不是全部）键在所有计数器对象之间共享。

我当前的代码非常慢。我用它来合并大约 4000 个计数器对象，方法是使用以下函数按顺序合并它们：

def addCounters(c1, c2, factor = 1.0):
    merged = c1
    for word, count in c2.iteritems():
        if word in merged:
            merged[word] = float(merged[word]) + float(count) * factor
        else:
            merged[word] = float(count) * factor
    return merged

根据我的 cProfile 测量，4181 次调用将运行在 25 秒内慢得令人无法接受。这很烦人，因为它还会冻结我的 GUI。

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
4181    1.056    0.000   25.088    0.006   MyClass.py:30(addCounters)

有谁知道更快的方法吗？

Answer 1

一些可能有帮助的事情：

如果您只是想强制 int 到 float，请不要不断地插入 float 调用；只要您保证 factor 是 float
如果您的 Counter 对象未使用 Counter 特定功能，则转换为 dict 或 defaultdict(int)（或此功能的 defaultdict(float)）可能帮助; dict 和 defaultdict（在 CPython 参考解释器中）是用 C 实现的，其中 Counter 是在 Python 中实现的，这增加了所有使用的开销。在本地测试中（诚然，在 Python 3.5 上，这可能与 2.7 的性能不完全匹配），使用您的原始代码，除了使用 defaultdict(int) 进行输入和输出外，什么都不做，减少了来自 ~ 的一组类似输入的运行时间19 秒到 ~12 秒。
可能没有意义，但是通过使用 x[k] += y * z 而不是 x[k] = x[k] + y * z 来避免两次单独的显式查找可能会（温和地）提高速度（由于 += 的实现方式，实际上会发生两次查找, 但字节码效率稍高)
不要检查 merged 中的每个 word 是否存在，因为 Counter 通过返回 0 来为您处理此密钥是否存在（并且defaultdict(int) 或 defaultdict(float) 会为您创建）

忽略输入类型从 Counter 到其他类型的变化，改进后的代码如下所示：

def addCounters(c1, c2, factor=1.0):
    # Assume inputs are defaultdict(int), not Counter
    merged = c1
    factor = float(factor)  # In case someone passes non-float default
    for word, count in c2.iteritems():
        merged[word] += count * factor
    return merged

在 Python 3.5 的本地测试中（唯一的代码差异是使用 .items() 而不是 .iteritems()），在使用 defaultdict(int) 和进行这些代码更改之间，在与您描述的数据集相似的数据集，总时间从 ~19 秒下降到 ~5.5 秒。在 GUI 事件循环中可能仍然太长而无法接受，但很难对此进行改进。

Answer 2

我在移动设备上，所以无法分析，但下面的实现似乎比原始代码简化了很多反汇编字节码。如果普通字典没问题，可能值得一试。

def addCounters(c1, c2, factor=1.0):
    return dict(c1, **{w:(c1[w] + c*factor) for w,c in c2.iteritems()})

如果您还需要支持纯 dict 参数（而不是仅 Counter 隐含地表现得像 defaultdict 这样 c1[w] 总是安全的），你可以执行 c1.get(w, 0).

def addCounters(c1, c2, factor=1.0):
    return dict(c1, **{w:(c1.get(w, 0) + c*factor) for w,c in c2.iteritems()})

Answer 3

受 F 先生的部分启发，我想出了一些东西，它在我的本地计算机上运行了 4.3 秒。如果有人能让它更快，我仍然会很高兴。我的方法适用于 dict 和 collections.Counter

基本上，我 "export" 将密钥分成几组，然后将它们分成 3 组：

c1
c2
两个键都出现了。
- 第 1 组的计数已经确定，因为我们执行了 c1+factor*c2 而 c2 中没有计数
- 第 2 组的计数只需要乘以该因子，因为 c1 中没有计数
- 现在，第 3 组中的键保证在 c1 和 c2 中都存在，可以再次轻松计算它们的数量
- 最后一切都合并在一起了

def addCounters(c1, c2, factor = 1.0):

#make sure factor is float
factor = float(factor)
#get keys as sets 
c1keys, c2keys = set(c1.keys()), set(c2.keys())
#keys only in c1
c1only = c1keys.difference(c2keys)
#keys only in c2
c2only = c1keys.difference(c1keys)
#keys guaranteed in both
both = c1keys.intersection(c2keys)

#generate dicts for keys which are unique to c1 or c2
c1onlydict = dict((w,c1[w]) for w in c1only)
c2onlydict = dict((w,c2[w]*factor) for w in c2only)
#merge
loners = dict(c1onlydict, **c2onlydict)

#now create the directory with keys which exist in both
bothdict = dict((key, c1[key] + c2[key]*factor) for key in both)

#merge everything
return dict(loners, **bothdict)

我认为它运行得更快的主要原因是当添加多个 counters/dicts 时，总是会将先前的累积作为 c1 反馈给方法。因此 c1onlydict（最容易创建并且可能具有高度优化的字节码）的大小将变得很大，而 c2onlydict 和 bothdict 相比之下会很小。

从多个 collections.Counter 对象中累积加权计数的最快方法？

Fastest way to accumulate weighted counts from multiple collections.Counter Objects?

python

performance

counter

weighted

cumulative-sum