计算循环缓冲区的标准偏差

Question

我需要计算值的标准偏差存储在循环缓冲区中.最终算法将在资源受限的设备上运行,因此我希望它尽可能轻量级.天真的方法是每次推入新值时重新评估整个缓冲区的标准偏差,但它会非常慢.理想情况下,我想要一种算法,在推入新值时动态更新标准差的当前值.

维基百科报告了一些快速计算的技术,但它们可以在流上使用:在我的情况下,当推入新值时,应该计算标准偏差,好像最后一个已经弹出的值从未存在过.

tl; dr:如何以最小的计算量计算循环缓冲区的标准偏差？

Answer 1

标准差可表示为:

 stddev = sqrt(1/N * SUM(x[i]^2) - 1/N^2 * SUM(x[i])^2)

对于未校正的样品标准偏差.对于更正的样本标准差,可以写:

 stddev = sqrt(1/(N-1) * SUM(x[i]^2) - 1/(N^2-N) * SUM(x[i])^2)

如果你维护两个累加器,一个用于SUM(x[i]^2),一个用于SUM(x[i]),那么这些对于每个新值都是微不足道的(更新最旧值的效果,并添加最新值的效果). N当然是缓冲区的长度.

当然,如果你是在浮点运算,那么你可能会遇到舍入错误((x + y) - x != y一般情况下).我认为没有任何简单的解决办法.