在常数时间内更新连续数字序列的平均值

Question

如何在不必遍历整个列表的情况下对平均数中的数字进行加减？

这在许多情况下非常有用。例如，连续计算流中最后X个值的平均值、将两个平均值相加以及基于新用户投票更新评级。

- Sam Olesen

---

这被称为“增量平均”，并在Math.SE上得到了回答。 - Dan Dascalescu

Answer 1

可以在常数时间O(1)内操纵平均值中的单个值。

下面的函数将数字添加到平均值中。average是当前平均值，size是平均值中当前值的数量，value是要添加到平均值中的数字：

double addToAverage(double average, int size, double value)
{
    return (size * average + value) / (size + 1);
}

同样地，下面的函数从平均数中删去一个数字：

double subtractFromAverage(double average, int size, double value)
{
    // if (size == 1) return 0;       // wrong but then adding a value "works"
    // if (size == 1) return NAN;     // mathematically proper
    // assert(size > 1);              // debug-mode check
    // if(size < 2) throw(...)        // always check
    return (size * average - value) / (size - 1);
}

当考虑对一个大小为0的集合求平均值时，你可以返回0，这样将一个值添加回去时，它作为平均值。但是如果认为将集合减少到大小0是一个错误，那么返回NAN将传播到未来的使用中，使其更加明显。但请查看什么是空序列的算术平均数？ - 你可能希望在现场嘈杂地报告错误，或者如果这种情况是错误的，就抛出C++异常（不仅仅是引发FP异常）。

如果没有特殊处理它，你可能会得到+或-Inf，因为x / 0.非零x，除非移除的值恰好等于当前平均值；那么你将得到0. / 0. => NaN。

---

你还可以结合这些函数轻松替换数字。如果正在计算数组/流中最后X个数字的平均值，则这非常方便。

double replaceInAverage(double average, int size, double oldValue, double newValue)
{
    return (size * average - oldvalue + newValue) / size;
}

还可以通过常数时间计算两个平均数的总平均值：

double addAveragesTogether(double averageA, int sizeA, double averageB, int sizeB)
{
    return (sizeA * averageA + sizeB * averageB) / (sizeA + sizeB);
}

- Sam Olesen

---

虽然 addToAverage 是正确的，但请注意使用这个替代公式时精度误差可能会更小。 - Dan Dascalescu

subtractFromAverage would throw an error if size is 1. I would add if (oldSize == 1) return 0; - Yousif

@Yousif：我不确定默默地返回0对于所有用例来说是否更好。如果有什么问题，NaN可能更合适。 （当前代码实际上将返回+-Inf，这也不好，除非average == value以获得0. / 0.=> NaN）。我想返回0的优点是将其添加到平均值中将设置平均值为该值。 - Peter Cordes

还要注意函数式编程中的除法操作比较昂贵；虽然通常值得这么做，但不像加法和乘法那样便宜。 （如果size是一个编译时常量，您可以执行 double inverse = 1. / size; 但这可能不是精确的，并且随着重复使用会积累误差。） - Peter Cordes

Answer 2

已经提到的典型方法是：

( n * a + v ) / (n + 1);

其中n是我们的旧计数，a是我们的旧平均值，而v则是我们的新值。

但是，n * a 部分随着n的增大，特别是当a本身较大时，最终会溢出。为了避免这种情况，请使用：

a + ( v - a ) / (n + 1)

随着n的增加，我们会失去一些精度 - 自然而然地，我们正在通过连续较小的量来修改a。批处理值可以缓解这个问题，但对于大多数任务来说可能过于复杂。

- c z

---

如果有人对第二个方程式为什么也能起作用感兴趣，可以在这里找到一个不错的解释：https://math.stackexchange.com/a/1836447/709688 - JannisW

但是是否有替代的方法来进行删除和替换呢？ - Barnack

请注意，浮点数在所有比例下保持相同的相对精度，因此将类似大小的数字相乘然后除以它们不会失去太多精度；只有当它实际上超过DBL_MAX（约为1.79769e+308）时才会出现问题，这是极其巨大的。另一个主要的数值问题是将小数加到大数中，使用n*a + v或a + v/n。如果v/n小于a的1ULP，则添加它甚至不会翻转a的尾数的低位。即如果|v| < |a|/2^53左右。即使v不是那么小，你仍然可能失去大部分精度。 - Peter Cordes

@PeterCordes 是的，这个比较将方程2与从头开始重新计算平均值进行了比较。然而，方程1仍然存在同样的问题 - 当n*a接近MAX时，n*a + v = n*a。使用适当的数据类型重新计算平均值总是更好的选择，但并不总是可能的（或必要的），就像在OP的情况下一样。 - c z

@Barnack 要从平均数中移除一个项目，请从当前平均数中移除该项目的影响，即 a-(v-a)/(n-1)（其中 n 和 a 分别表示移除 v 之前的项目数量和平均值）。 - c z