Есть ли способ найти среднее арифметическое "лучше", чем sum()/N?

Предположим, что у нас есть N чисел (целые числа, поплавки, все, что вы хотите) и хотите найти среднее арифметическое. Самый простой способ - суммировать все значения и делить на количество значений:

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

Он отлично работает, но требует больших целых чисел. Если нам не нужны большие целые числа, и мы хорошо разбираемся в ошибках округления, а N - это сила двух, мы можем использовать "divide-and-conquer": ((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

Любые другие способы?

PS. игровая площадка для ленивых

Ответ 1

Knuth перечисляет следующий метод вычисления среднего и стандартного отклонения с учетом плавающей запятой (оригинал на стр. 232 том 2 "Искусство программирования" , Редакция 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

Ответ 2

Здесь можно вычислить среднее значение, используя только целые числа без ошибок округления и избегая больших промежуточных значений:

sum = 0
rest = 0
for num in numbers:
  sum += num / N
  rest += num % N
  sum += rest / N
  rest = rest % N

return sum, rest

Ответ 3

Если большие целые числа являются проблемой... это нормально

a/N + b/N+.... n/N

Я имею в виду, что вы ищете только другие способы или оптимальный способ?

Ответ 4

Если массив представляет собой данные с плавающей запятой, даже "простой" алгоритм страдает от ошибки округления. Интересно, что в этом случае блокирование вычисления в sqrt (N) суммах длины sqrt (N) фактически уменьшает ошибку в среднем случае (даже при том, что выполняется одинаковое число округлений с плавающей запятой).

Для целочисленных данных обратите внимание, что вам не нужны общие "большие целые числа"; если у вас в вашем массиве меньше 4 миллиардов элементов (вероятно), вам нужен только целочисленный тип на 32 бита, превышающий тип данных массива. Выполнение добавления на этом чуть большем типе будет во многом всегда быстрее, чем деление или модуль на самом типе. Например, для большинства 32-битных систем 64-разрядное дополнение выполняется быстрее, чем 32-разрядное деление/модуль. Этот эффект будет только более преувеличенным по мере увеличения типов.

Ответ 5

Если вы используете float, вы можете избежать больших целых чисел:

def simple_mean(array[N]):
    sum = 0.0 # <---
    for i = 1 to N
       sum += array[i]
    return sum / N

Ответ 6

алгоритм Kahan (согласно википедии) имеет лучшую производительность во время выполнения (чем попарное суммирование) - O(n) - и O(1) рост ошибок:

function KahanSum(input)
    var sum = 0.0
    var c = 0.0                  // A running compensation for lost low-order bits.
    for i = 1 to input.length do
        var y = input[i] - c     // So far, so good: c is zero.
        var t = sum + y          // Alas, sum is big, y small, so low-order digits of y are lost.
        c = (t - sum) - y // (t - sum) recovers the high-order part of y; subtracting y recovers -(low part of y)
        sum = t           // Algebraically, c should always be zero. Beware overly-aggressive optimizing compilers!
        // Next time around, the lost low part will be added to y in a fresh attempt.
    return sum

Его идея заключается в том, что младшие разряды чисел с плавающей запятой суммируются и корректируются независимо от основного суммирования.