Gibt es eine Möglichkeit, arithmetisches Mittel "besser" als Summe()/N zu finden?

Question

Angenommen, wir haben N Zahlen (Ganzzahlen, Gleitkommazahlen, was immer Sie wollen) und möchten ihr arithmetisches Mittel finden. Einfachste Methode ist es, alle Werte und Dividieren durch die Anzahl der Werte zu summieren:

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

Es funktioniert gut, erfordert aber große Zahlen. Wenn wir keine großen ganzen Zahlen wollen und uns Rundungsfehler gut machen, und N die Potenz von zwei ist, können wir 'teile und herrsche' verwenden: ((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, so weiter.

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

Andere Möglichkeiten?

PS. playground for lazy

Answer 1

Wenn die großen ganzen Zahlen Problem sind ... ist es ok

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

Ich meine Sie suchen nur nach anderen Wegen oder die optimale Art und Weise?

Answer 2

Wenn Sie float Sie große Zahlen vermeiden könnten:

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

Answer 3

Knuth listet die folgende Methode für Mittelwert und Standardabweichung angegeben Floating-Point (Original auf S. Berechnung 232 von Vol 2 of The Art of Computer Programming, Ausgabe 1998, meine Anpassung unten. vermeidet Sonder-Gehäuse die erste Iteration):

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

Hier ist ein Weg, um den Mittelwert mit nur ganzen Zahlen ohne Rundungsfehler und die Vermeidung von großen Zwischenwerten zu berechnen:

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

Wenn das Array Gleitkommadaten ist, leidet selbst der "einfache" Algorithmus unter Rundungsfehler. Interessanterweise reduziert in diesem Fall die Blockierung der Berechnung in sqrt (N) -Summen der Länge sqrt (N) tatsächlich den Fehler im Durchschnittsfall (obwohl dieselbe Anzahl von Gleitkomma-Rundungen ausgeführt wird).

Für ganzzahlige Daten beachten Sie, dass Sie keine allgemeinen "großen Ganzzahlen" benötigen; Wenn Sie weniger als 4 Milliarden Elemente in Ihrem Array haben (wahrscheinlich), benötigen Sie nur einen Integer-Typ, der 32 Bit größer ist als der Typ der Array-Daten. Das Hinzufügen auf diesem geringfügig größeren Typ wird immer schneller sein als das Teilen oder Modulieren des Typs selbst. Zum Beispiel ist bei den meisten 32-Bit-Systemen die 64-Bit-Addition schneller als 32-Bit-Division/Modul. Dieser Effekt wird nur übertrieben, wenn die Typen größer werden.

Answer 6

Die Kahan algorithm (nach der hinzufügen) hat eine bessere Leistung-Laufzeit (als die paarweise Summation) - O(n) - und ein O(1) Fehler Wachstum:

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 

Die Idee ist, dass die niedrigen Bits der Gleitkommazahlen werden summiert und unabhängig von der Hauptsummierung korrigiert.