¿Hay alguna forma de encontrar la media aritmética "mejor" que sum()/N?

Question

Supongamos que tenemos N números (enteros, flotantes, lo que quieras) y queremos encontrar su media aritmética. método más sencillo consiste en sumar todos los valores y se divide por el número de valores:

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

Funciona bien, pero requiere grandes números enteros. Si no queremos enteros grandes y estamos bien con errores de redondeo, y N es el poder de dos, podemos usar 'divide y vencerás': ((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, etc.

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

¿Alguna otra manera?

PS. playground for lazy

Answer 1

Si los grandes números enteros son un problema ... ¿está bien

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

quiero decir que usted está buscando sólo para otras formas o la forma óptima?

Answer 2

Si utiliza float es posible evitar grandes números enteros:

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

Answer 3

Knuth enumera el siguiente método para el cálculo de la media y desviación estándar dada de punto flotante (original en la página 232 de Vol 2 of The Art of Computer Programming, edición de 1998; mi adaptación a continuación. evita-especial de la carcasa de la primera iteración):

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

Aquí está una manera de calcular la media usando sólo números enteros y sin errores de redondeo y evitar grandes valores intermedios:

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

Si la matriz es de coma flotante, incluso el algoritmo "simple" sufre un error de redondeo. Curiosamente, en ese caso, bloquear el cálculo en sqrt (N) sumas de longitud sqrt (N) en realidad reduce el error en el caso promedio (aunque se realice el mismo número de redondeos en coma flotante).

Para datos enteros, tenga en cuenta que no necesita "enteros grandes" generales; si tiene menos de 4 mil millones de elementos en su matriz (probable), solo necesita un entero de 32 bits más grande que el tipo de datos de la matriz. Realizar la adición en este tipo un poco más grande casi siempre será más rápido que hacer división o módulo en el tipo mismo. Por ejemplo, en la mayoría de los sistemas de 32 bits, la adición de 64 bits es más rápida que la división/módulo de 32 bits. Este efecto solo se volverá más exagerado a medida que los tipos se vuelvan más grandes.

Answer 6

El Kahan algorithm (según la Wikipedia) tiene un mejor rendimiento en tiempo de ejecución (de la suma de pares) - O(n) - y un crecimiento O(1) error:

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 

Su idea es que las bajas bits de los números de punto flotante se suman y corrigen independientemente de la suma principal.