Return to Answer

replaced http://stackoverflow.com/ with https://stackoverflow.com/

edited May 23, 2017 at 12:40

On Stack Overflow, I wrote an answer an answer which calculates the standard deviation in a single pass with compensation. It is parallel-friendly:

On Stack Overflow, I wrote an answer which calculates the standard deviation in a single pass with compensation. It is parallel-friendly:

deleted 2 characters in body

Source Link

edited Apr 11, 2016 at 19:55

Tunaki

edited Apr 11, 2016 at 19:55

Tunaki

9.3k
1
31
46

static class DoubleStatistics extends DoubleSummaryStatistics {
 private double sumOfSquare = 0.0d;
 private double sumOfSquareCompensation; // Low order bits of sum
 private double simpleSumOfSquare; // Used to compute right sum for
 // non-finite inputs
 @Override
 public void accept(double value) {
 super.accept(value);
 double squareValue = value * value;
 simpleSumOfSquare += squareValue;
 sumOfSquareWithCompensation(squareValue);
 }
 public DoubleStatistics combine(DoubleStatistics other) {
 super.combine(other);
 simpleSumOfSquare += other.simpleSumOfSquare;
 sumOfSquareWithCompensation(other.sumOfSquare);
 sumOfSquareWithCompensation(other.sumOfSquareCompensation);
 return this;
 }
 private void sumOfSquareWithCompensation(double value) {
 double tmp = value - sumOfSquareCompensation;
 double velvel = sumOfSquare + tmp; // Little wolf of rounding error
 sumOfSquareCompensation = (velvel - sumOfSquare) - tmp;
 sumOfSquare = velvel;
 }
 public double getSumOfSquare() {
 double tmp = sumOfSquare + sumOfSquareCompensation;
 if (Double.isNaN(tmp) && Double.isInfinite(simpleSumOfSquare)) {
 return simpleSumOfSquare;
 }
 return tmp;
 }
 public final double getStandardDeviation() {
 long count = getCount();
 double sumOfSquaressumOfSquare = getSumOfSquare();
 double average = getAverage();
 return count > 0 ? Math.sqrt((sumOfSquaressumOfSquare - count * Math.pow(average, 2)) / (count - 1)) : 0.0d;
 }
 public static Collector<Double, ?, DoubleStatistics> collector() {
 return Collector.of(DoubleStatistics::new, DoubleStatistics::accept, DoubleStatistics::combine);
 }
}

static class DoubleStatistics extends DoubleSummaryStatistics {
 private double sumOfSquare = 0.0d;
 private double sumOfSquareCompensation; // Low order bits of sum
 private double simpleSumOfSquare; // Used to compute right sum for
 // non-finite inputs
 @Override
 public void accept(double value) {
 super.accept(value);
 double squareValue = value * value;
 simpleSumOfSquare += squareValue;
 sumOfSquareWithCompensation(squareValue);
 }
 public DoubleStatistics combine(DoubleStatistics other) {
 super.combine(other);
 simpleSumOfSquare += other.simpleSumOfSquare;
 sumOfSquareWithCompensation(other.sumOfSquare);
 sumOfSquareWithCompensation(other.sumOfSquareCompensation);
 return this;
 }
 private void sumOfSquareWithCompensation(double value) {
 double tmp = value - sumOfSquareCompensation;
 double velvel = sumOfSquare + tmp; // Little wolf of rounding error
 sumOfSquareCompensation = (velvel - sumOfSquare) - tmp;
 sumOfSquare = velvel;
 }
 public double getSumOfSquare() {
 double tmp = sumOfSquare + sumOfSquareCompensation;
 if (Double.isNaN(tmp) && Double.isInfinite(simpleSumOfSquare)) {
 return simpleSumOfSquare;
 }
 return tmp;
 }
 public final double getStandardDeviation() {
 long count = getCount();
 double sumOfSquares = getSumOfSquare();
 double average = getAverage();
 return count > 0 ? Math.sqrt((sumOfSquares - count * Math.pow(average, 2)) / (count - 1)) : 0.0d;
 }
 public static Collector<Double, ?, DoubleStatistics> collector() {
 return Collector.of(DoubleStatistics::new, DoubleStatistics::accept, DoubleStatistics::combine);
 }
}

