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

Question

Angenommen, wir haben N Zahlen (ganze Zahlen, Gleitkommazahlen, was immer Sie wollen) und wollen ihr arithmetisches Mittel finden. Die einfachste Methode ist, alle Werte zu summieren und durch die Anzahl der Werte zu dividieren:

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 ganze Zahlen. Wenn wir keine großen ganzen Zahlen wollen und mit Rundungsfehlern zurechtkommen und N eine Potenz von zwei ist, können wir "Teilen und Beherrschen" 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 und 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

Gibt es noch andere Möglichkeiten?

PS. Spielplatz für Faule

Answer 1

Knuth führt die folgende Methode zur Berechnung von Mittelwert und Standardabweichung bei Fließkommazahlen auf (Original auf S. 232 von Band 2 von Die Kunst der Computerprogrammierung (Ausgabe von 1998; in meiner nachstehenden Bearbeitung wird die erste Fassung nicht besonders hervorgehoben):

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 2

Hier ist eine Möglichkeit, den Mittelwert nur mit ganzen Zahlen zu berechnen, ohne Rundungsfehler und ohne große Zwischenwerte:

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

return sum, rest

Answer 3

Wenn die großen ganzen Zahlen ein Problem sind... ist es in Ordnung

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

Ich meine, Sie suchen nur nach anderen Wegen oder nach dem optimalen Weg?

Answer 4

Handelt es sich bei dem Array um Fließkommadaten, leidet selbst der "einfache" Algorithmus unter Rundungsfehlern. Interessanterweise führt in diesem Fall das Blockieren der Berechnung in sqrt(N)-Summen der Länge sqrt(N) tatsächlich zu einer Verringerung des Fehlers im durchschnittlichen Fall (obwohl die gleiche Anzahl von Fließkommarundungen durchgeführt wird).

Wenn Sie weniger als 4 Milliarden Elemente in Ihrem Array haben (was wahrscheinlich ist), brauchen Sie nur einen Integer-Typ, der 32 Bit größer ist als der Typ der Array-Daten. Die Addition auf diesem etwas größeren Typ wird so gut wie immer schneller sein als die Division oder der Modulus auf dem Typ selbst. Auf den meisten 32-Bit-Systemen ist zum Beispiel die 64-Bit-Addition schneller als die 32-Bit-Division/Modulierung. Dieser Effekt wird nur noch stärker, wenn die Typen größer werden.

Answer 5

Wenn Sie float können Sie große ganze Zahlen vermeiden:

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