Python - 在字典每次修改时，找出平均值的最快方法是什么？

Question

我正在寻找一种最快、最有效的方法来从字典中提取平均值。我现在的任务需要这样做成千上万次，所以每次都遍历字典里的所有值来计算平均值显然是非常低效的。字典中会不断添加成百上千的新键值对，每次添加时我们都需要找到新的平均值。此外，每当某个值被更新时，我们也需要重新计算平均值，这种更新会发生成千上万次。

提前感谢大家——这里真是一个很棒的地方。

Answer 1

从 dict 这个字典类继承，并在每次调用 __setitem__ 方法时计算平均值。

因为你可以在你的字典类里存储之前的平均值，只需要把这个平均值和新加的值一起算平均，所以这样做应该会很快。第一次添加新项的时候，平均值就直接是这个新值本身。

Answer 2

下面的内容是关于运行平均值的，也就是说，如果你知道之前的平均值：

At = (A0 * N + E) / (N + 1)

At is the average after addition of the new element
A0 is the average before addition of the new element
N is the number of element before addition of the new element
E is the new element's value

它的简单版本是，如果你记录下所有元素的总和，就可以使用：

At = (T + E) / (N + 1)

T is the total of all elements
A0 is the average before addition of the new element
N is the number of element before addition of the new element
E is the new element's value

当你删除一个值时，你可以做类似的操作：

At = (A0 * N - E) / (N - 1)

而当你更新一个值时：

At = (A0 * N - E0 + E1) / (N)

E0 is value before updating, E1 is value after updating.

Answer 3

创建一个自己的字典子类，这个子类可以记录数量和总和，然后能够快速返回平均值：

class AvgDict(dict):
    def __init__(self):
        self._total = 0.0
        self._count = 0

    def __setitem__(self, k, v):
        if k in self:
            self._total -= self[k]
            self._count -= 1
        dict.__setitem__(self, k, v)
        self._total += v
        self._count += 1

    def __delitem__(self, k):
        v = self[k]
        dict.__delitem__(self, k)
        self._total -= v
        self._count -= 1

    def average(self):
        if self._count:
            return self._total/self._count

a = AvgDict()
assert a.average() is None
a[1] = 1
assert a.average() == 1
a[2] = 10
assert a.average() == 5.5
assert a[2] == 10
a[1] = 5
assert a.average() == 7.5
del a[1]
assert a.average() == 10