static class DoubleStatistics extends DoubleSummaryStatistics {
 private double sumOfSquare = 0.0d;
 private double sumOfSquareCompensation; // Low order bits of sum
 private double simpleSumOfSquare; // Used to compute right sum for
 // non-finite inputs
 @Override
 public void accept(double value) {
 super.accept(value);
 double squareValue = value * value;
 simpleSumOfSquare += squareValue;
 sumOfSquareWithCompensation(squareValue);
 }
 public DoubleStatistics combine(DoubleStatistics other) {
 super.combine(other);
 simpleSumOfSquare += other.simpleSumOfSquare;
 sumOfSquareWithCompensation(other.sumOfSquare);
 sumOfSquareWithCompensation(other.sumOfSquareCompensation);
 return this;
 }
 private void sumOfSquareWithCompensation(double value) {
 double tmp = value - sumOfSquareCompensation;
 double velvel = sumOfSquare + tmp; // Little wolf of rounding error
 sumOfSquareCompensation = (velvel - sumOfSquare) - tmp;
 sumOfSquare = velvel;
 }
 public double getSumOfSquare() {
 double tmp = sumOfSquare + sumOfSquareCompensation;
 if (Double.isNaN(tmp) && Double.isInfinite(simpleSumOfSquare)) {
 return simpleSumOfSquare;
 }
 return tmp;
 }
 public final double getStandardDeviation() {
 long count = getCount();
 double sumOfSquare = getSumOfSquare();
 double average = getAverage();
 return count > 0 ? Math.sqrt((sumOfSquare - count * Math.pow(average, 2)) / (count - 1)) : 0.0d;
 }
 public static Collector<Double, ?, DoubleStatistics> collector() {
 return Collector.of(DoubleStatistics::new, DoubleStatistics::accept, DoubleStatistics::combine);
 }
}

Source Link

answered Apr 11, 2016 at 19:50

Tunaki

answered Apr 11, 2016 at 19:50

Tunaki

9.3k
1
31
46

You are traversing the collection twice to determine the standard deviation when you could do it in a single pass.
Also, you could accumulate quickly rounding errors with the Math.pow(x.doubleValue() - average, 2.0) call. It would be best to implement the Kahan summation algorithm (that the Stream API has for DoubleStream#sum()).
In the lambda expression (x) -> x.doubleValue(), you don't need to add the parentheses around (x). You can just have x -> x.doubleValue(). You could also use a method-reference, which avoids a lamda, and have Number::doubleValue.

On Stack Overflow, I wrote an answer which calculates the standard deviation in a single pass with compensation. It is parallel-friendly:

static class DoubleStatistics extends DoubleSummaryStatistics {
 private double sumOfSquare = 0.0d;
 private double sumOfSquareCompensation; // Low order bits of sum
 private double simpleSumOfSquare; // Used to compute right sum for
 // non-finite inputs
 @Override
 public void accept(double value) {
 super.accept(value);
 double squareValue = value * value;
 simpleSumOfSquare += squareValue;
 sumOfSquareWithCompensation(squareValue);
 }
 public DoubleStatistics combine(DoubleStatistics other) {
 super.combine(other);
 simpleSumOfSquare += other.simpleSumOfSquare;
 sumOfSquareWithCompensation(other.sumOfSquare);
 sumOfSquareWithCompensation(other.sumOfSquareCompensation);
 return this;
 }
 private void sumOfSquareWithCompensation(double value) {
 double tmp = value - sumOfSquareCompensation;
 double velvel = sumOfSquare + tmp; // Little wolf of rounding error
 sumOfSquareCompensation = (velvel - sumOfSquare) - tmp;
 sumOfSquare = velvel;
 }
 public double getSumOfSquare() {
 double tmp = sumOfSquare + sumOfSquareCompensation;
 if (Double.isNaN(tmp) && Double.isInfinite(simpleSumOfSquare)) {
 return simpleSumOfSquare;
 }
 return tmp;
 }
 public final double getStandardDeviation() {
 long count = getCount();
 double sumOfSquares = getSumOfSquare();
 double average = getAverage();
 return count > 0 ? Math.sqrt((sumOfSquares - count * Math.pow(average, 2)) / (count - 1)) : 0.0d;
 }
 public static Collector<Double, ?, DoubleStatistics> collector() {
 return Collector.of(DoubleStatistics::new, DoubleStatistics::accept, DoubleStatistics::combine);
 }
}

It has the same logic as DoubleSummaryStatistics but extended to calculate the sum of squares.

With such a class, you can then have:

public static double computeStandardDeviation(Number... collection) {
 return Arrays.stream(collection)
 .map(Number::doubleValue)
 .collect(DoubleStatistics.collector())
 .getStandardDeviation();
}

lang-java