以恒定时间更新连续数字序列的平均值

Question

如何在平均值中添加和减去数字而不必遍历整个列表？

这在许多情况下非常有用.例如,连续计算流中最后X个值的平均值,将两个平均值相加,并根据新用户投票更新评级.

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)
{
    return (size * average - value) / (size - 1);
}

您还可以组合这些功能以轻松替换数字.如果要计算数组/流中最后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);
}

Answer 2

已经提到的典型方式是：

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

n我们的新指标在哪里，a我们的旧平均值在哪里，v我们的新价值在哪里？

然而，n * a部分将最终溢出的n变大，特别是如果a本身是很大的。为了避免这种使用：

a + ( v - a ) / n

随着n增加，我们的确失去了一些精度-自然，我们不断地a按较小的量进行修改。批处理值可以缓解此问题，但对于大多数任务而言可能会过大。