algorithm - 如何有效地动态计算平均值(移动平均值)？

Question

我想到了这个

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

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

问题可能出在求和误差上——但我假设通常向上舍入和向下舍入的数量应该是平衡的，所以误差不会显着加起来。

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

Answer 1

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