C'è un modo per trovare la media aritmetica "migliore" di sum()/N?

Question

Supponiamo di avere N numeri (interi, float, qualunque cosa tu voglia) e voglio trovare la loro media aritmetica. il metodo più semplice è quello di sommare tutti i valori e dividere per il numero di valori:

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

Funziona bene, ma richiede grandi numeri interi. Se non vogliamo i grandi numeri interi e stiamo bene con gli errori di arrotondamento, e N è la potenza di due, possiamo usare '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, così via.

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

In altri modi?

PS. playground for lazy

Answer 1

Se le grandi interi sono problema ... è ok

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

voglio dire che stai cercando solo per altri modi o il modo ottimale?

Answer 2

Se si utilizza float si potrebbe evitare di grandi numeri interi:

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

Answer 3

Knuth elenca il seguente metodo per calcolare media e deviazione standard dato a virgola mobile (originale a pag 232 di Vol 2 of The Art of Computer Programming, edizione 1998; il mio adattamento di seguito. evita speciale involucro prima iterazione):

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

Ecco un modo per calcolare la media utilizzando solo numeri interi senza errori di arrotondamento e di evitare grandi valori intermedi:

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

Se l'array è in virgola mobile, anche l'algoritmo "semplice" presenta un errore di arrotondamento. È interessante notare che in tal caso, il blocco del calcolo in sqrt (N) somme di lunghezza sqrt (N) riduce effettivamente l'errore nel caso medio (anche se viene eseguito lo stesso numero di arrotondamenti a virgola mobile).

Per i dati interi, si noti che non sono necessari i "grandi numeri interi" generici; se hai meno di 4 miliardi di elementi nel tuo array (probabile), hai solo bisogno di un numero intero di 32 bit più grande di quello del tipo di dati dell'array. L'aggiunta di questo tipo leggermente più grande sarà praticamente sempre più veloce rispetto alla divisione o al modulo sul tipo stesso. Ad esempio, sulla maggior parte dei sistemi a 32 bit, l'aggiunta a 64 bit è più veloce della divisione/modulo a 32 bit. Questo effetto diventerà solo più esagerato quando i tipi diventeranno più grandi.

Answer 6

Il Kahan algorithm (secondo wikipedia) presenta migliori prestazioni di esecuzione (rispetto alla sommatoria coppie) - O(n) - e una crescita O(1) errore:

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 

sua idea è che i bit bassi dei numeri in virgola mobile sono sommati e corretti indipendentemente dalla sommatoria principale.