Comment calculer efficacement la moyenne à la volée (moyenne mobile)?
Je viens avec ceci
n=1;
curAvg = 0;
loop{
curAvg = curAvg + (newNum - curAvg)/n;
n++;
}
Je pense que les faits saillants de cette façon sont:
- Il évite les grands nombres (et le débordement possible si vous additionnez puis divisez)
- vous enregistrez un registre (pas besoin de stocker somme)
Le problème pourrait être avec l'erreur de sommation - mais je suppose que Généralement il y aura des nombres équilibrés de round up et round down de sorte que l'erreur ne doit pas résumer de façon spectaculaire.
Voyez-vous des pièges dans cette solution? Avez-vous une meilleure proposition?
2 réponses
Votre solution est essentiellement la solution en ligne optimale "standard "pour garder une trace de moyenne sans stocker de grosses sommes et aussi en cours d'exécution" en ligne", c'est-à-dire que vous pouvez simplement traiter un nombre à la fois sans revenir à d'autres nombres, et vous n'utilisez qu'une quantité constante de mémoire supplémentaire. Si vous voulez une solution légèrement optimisée en termes de précision numérique, au prix d'être "en ligne", alors en supposant que vos nombres sont tous non négatifs, puis triez vos nombres d'abord à partir de le plus petit au plus grand, puis traitez - les dans cet ordre, de la même manière que vous le faites maintenant. De cette façon, si vous obtenez un tas de nombres qui sont vraiment petits à peu près égaux et que vous obtenez un grand nombre, vous serez en mesure de calculer la moyenne avec précision sans sous-flux, par opposition à si vous avez traité le grand nombre en premier.
La formule ci-dessus est absurde. Les mathématiques simples et la précision dicteraient:
n c'est le itération compteur, AV est en cours d'exécution moyenne, newVal est la nouvelle valeur de
Initialisation n=0, AV=0
( (AV * n) + newVal ) / (n+1) = AV
Il n'y a pas de raccourci, vous devez avoir tous les nombres et les diviser par le nombre d'itérations, mais vous pouvez reconstruire l'un des nombres en sachant de quelle itération il s'agit, c'est un tossup de garder un total en cours d'exécution ou de le recalculer. Le temps de recalcul est à un coût élevé le coût de stockage d'un nombre probablement un faible coût en termes de mémoire et le code à recalculer serait certainement plus que l'emplacement de la mémoire pour contenir le total et l'itération.