Wie kann der Durchschnitt im laufenden Betrieb effizient berechnet werden (gleitender Durchschnitt)?

Question

ich komme mit diesem

n=1; 
curAvg = 0; 
loop{ 
    curAvg = curAvg + (newNum - curAvg)/n; 
    n++; 
} 

Ich denke, Highlights dieser Art sind:
- Es große Zahlen vermeidet
(und möglichen Überlauf, wenn Sie und teilen sich dann summieren würde) - Sie ein Register speichern (nicht müssen die Summe speichern)

Das Problem könnte mit Summierungsfehler sein - aber ich gehe davon aus, dass es im Allgemeinen ausgeglichene Zahlen von Aufrunden und Abrunden geben sollte, so dass der Fehler nicht dramatisch zusammenfasst.

Siehst du irgendwelche Fallstricke in dieser Lösung? Haben Sie einen besseren Vorschlag?

Answer 1

Ihre Lösung ist im Wesentlichen die "standardmäßige" Online-Lösung für eine durchschnittliche Laufstrecke, ohne große Summen zu speichern und auch "online" zu fahren, dh Sie können nur eine Nummer auf einmal bearbeiten, ohne zu anderen Nummern zurückzukehren , und Sie verwenden nur eine konstante Menge an zusätzlichem Speicher. Wenn Sie eine etwas optimierte Lösung in Bezug auf die numerische Genauigkeit wollen, auf Kosten von "online", dann unter der Annahme, Ihre Zahlen sind alle nicht negativ, dann sortieren Sie Ihre Zahlen zuerst vom kleinsten zum größten und dann verarbeiten sie in dieser Reihenfolge, die So wie Sie es jetzt tun. Auf diese Weise, wenn Sie eine Reihe von Zahlen, die wirklich klein sind etwa gleich und dann erhalten Sie eine große Zahl, können Sie den Durchschnitt genau ohne Unterlauf zu berechnen, im Gegensatz zu, wenn Sie die große Zahl zuerst verarbeitet.

Answer 2

Die obige Formel ist Unsinn. Einfache Mathematik und Präzision diktieren würde:

n ist der Wiederholungszähler, AV läuft Durchschnitt ist newVal neuen Wert

Initialisierung n=0, AV=0

((AV * n) + newVal)/(n+1) = AV 

Es gibt keine Abkürzung, müssen Sie haben alle Zahlen und teilen sie durch die Anzahl der Iterationen, aber Sie können eine der Zahlen neu erstellen, indem Sie wissen, welche Iteration es ist, es ist ein Tossup, eine laufende Summe zu behalten oder sie neu zu berechnen. Die Zeit für die Neuberechnung ist mit hohen Kosten verbunden, die Kosten für die Speicherung einer Zahl sind wahrscheinlich mit geringen Speicherkosten verbunden, und der neu zu berechnende Code wäre sicherlich mehr als der Speicherplatz für die Summe und die Iteration.