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

language-agnostic math

Question

Supongamos que tenemos N números (enteros, flotantes, lo que quieras) y queremos encontrar su media aritmética. El método más simple es sumar todos los valores y dividir por 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 números enteros grandes. Si no queremos números 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?

PD. patio de recreo para perezoso

Answer 1

Aquí hay una forma de calcular la media usando enteros enteros sin errores de redondeo y evitando 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 2

El algoritmo de Kahan (de acuerdo con la wikipedia) tiene un mejor rendimiento en el tiempo de ejecución (que la suma por pares) - O(n) - y un crecimiento de error 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

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

Answer 3

Knuth enumera el siguiente método para calcular la desviación media y estándar dado el punto flotante (original en la página 232 del Vol. 2 de The Art of Computer Programming , edición de 1998; mi adaptación a continuación evita el revestimiento especial 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

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 5

Si los enteros grandes son un problema ... ¿está bien?

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

Quiero decir que estás buscando otras formas o la forma óptima?

Answer 6

Si usas float puedes evitar números enteros grandes:

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