计算标准偏差在循环缓冲器 [英] Computing standard deviation over a circular buffer

问题描述

我需要计算值的标准偏差被存储在循环缓冲器。最终的算法将运行一个资源有限的设备上，所以我想这是尽可能轻。天真的做法是，一个新的值被压在每次重新评估的标准偏差在整个缓冲区，但是这将是非常缓慢的。理想情况下，我想一个算法，动态更新的标准偏差的当前值作为新的值被推入。

I need to calculate the standard deviation of values are stored in a circular buffer. The final algorithm will run on a resource-constrained device, thus I want it to be as lightweight as possible. The naive approach would be to re-evaluate the standard deviation over the whole buffer each time that a new value is pushed in, but it would be really slow. Ideally, I'd like an algorithm that dynamically updates the current value of standard deviation as new values are pushed in.

维基百科报道的一些技术进行快速计算，但他们可以在数据流中使用：在我的情况下，当一个新值推入，标准差的计算方法，如果已经弹出的最后一个值不存在。

Wikipedia reports some techniques for rapid calculation, but they can be used on streams: in my case when a new value is pushed in, the standard deviation should be calculated as if the last value that has been popped never existed.

TL;博士：我如何计算标准差以上的循环缓冲区以最小的计算量

tl;dr: how can I calculate standard deviation over a circular buffer with minimal computational effort?

推荐答案

标准差可以pssed作为前$ P $：

Standard deviation can be expressed as:

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

有关未修正的样本标准差。对于修正样本标准差可以写成：

For the uncorrected sample standard deviation. For the corrected sample standard deviation one can write:

 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 当然会是你的缓冲区的长度。

If you maintain two accumulators, one for SUM(x[i]^2), and one for SUM(x[i]), then these are trivial to update for each new value (subtract the effect of the oldest value, and add in the effect of the newest value). N will of course be the length of your buffer.

当然，如果你这样做是在浮点运算，那么你可能会遇到的舍入误差（（X + Y） - X = Y ，在一般）。我不认为有任何容易解决的。

Of course, if you are doing this in floating-point, then you will probably run into roundoff errors ((x + y) - x != y, in general). I don't think there's any easy fix for that.

这篇关于计算标准偏差在循环缓冲器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！