| /* |
| * Copyright (C) 2013 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.math; |
| |
| import com.google.caliper.BeforeExperiment; |
| import com.google.caliper.Benchmark; |
| import com.google.caliper.Param; |
| import com.google.caliper.api.SkipThisScenarioException; |
| import com.google.common.primitives.Doubles; |
| import java.util.Random; |
| |
| /** |
| * Benchmarks for various algorithms for computing the mean and/or variance. |
| * |
| * @author Louis Wasserman |
| */ |
| public class StatsBenchmark { |
| |
| enum MeanAlgorithm { |
| SIMPLE { |
| @Override |
| double mean(double[] values) { |
| double sum = 0.0; |
| for (double value : values) { |
| sum += value; |
| } |
| return sum / values.length; |
| } |
| }, |
| KAHAN { |
| @Override |
| double mean(double[] values) { |
| double sum = 0.0; |
| double c = 0.0; |
| for (double value : values) { |
| double y = value - c; |
| double t = sum + y; |
| c = (t - sum) - y; |
| sum = t; |
| } |
| return sum / values.length; |
| } |
| }, |
| KNUTH { |
| @Override |
| double mean(double[] values) { |
| double mean = values[0]; |
| for (int i = 1; i < values.length; i++) { |
| mean = mean + (values[i] - mean) / (i + 1); |
| } |
| return mean; |
| } |
| }; |
| |
| abstract double mean(double[] values); |
| } |
| |
| static class MeanAndVariance { |
| private final double mean; |
| private final double variance; |
| |
| MeanAndVariance(double mean, double variance) { |
| this.mean = mean; |
| this.variance = variance; |
| } |
| |
| @Override |
| public int hashCode() { |
| return Doubles.hashCode(mean) * 31 + Doubles.hashCode(variance); |
| } |
| } |
| |
| enum VarianceAlgorithm { |
| DO_NOT_COMPUTE { |
| @Override |
| MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { |
| return new MeanAndVariance(meanAlgorithm.mean(values), 0.0); |
| } |
| }, |
| SIMPLE { |
| @Override |
| MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { |
| double mean = meanAlgorithm.mean(values); |
| double sumOfSquaresOfDeltas = 0.0; |
| for (double value : values) { |
| double delta = value - mean; |
| sumOfSquaresOfDeltas += delta * delta; |
| } |
| return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length); |
| } |
| }, |
| KAHAN { |
| @Override |
| MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { |
| double mean = meanAlgorithm.mean(values); |
| double sumOfSquaresOfDeltas = 0.0; |
| double c = 0.0; |
| for (double value : values) { |
| double delta = value - mean; |
| double deltaSquared = delta * delta; |
| double y = deltaSquared - c; |
| double t = sumOfSquaresOfDeltas + deltaSquared; |
| c = (t - sumOfSquaresOfDeltas) - y; |
| sumOfSquaresOfDeltas = t; |
| } |
| return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length); |
| } |
| }, |
| KNUTH { |
| @Override |
| MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { |
| if (meanAlgorithm != MeanAlgorithm.KNUTH) { |
| throw new SkipThisScenarioException(); |
| } |
| double mean = values[0]; |
| double s = 0.0; |
| for (int i = 1; i < values.length; i++) { |
| double nextMean = mean + (values[i] - mean) / (i + 1); |
| s += (values[i] - mean) * (values[i] - nextMean); |
| mean = nextMean; |
| } |
| return new MeanAndVariance(mean, s / values.length); |
| } |
| }; |
| |
| abstract MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm); |
| } |
| |
| @Param({"100", "10000"}) |
| int n; |
| |
| @Param MeanAlgorithm meanAlgorithm; |
| @Param VarianceAlgorithm varianceAlgorithm; |
| |
| private double[][] values = new double[0x100][]; |
| |
| @BeforeExperiment |
| void setUp() { |
| Random rng = new Random(); |
| for (int i = 0; i < 0x100; i++) { |
| values[i] = new double[n]; |
| for (int j = 0; j < n; j++) { |
| values[i][j] = rng.nextDouble(); |
| } |
| } |
| } |
| |
| @Benchmark |
| int meanAndVariance(int reps) { |
| int tmp = 0; |
| for (int i = 0; i < reps; i++) { |
| tmp += varianceAlgorithm.variance(values[i & 0xFF], meanAlgorithm).hashCode(); |
| } |
| return tmp; |
| } |
| } |