src/tools/telemetry/telemetry/util/statistics_unittest.py

   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
   5 import math
   6 import random
   7 import unittest
   8
   9 from telemetry.util import statistics
  10
  11
  12 def 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
  31 def 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
  40 class 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))