如何快速有效地计算平均值(移动平均值)? [英] How to efficiently compute average on the fly (moving average)?

问题描述

我想出了这个

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

我认为这种方式的亮点是:
-避免大数(如果求和然后除法，可能会发生溢出)
-您保存一个寄存器(无需存储总和)

I think highlights of this way are:
- It avoids big numbers (and possible overflow if you would sum and then divide)
- you save one register (not need to store sum)

麻烦可能在于求和错误-但我认为一般情况下，向上舍入和向下舍入的次数应该是平衡的，因此错误不会大幅度地累加.

The trouble might be with summing error - but I assume that generally there shall be balanced numbers of round up and round down so the error shall not sum up dramatically.

您看到此解决方案有什么陷阱吗? 你有更好的建议吗?

Do you see any pitfalls in this solution? Have you any better proposal?

推荐答案

您的解决方案本质上是标准"的最佳在线解决方案，用于在不存储大笔费用的情况下以及在在线"运行时保持平均值运行，即，您可以一次只处理一个数字而不必返回其他数字，则只使用恒定数量的额外内存.如果您想在数值精度方面进行稍微优化的解决方案(以在线"为代价)，则假设您的数字均为非负数，然后从小到大先对数字进行排序，然后按该顺序进行处理，您现在使用的相同方式.这样，如果您得到一堆很小的约相等的数，然后又得到一个大数，则与先处理大数相反，您将能够准确地计算平均值而不会发生下溢.

Your solution is essentially the "standard" optimal online solution for keeping a running track of average without storing big sums and also while running "online", i.e. you can just process one number at a time without going back to other numbers, and you only use a constant amount of extra memory. If you want a slightly optimized solution in terms of numerical accuracy, at the cost of being "online", then assuming your numbers are all non-negative, then sort your numbers first from smallest to largest and then process them in that order, the same way you do now. That way, if you get a bunch of numbers that are really small about equal and then you get one big number, you will be able to compute the average accurately without underflow, as opposed to if you processed the large number first.

这篇关于如何快速有效地计算平均值(移动平均值)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！