1# Copyright 2014 The Chromium Authors. All rights reserved. 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4 5import math 6import random 7import unittest 8 9from telemetry.util import statistics 10 11 12def Relax(samples, iterations=10): 13 """Lloyd relaxation in 1D. 14 15 Keeps the position of the first and last sample. 16 """ 17 for _ in xrange(0, iterations): 18 voronoi_boundaries = [] 19 for i in xrange(1, len(samples)): 20 voronoi_boundaries.append((samples[i] + samples[i-1]) * 0.5) 21 22 relaxed_samples = [] 23 relaxed_samples.append(samples[0]) 24 for i in xrange(1, len(samples)-1): 25 relaxed_samples.append( 26 (voronoi_boundaries[i-1] + voronoi_boundaries[i]) * 0.5) 27 relaxed_samples.append(samples[-1]) 28 samples = relaxed_samples 29 return samples 30 31def CreateRandomSamples(num_samples): 32 samples = [] 33 position = 0.0 34 samples.append(position) 35 for _ in xrange(1, num_samples): 36 position += random.random() 37 samples.append(position) 38 return samples 39 40class StatisticsUnitTest(unittest.TestCase): 41 42 def testNormalizeSamples(self): 43 samples = [] 44 normalized_samples, scale = statistics.NormalizeSamples(samples) 45 self.assertEquals(normalized_samples, []) 46 self.assertEquals(scale, 1.0) 47 48 samples = [0.0, 0.0] 49 normalized_samples, scale = statistics.NormalizeSamples(samples) 50 self.assertEquals(normalized_samples, [0.5, 0.5]) 51 self.assertEquals(scale, 1.0) 52 53 samples = [0.0, 1.0/3.0, 2.0/3.0, 1.0] 54 normalized_samples, scale = statistics.NormalizeSamples(samples) 55 self.assertEquals(normalized_samples, [1.0/8.0, 3.0/8.0, 5.0/8.0, 7.0/8.0]) 56 self.assertEquals(scale, 0.75) 57 58 samples = [1.0/8.0, 3.0/8.0, 5.0/8.0, 7.0/8.0] 59 normalized_samples, scale = statistics.NormalizeSamples(samples) 60 self.assertEquals(normalized_samples, samples) 61 self.assertEquals(scale, 1.0) 62 63 def testDiscrepancyRandom(self): 64 """Tests NormalizeSamples and Discrepancy with random samples. 65 66 Generates 10 sets of 10 random samples, computes the discrepancy, 67 relaxes the samples using Llloyd's algorithm in 1D, and computes the 68 discrepancy of the relaxed samples. Discrepancy of the relaxed samples 69 must be less than or equal to the discrepancy of the original samples. 70 """ 71 random.seed(1234567) 72 for _ in xrange(0, 10): 73 samples = CreateRandomSamples(10) 74 samples = statistics.NormalizeSamples(samples)[0] 75 d = statistics.Discrepancy(samples) 76 relaxed_samples = Relax(samples) 77 d_relaxed = statistics.Discrepancy(relaxed_samples) 78 self.assertTrue(d_relaxed <= d) 79 80 def testDiscrepancyAnalytic(self): 81 """Computes discrepancy for sample sets with known statistics.""" 82 samples = [] 83 d = statistics.Discrepancy(samples) 84 self.assertEquals(d, 0.0) 85 86 samples = [0.5] 87 d = statistics.Discrepancy(samples) 88 self.assertEquals(d, 0.5) 89 90 samples = [0.0, 1.0] 91 d = statistics.Discrepancy(samples) 92 self.assertEquals(d, 1.0) 93 94 samples = [0.5, 0.5, 0.5] 95 d = statistics.Discrepancy(samples) 96 self.assertEquals(d, 1.0) 97 98 samples = [1.0/8.0, 3.0/8.0, 5.0/8.0, 7.0/8.0] 99 d = statistics.Discrepancy(samples) 100 self.assertEquals(d, 0.25) 101 102 samples = [1.0/8.0, 5.0/8.0, 5.0/8.0, 7.0/8.0] 103 d = statistics.Discrepancy(samples) 104 self.assertEquals(d, 0.5) 105 106 samples = [1.0/8.0, 3.0/8.0, 5.0/8.0, 5.0/8.0, 7.0/8.0] 107 d = statistics.Discrepancy(samples) 108 self.assertEquals(d, 0.4) 109 110 samples = [0.0, 1.0/3.0, 2.0/3.0, 1.0] 111 d = statistics.Discrepancy(samples) 112 self.assertEquals(d, 0.5) 113 114 samples = statistics.NormalizeSamples(samples)[0] 115 d = statistics.Discrepancy(samples) 116 self.assertEquals(d, 0.25) 117 118 def testTimestampsDiscrepancy(self): 119 time_stamps = [] 120 d_abs = statistics.TimestampsDiscrepancy(time_stamps, True) 121 self.assertEquals(d_abs, 0.0) 122 123 time_stamps = [4] 124 d_abs = statistics.TimestampsDiscrepancy(time_stamps, True) 125 self.assertEquals(d_abs, 0.5) 126 127 time_stamps_a = [0, 1, 2, 3, 5, 6] 128 time_stamps_b = [0, 1, 2, 3, 5, 7] 129 time_stamps_c = [0, 2, 3, 4] 130 time_stamps_d = [0, 2, 3, 4, 5] 131 132 d_abs_a = statistics.TimestampsDiscrepancy(time_stamps_a, True) 133 d_abs_b = statistics.TimestampsDiscrepancy(time_stamps_b, True) 134 d_abs_c = statistics.TimestampsDiscrepancy(time_stamps_c, True) 135 d_abs_d = statistics.TimestampsDiscrepancy(time_stamps_d, True) 136 d_rel_a = statistics.TimestampsDiscrepancy(time_stamps_a, False) 137 d_rel_b = statistics.TimestampsDiscrepancy(time_stamps_b, False) 138 d_rel_c = statistics.TimestampsDiscrepancy(time_stamps_c, False) 139 d_rel_d = statistics.TimestampsDiscrepancy(time_stamps_d, False) 140 141 self.assertTrue(d_abs_a < d_abs_b) 142 self.assertTrue(d_rel_a < d_rel_b) 143 self.assertTrue(d_rel_d < d_rel_c) 144 self.assertAlmostEquals(d_abs_d, d_abs_c) 145 146 def testDiscrepancyMultipleRanges(self): 147 samples = [[0.0, 1.2, 2.3, 3.3], [6.3, 7.5, 8.4], [4.2, 5.4, 5.9]] 148 d_0 = statistics.TimestampsDiscrepancy(samples[0]) 149 d_1 = statistics.TimestampsDiscrepancy(samples[1]) 150 d_2 = statistics.TimestampsDiscrepancy(samples[2]) 151 d = statistics.TimestampsDiscrepancy(samples) 152 self.assertEquals(d, max(d_0, d_1, d_2)) 153 154 def testApproximateDiscrepancy(self): 155 """Tests approimate discrepancy implementation by comparing to exact 156 solution. 157 """ 158 random.seed(1234567) 159 for _ in xrange(0, 5): 160 samples = CreateRandomSamples(10) 161 samples = statistics.NormalizeSamples(samples)[0] 162 d = statistics.Discrepancy(samples) 163 d_approx = statistics.Discrepancy(samples, 500) 164 self.assertEquals(round(d, 2), round(d_approx, 2)) 165 166 def testPercentile(self): 167 # The 50th percentile is the median value. 168 self.assertEquals(3, statistics.Percentile([4, 5, 1, 3, 2], 50)) 169 self.assertEquals(2.5, statistics.Percentile([5, 1, 3, 2], 50)) 170 # When the list of values is empty, 0 is returned. 171 self.assertEquals(0, statistics.Percentile([], 50)) 172 # When the given percentage is very low, the lowest value is given. 173 self.assertEquals(1, statistics.Percentile([2, 1, 5, 4, 3], 5)) 174 # When the given percentage is very high, the highest value is given. 175 self.assertEquals(5, statistics.Percentile([5, 2, 4, 1, 3], 95)) 176 # Linear interpolation between closest ranks is used. Using the example 177 # from <http://en.wikipedia.org/wiki/Percentile>: 178 self.assertEquals(27.5, statistics.Percentile([15, 20, 35, 40, 50], 40)) 179 180 def testArithmeticMean(self): 181 # The ArithmeticMean function computes the simple average. 182 self.assertAlmostEquals(40/3.0, statistics.ArithmeticMean([10, 10, 20])) 183 self.assertAlmostEquals(15.0, statistics.ArithmeticMean([10, 20])) 184 # If the 'count' is zero, then zero is returned. 185 self.assertEquals(0, statistics.ArithmeticMean([])) 186 187 def testDurationsDiscrepancy(self): 188 durations = [] 189 d = statistics.DurationsDiscrepancy(durations) 190 self.assertEquals(d, 0.0) 191 192 durations = [4] 193 d = statistics.DurationsDiscrepancy(durations) 194 self.assertEquals(d, 4.0) 195 196 durations_a = [1, 1, 1, 1, 1] 197 durations_b = [1, 1, 2, 1, 1] 198 durations_c = [1, 2, 1, 2, 1] 199 200 d_a = statistics.DurationsDiscrepancy(durations_a) 201 d_b = statistics.DurationsDiscrepancy(durations_b) 202 d_c = statistics.DurationsDiscrepancy(durations_c) 203 204 self.assertTrue(d_a < d_b < d_c) 205 206 def testStandardDeviation(self): 207 self.assertAlmostEquals(math.sqrt(2/3.0), 208 statistics.StandardDeviation([1, 2, 3])) 209 self.assertEquals(0, statistics.StandardDeviation([1])) 210 self.assertEquals(0, statistics.StandardDeviation([])) 211 212 def testTrapezoidalRule(self): 213 self.assertEquals(4, statistics.TrapezoidalRule([1, 2, 3], 1)) 214 self.assertEquals(2, statistics.TrapezoidalRule([1, 2, 3], .5)) 215 self.assertEquals(0, statistics.TrapezoidalRule([1, 2, 3], 0)) 216 self.assertEquals(-4, statistics.TrapezoidalRule([1, 2, 3], -1)) 217 self.assertEquals(3, statistics.TrapezoidalRule([-1, 2, 3], 1)) 218 self.assertEquals(0, statistics.TrapezoidalRule([1], 1)) 219 self.assertEquals(0, statistics.TrapezoidalRule([0], 1)) 220