在线算法计算标准差
通常情况下，我有一个更技术性的问题，但我将通过计算球的例子为您简化它。
假设我有不同颜色的球和为每种颜色保留的arrays的一个索引（初始化为全0）。 每次我选一个球，我都会将相应的索引增加1。
球被随机挑选，我一次只能挑一个球。 我唯一的目的是计算每种颜色的球数，直到我用完球。
我想计算不同颜色的球数的标准偏差， 而我正在计算它们 。 在完成对所有球的计数之后，我不想再次遍历数组来计算它。
想象：
随机顺序的球： BBGRRYYBBGGGGGGB （每个字母代表一种颜色的第一个字母）从0到3的数组索引分别对应于颜色B，G，R和Y. 当我完成拾球时，我的arrays看起来像[5,7,2,2] 。
在得到最终数组后计算标准偏差非常简单，但我想在填充此数组时这样做。
我想用Java做，我有大约1000种颜色。
实现这一目标的最有效方法是什么？ 或者在掌握最终arrays之前是否有办法做到这一点？
由于平均值和标准差是使用总和计算的，因此您可以轻松地为这些实现适当的累加器。 然后，当您需要实际值时，完成剩余的计算（特别是除法）。
由于您为每个输入增加一个频率，因此平方和是棘手的部分。 解决此问题的一种方法是保持到目前为止所看到的每种颜色的计数（使用适当的数据结构）。 然后，当您在输入中看到颜色时，可以减去其先前的方块并将新方块添加回来（或等效地将两个方块的差值添加到累加器中）。
我将把它留给读者来实现这里描述的算法。
您不需要数组来计算标准偏差。
只需跟踪点数，总和和总平方和。 您可以随时计算平均值和标准偏差，而无需保留arrays。
如果我了解您的要求，您将需要一个颜色为关键的Map，而Statistics的实例就是值。
这是一个为你做的课程。
package statistics; /** * Statistics * @author Michael * @link http://stackoverflow.com/questions/11978667/online-algorithm-for-calculating-standrd-deviation/11978689#11978689 * @since 8/15/12 7:34 PM */ public class Statistics { private int n; private double sum; private double sumsq; public void reset() { this.n = 0; this.sum = 0.0; this.sumsq = 0.0; } public synchronized void addValue(double x) { ++this.n; this.sum += x; this.sumsq += x*x; } public synchronized double calculateMean() { double mean = 0.0; if (this.n > 0) { mean = this.sum/this.n; } return mean; } public synchronized double calculateVariance() { double deviation = calculateStandardDeviation(); return deviation*deviation; } public synchronized double calculateStandardDeviation() { double deviation = 0.0; if (this.n > 1) { deviation = Math.sqrt((this.sumsq - this.sum*this.sum/this.n)/(this.n-1)); } return deviation; } }
这是它的unit testing：
package statistics; import org.junit.Assert; import org.junit.Test; /** * StatisticsTest * @author Michael * @link http://www.wolframalpha.com/input/?i=variance%281%2C+2%2C+3%2C+4%2C+5%2C+6%29&a=*C.variance-_*Variance- * @since 8/15/12 7:42 PM */ public class StatisticsTest { private static final double TOLERANCE = 1.0E-9; @Test public void testCalculateMean() { double [] values = new double[] { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0 }; Statistics stats = new Statistics(); for (double value : values) { stats.addValue(value); } double expected = 3.5; Assert.assertEquals(expected, stats.calculateMean(), TOLERANCE); } @Test public void testCalculateVariance() { double [] values = new double[] { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0 }; Statistics stats = new Statistics(); for (double value : values) { stats.addValue(value); } double expected = 3.5; Assert.assertEquals(expected, stats.calculateVariance(), TOLERANCE); } @Test public void testCalculateStandardDeviation() { double [] values = new double[] { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0 }; Statistics stats = new Statistics(); for (double value : values) { stats.addValue(value); } double expected = Math.sqrt(3.5); Assert.assertEquals(expected, stats.calculateStandardDeviation(), TOLERANCE); } }