algorithm - 有什么方法可以找到算术平均值 "better"而不是 sum()/N？

Question

假设我们有 N 个数字(整数、 float ，任何你想要的)并且想要找到它们的算术平均值。最简单的方法是将所有值相加并除以值的数量:

def simple_mean(array[N]): # pseudocode
    sum = 0
    for i = 1 to N
       sum += array[i]
    return sum / N

它工作正常，但需要大整数。如果我们不想要大整数并且我们可以接受舍入误差，并且 N 是 2 的幂，我们可以使用“分而治之”:((a+b)/2 + (c+ d)/2)/2 = (a+b+c+d)/4, ((a+b+c+d)/4 + (e+f+g+h)/4)/2 = (a+b+c+d+e+f+g+h)/8，以此类推。

def bisection_average(array[N]):
   if N == 1: return array[1]
   return (bisection_average(array[:N/2])+bisection_average(array[N/2:]))/2

还有其他方法吗？

附言。 playground for lazy

Answer 1

Knuth 列出了以下计算给定 float 的均值和标准差的方法(原创于 Vol 2 of The Art of Computer Programming 的第 232 页，1998 年版；我在下面的改编避免了第一次迭代的特殊情况):

double M=0, S=0;

for (int i = 0; i < N; ++i)
{
    double Mprev = M;
    M += (x[i] - M)/(i+1);
    S += (x[i] - M)*(x[i] - Mprev);
}

// mean = M
// std dev = sqrt(S/N) or sqrt(S/N+1)
// depending on whether you want population or sample std dev