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