我的标准差计算可以更加高效吗？

Question

我想知道我的标准差方法能否更加高效。所谓高效是指快速，而快速是指从方法调用到方法返回的延迟较短。

以下是代码：

public double stdDev(ArrayList<Double> input) {

    double Nrecip   = ( 1.0 / ( input.size()) );
    double sum      = 0.0;
    double average  = 0.0;

    for (Double input : inputs) {
        average += input;
    } average *= Nrecip;

    for (Double input : inputs) {
        sum += ( (input - average)*(input - average) );
    } sum *= Nrecip;

    return Math.sqrt(sum);

}

我希望能得到您的帮助和建议。

- d0rmLife

---

你可以使用 average += Nrecip*input;，但这并不能使任何东西更快。 - OneCricketeer

你可以使用 double 而不是 Double ，这样可以节省大量的内存空间。 - Peter Lawrey

计算 (input - average) 时只需计算一次，而不是两次？ - OneCricketeer

只使用一个for循环，并利用“Var（X）= E [（X-E [X]）²] = E [X²] -（E [X]）²”的事实。 - fabian

Answer 1

您可以一遍完成标准差的计算。同时，使用double[]会更有效率。

public static double stdDev(double... a) {
    double sum = 0;
    double sq_sum = 0;
    for (int i = 0; i < n; ++i) {
        double ai = a[i];
        sum += ai;
        sq_sum += ai * ai;
    }
    double mean = sum / n;
    double variance = sq_sum / n - mean * mean;
    return Math.sqrt(variance);
}

这是将此解决方案在C中转换的结果。

只需一次通过内存即可提高性能。

- Peter Lawrey

---

好的回答，谢谢。double... a 是什么意思？我对这种语法不熟悉。另外，我使用 ArrayList<Double> 因为这个方法经常需要滚动更新，所以使用 ArrayList 可以方便地进行更新。两种数据结构之间的速度损失是否显著？我认为 ArrayList 有恒定的读取时间。 - d0rmLife

@d0rmLife ArrayList的时间复杂度是常数级别，创建new Double的成本也是如此，但常数因子较高。使用double..类似于数组，但您可以使用double d = stdDev(1,2,3,4,5);。使用double[]可以使用ArrayList<Double>的约28%的内存，这在开始使用CPU缓存时可能会产生差异。 - Peter Lawrey

@d0rmLife 这是一个类的示例，它包装了一个 double[] 但像 ArrayList 一样运作 http://trove4j.sourceforge.net/javadocs/gnu/trove/list/array/TDoubleArrayList.html - Peter Lawrey

我是否正确理解，您可以计算人口的所有平方和，然后方差=（sq_sum / n）-（mean * mean）？方差可能为负吗？ - simgineer

只有当存在表示错误时，@simgineer 才需要进行处理。平均数的平方应始终小于（或等于）平方的平均数。 - Peter Lawrey

非常酷的算法和如此简单的数学解释在链接下，谢谢！ - Павел

Answer 2

使用 org.apache.commons.math3.stat.descriptive

public double stdDev(ArrayList<Double> input) { 

    DescriptiveStatistics ds = new DescriptiveStatistics(input.toArray(new Double[0]));

    return ds.getStandardDeviation();

}

- CSK