Czy istnieje sposób na znalezienie średniej arytmetycznej "lepszej" niż suma()/N?

Question

Załóżmy, że mamy N liczb (liczb całkowitych, pływaków, cokolwiek chcesz) i chcesz znaleźć ich średnią arytmetyczną. Najprostszą metodą jest zsumowanie wszystkich wartości i podzielenie przez liczbę wartości:

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

Działa dobrze, ale wymaga dużych liczb całkowitych. Jeśli nie chcemy dużych liczb całkowitych i mamy problemy z błędami zaokrąglania, a N jest potęgą dwóch, możemy użyć "dziel i rządź": ((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, i tak dalej.

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

Jakieś inne sposoby?

PS. playground for lazy

Answer 1

Jeśli duże liczby całkowite są problemem ... to jest ok

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

Znaczy szukasz tylko inny sposób lub sposób optymalny?

Answer 2

Jeśli używasz float można uniknąć dużych liczb całkowitych:

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

Answer 3

Knuth wymienia następujące metody obliczania średniej i odchylenia standardowego podane zmiennoprzecinkowa (oryginał na str 232 Vol 2 of The Art of Computer Programming, wydanie 1998; mój adaptacji poniżej. unika specjalnej obudowy pierwszej iteracji):

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 4

oto sposób obliczyć średnią używając tylko liczby całkowite bez zaokrąglania błędów i unikanie dużych wartości pośrednie:

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

return sum, rest 

Answer 5

Jeśli tablica jest danymi zmiennoprzecinkowymi, nawet "prosty" algorytm ma problem z zaokrągleniem. Co ciekawe, w tym przypadku blokowanie obliczeń na sqrt (N) sumy długości sqrt (N) faktycznie zmniejsza błąd w przeciętnym przypadku (mimo że wykonuje się tę samą liczbę zaokrągleń zmiennoprzecinkowych).

Dla danych całkowitych, nie potrzebujesz ogólnych "dużych liczb całkowitych"; jeśli masz mniej niż 4 miliardy elementów w twojej tablicy (prawdopodobnie), potrzebujesz tylko liczby całkowitej 32-bitowej większej niż typ danych tablicy. Wykonywanie dodawania na tym nieco większym typie będzie prawie zawsze szybsze niż dzielenie lub moduł na samym typie. Na przykład w większości systemów 32-bitowych dodanie 64-bitowe jest szybsze niż podział 32-bitowy/moduł. Efekt ten będzie bardziej wyolbrzymiany, ponieważ typy stają się większe.

Answer 6

Kahan algorithm (wg Wikipedii) ma lepszą wydajność środowiska wykonawczego (niż parami sumowanie) - O(n) - oraz wzrost O(1) błędzie:

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 

Jego ideą jest, że niskie bity liczb zmiennoprzecinkowych są sumowane i korygowane niezależnie od głównego sumowania.