在线算法计算标准偏差 [英] Online algorithm for calculating standard deviation

问题描述

通常情况下，我有更多的技术问题，但我将简化它为你计算球的例子。

Normally, I have a more technical problem but I will simplify it for you with an example of counting balls.

假设我有不同颜色的球和一个数组的一个索引（初始化为全0）保留每种颜色。每次我挑了一个球，我增加了相应的指数1。

Assume I have balls of different colors and one index of an array (initialized to all 0's) reserved for each color. Every time I pick a ball, I increment the corresponding index by 1.

球都是随机挑选，我只能挑一球的时间。我唯一​​的目的是计算球的数量为每一种颜色，直到用完了球。

Balls are picked randomly and I can only pick one ball at a time. My sole purpose is to count number of balls for every color, until I run out of balls.

我想计算出不同颜色的球数的标准差，的而我指望他们的。我不希望由具有通过阵列一次迭代我与计算所有的球完成后计算。

I would like to calculate standard deviation of the number of balls of different colors, while I am counting them. I do not want to calculate it by having to iterate through the array once more after I am done with counting all the balls.

要显现：

球以随机顺序： BBGRRYYBBGGGGGGB （每个字母重新presents颜色的第一个字母） 数组索引从0至3对应的颜色B，G，分别R和Y。 当我做采摘的球，我的数组看起来像 [5,7,2,2] 。

Balls in random order: BBGRRYYBBGGGGGGB (each letter represents first letter of a color) Array indices from 0 to 3 correspond to colors B, G, R and Y respectively. When I am done picking the balls, my array looks like [5,7,2,2].

这是很简单的具有最终数组后，计算标准差，但我想这样做，而我填补这一阵列。

It is very simple to calculate standard deviation after having the final array but I want to do it while I am filling this array.

我想这样做在Java中，我有大约1000个颜色。

I want to do it in Java and I have approximately 1000 colors.

什么是实施的最有效的方法是什么？还是甚至有一种方法具有在手的最后阵列之前办呢？

What is the most efficient way to implement that? Or is there even a way to do it before having the final array in hand?

推荐答案

由于平均值和标准偏差使用金额计算，你可以轻松地实施适当的蓄电池为这些。然后，当你想要的实际值，完成计算（特别是师）的其余部分。

Since average and standard deviation are calculated using sums, you can easily implement appropriate accumulators for these. Then when you want the actual values, finish the rest of the calculation (particularly, the divisions).

平方和是棘手的部分，因为你增加了频率为每路输入之一。处理这个的一种方式是维持迄今看到（使用适当的数据结构）的每种颜色的计数。然后，当你看到一个颜色的输入，可以减去其previous广场和添加新广场早在（或者两个平方差添加到您的累加器）。

The sum of squares is the tricky part since you increment one of the frequencies for each input. One way to deal with this is to maintain a count of each color seen so far (using an appropriate data structure). Then when you see a color in the input, you can subtract out its previous square and add the new square back in (or equivalently add the difference of the two squares to your accumulator).

我会离开它的读者来实现此处所描述的算法。

I'll leave it to the reader to implement the algorithm described here.

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