如何有效地动态计算平均值（移动平均值）？

Question

我想到了这个

n=1;
curAvg = 0;
loop{
  curAvg = curAvg + (newNum - curAvg)/n;
  n++;
}

我认为这种方式的亮点是：
- 它避免了大数字（如果先求和再除可能会溢出）
- 你保存一个寄存器（不需要存储总和）

问题可能出在求和误差上 - 但我认为通常向上舍入和向下舍入的数字应该是平衡的，因此误差不会显着加起来。

您认为此解决方案有任何缺陷吗？你有更好的建议吗？

Answer 1

您的解决方案本质上是 "standard" 最佳在线解决方案，用于保持运行平均跟踪而不存储大笔金额，同时运行 "online"，即您可以一次只处理一个数字而不返回其他数字，并且您只使用恒定数量的额外内存。如果你想要一个在数值精度方面稍微优化的解决方案，代价是"online"，那么假设你的数字都是非负数，然后先从小到大对你的数字进行排序，然后按该顺序处理它们，就像你现在做的那样。这样，如果你得到一堆非常小的数字，然后你得到一个大数字，你将能够准确地计算平均值而不会下溢，而不是如果你先处理大数字。

Answer 2

这个算法我用了很多年。循环是任何一种循环。可能是单独的网络会话，也可能是真正的循环。关键是您需要跟踪的只是当前计数 (N) 和当前平均值 (avg)。每次收到新值时，应用此算法更新平均值。这将计算精确的算术平均值。它还有一个额外的好处，那就是它可以防止溢出。如果你有大量的大数需要平均，那么在你除以 N 之前将它们全部相加可能会溢出。这个算法避免了这个陷阱。

Variables that are stored during the computation of the average:
N = 0
avg = 0

For each new value: V
    N=N+1
    a = 1/N
    b = 1 - a
    avg = a * V + b * avg

如何有效地动态计算平均值（移动平均值）？

How to efficiently compute average on the fly (moving average)?

algorithm

math

average

moving-average