1 /* 2 * Copyright (C) 2013 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.math; 18 19 import com.google.caliper.BeforeExperiment; 20 import com.google.caliper.Benchmark; 21 import com.google.caliper.Param; 22 import com.google.caliper.api.SkipThisScenarioException; 23 import com.google.common.primitives.Doubles; 24 import java.util.Random; 25 26 /** 27 * Benchmarks for various algorithms for computing the mean and/or variance. 28 * 29 * @author Louis Wasserman 30 */ 31 public class StatsBenchmark { 32 33 enum MeanAlgorithm { 34 SIMPLE { 35 @Override mean(double[] values)36 double mean(double[] values) { 37 double sum = 0.0; 38 for (double value : values) { 39 sum += value; 40 } 41 return sum / values.length; 42 } 43 }, 44 KAHAN { 45 @Override mean(double[] values)46 double mean(double[] values) { 47 double sum = 0.0; 48 double c = 0.0; 49 for (double value : values) { 50 double y = value - c; 51 double t = sum + y; 52 c = (t - sum) - y; 53 sum = t; 54 } 55 return sum / values.length; 56 } 57 }, 58 KNUTH { 59 @Override mean(double[] values)60 double mean(double[] values) { 61 double mean = values[0]; 62 for (int i = 1; i < values.length; i++) { 63 mean = mean + (values[i] - mean) / (i + 1); 64 } 65 return mean; 66 } 67 }; 68 mean(double[] values)69 abstract double mean(double[] values); 70 } 71 72 static class MeanAndVariance { 73 private final double mean; 74 private final double variance; 75 MeanAndVariance(double mean, double variance)76 MeanAndVariance(double mean, double variance) { 77 this.mean = mean; 78 this.variance = variance; 79 } 80 81 @Override hashCode()82 public int hashCode() { 83 return Doubles.hashCode(mean) * 31 + Doubles.hashCode(variance); 84 } 85 } 86 87 enum VarianceAlgorithm { 88 DO_NOT_COMPUTE { 89 @Override variance(double[] values, MeanAlgorithm meanAlgorithm)90 MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { 91 return new MeanAndVariance(meanAlgorithm.mean(values), 0.0); 92 } 93 }, 94 SIMPLE { 95 @Override variance(double[] values, MeanAlgorithm meanAlgorithm)96 MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { 97 double mean = meanAlgorithm.mean(values); 98 double sumOfSquaresOfDeltas = 0.0; 99 for (double value : values) { 100 double delta = value - mean; 101 sumOfSquaresOfDeltas += delta * delta; 102 } 103 return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length); 104 } 105 }, 106 KAHAN { 107 @Override variance(double[] values, MeanAlgorithm meanAlgorithm)108 MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { 109 double mean = meanAlgorithm.mean(values); 110 double sumOfSquaresOfDeltas = 0.0; 111 double c = 0.0; 112 for (double value : values) { 113 double delta = value - mean; 114 double deltaSquared = delta * delta; 115 double y = deltaSquared - c; 116 double t = sumOfSquaresOfDeltas + deltaSquared; 117 c = (t - sumOfSquaresOfDeltas) - y; 118 sumOfSquaresOfDeltas = t; 119 } 120 return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length); 121 } 122 }, 123 KNUTH { 124 @Override variance(double[] values, MeanAlgorithm meanAlgorithm)125 MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) { 126 if (meanAlgorithm != MeanAlgorithm.KNUTH) { 127 throw new SkipThisScenarioException(); 128 } 129 double mean = values[0]; 130 double s = 0.0; 131 for (int i = 1; i < values.length; i++) { 132 double nextMean = mean + (values[i] - mean) / (i + 1); 133 s += (values[i] - mean) * (values[i] - nextMean); 134 mean = nextMean; 135 } 136 return new MeanAndVariance(mean, s / values.length); 137 } 138 }; 139 variance(double[] values, MeanAlgorithm meanAlgorithm)140 abstract MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm); 141 } 142 143 @Param({"100", "10000"}) 144 int n; 145 146 @Param MeanAlgorithm meanAlgorithm; 147 @Param VarianceAlgorithm varianceAlgorithm; 148 149 private double[][] values = new double[0x100][]; 150 151 @BeforeExperiment setUp()152 void setUp() { 153 Random rng = new Random(); 154 for (int i = 0; i < 0x100; i++) { 155 values[i] = new double[n]; 156 for (int j = 0; j < n; j++) { 157 values[i][j] = rng.nextDouble(); 158 } 159 } 160 } 161 162 @Benchmark meanAndVariance(int reps)163 int meanAndVariance(int reps) { 164 int tmp = 0; 165 for (int i = 0; i < reps; i++) { 166 tmp += varianceAlgorithm.variance(values[i & 0xFF], meanAlgorithm).hashCode(); 167 } 168 return tmp; 169 } 170 } 171