Python - 每次修改时找到整个字典平均值的最快方法？

Question

我正在尝试找到最快/最有效的方法来从字典中提取平均值。我正在处理的任务要求它执行数千次，因此每次简单地迭代字典中的所有值来查找平均值将是完全低效的。成百上千的新键、值对被添加到字典中，每次发生这种情况时我们都需要找到平均值。我们还需要在每次值更新时找到新的平均值，这会发生数千次。

预先感谢——这是一个很棒的地方。

Answer 1

创建自己的 dict 子类来跟踪计数和总计，然后可以快速返回平均值：

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

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

继承自dict，每次调用__setitem__时计算平均值。

由于您可以将先前的平均值存储在字典类中，并且仅对这个值和添加的新值进行平均，所以这应该非常快 - 第一次添加新项目时，平均值就是这个值的平均值。