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

Question

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

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

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

Answer 1

Кнут перечисляет следующий метод для вычисления среднего и стандартного отклонения с учетом плавающей запятой (оригинал на стр. 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

Answer 2

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

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

return sum, rest

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

Алгоритм Кахана (согласно википедии) имеет лучшую производительность во время выполнения (чем парное суммирование) - 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

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