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 
25 import java.util.Random;
26 
27 /**
28  * Benchmarks for various algorithms for computing the mean and/or variance.
29  *
30  * @author Louis Wasserman
31  */
32 public class StatsBenchmark {
33 
34   enum MeanAlgorithm {
35     SIMPLE {
36       @Override
mean(double[] values)37       double mean(double[] values) {
38         double sum = 0.0;
39         for (double value : values) {
40           sum += value;
41         }
42         return sum / values.length;
43       }
44     },
45     KAHAN {
46       @Override
mean(double[] values)47       double mean(double[] values) {
48         double sum = 0.0;
49         double c = 0.0;
50         for (double value : values) {
51           double y = value - c;
52           double t = sum + y;
53           c = (t - sum) - y;
54           sum = t;
55         }
56         return sum / values.length;
57       }
58     },
59     KNUTH {
60       @Override
mean(double[] values)61       double mean(double[] values) {
62         double mean = values[0];
63         for (int i = 1; i < values.length; i++) {
64           mean = mean + (values[i] - mean) / (i + 1);
65         }
66         return mean;
67       }
68     };
69 
mean(double[] values)70     abstract double mean(double[] values);
71   }
72 
73   static class MeanAndVariance {
74     private final double mean;
75     private final double variance;
76 
MeanAndVariance(double mean, double variance)77     MeanAndVariance(double mean, double variance) {
78       this.mean = mean;
79       this.variance = variance;
80     }
81 
82     @Override
hashCode()83     public int hashCode() {
84       return Doubles.hashCode(mean) * 31 + Doubles.hashCode(variance);
85     }
86   }
87 
88   enum VarianceAlgorithm {
89     DO_NOT_COMPUTE {
90       @Override
variance(double[] values, MeanAlgorithm meanAlgorithm)91       MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
92         return new MeanAndVariance(meanAlgorithm.mean(values), 0.0);
93       }
94     },
95     SIMPLE {
96       @Override
variance(double[] values, MeanAlgorithm meanAlgorithm)97       MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
98         double mean = meanAlgorithm.mean(values);
99         double sumOfSquaresOfDeltas = 0.0;
100         for (double value : values) {
101           double delta = value - mean;
102           sumOfSquaresOfDeltas += delta * delta;
103         }
104         return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length);
105       }
106     },
107     KAHAN {
108       @Override
variance(double[] values, MeanAlgorithm meanAlgorithm)109       MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
110         double mean = meanAlgorithm.mean(values);
111         double sumOfSquaresOfDeltas = 0.0;
112         double c = 0.0;
113         for (double value : values) {
114           double delta = value - mean;
115           double deltaSquared = delta * delta;
116           double y = deltaSquared - c;
117           double t = sumOfSquaresOfDeltas + deltaSquared;
118           c = (t - sumOfSquaresOfDeltas) - y;
119           sumOfSquaresOfDeltas = t;
120         }
121         return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length);
122       }
123     },
124     KNUTH {
125       @Override
variance(double[] values, MeanAlgorithm meanAlgorithm)126       MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
127         if (meanAlgorithm != MeanAlgorithm.KNUTH) {
128           throw new SkipThisScenarioException();
129         }
130         double mean = values[0];
131         double s = 0.0;
132         for (int i = 1; i < values.length; i++) {
133           double nextMean = mean + (values[i] - mean) / (i + 1);
134           s += (values[i] - mean) * (values[i] - nextMean);
135           mean = nextMean;
136         }
137         return new MeanAndVariance(mean, s / values.length);
138       }
139     };
140 
variance(double[] values, MeanAlgorithm meanAlgorithm)141     abstract MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm);
142   }
143 
144   @Param({"100", "10000"})
145   int n;
146 
147   @Param
148   MeanAlgorithm meanAlgorithm;
149   @Param
150   VarianceAlgorithm varianceAlgorithm;
151 
152   private double[][] values = new double[0x100][];
153 
154   @BeforeExperiment
setUp()155   void setUp() {
156     Random rng = new Random();
157     for (int i = 0; i < 0x100; i++) {
158       values[i] = new double[n];
159       for (int j = 0; j < n; j++) {
160         values[i][j] = rng.nextDouble();
161       }
162     }
163   }
164 
meanAndVariance(int reps)165   @Benchmark int meanAndVariance(int reps) {
166     int tmp = 0;
167     for (int i = 0; i < reps; i++) {
168       tmp += varianceAlgorithm.variance(values[i & 0xFF], meanAlgorithm).hashCode();
169     }
170     return tmp;
171   }
172 }
173