src/tools/perf/metrics/statistics_unittest.py

   1 # Copyright 2013 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 unittest
   6 import random
   7
   8 from metrics import statistics
   9
  10
  11 def Relax(samples, iterations=10):
  12   """Lloyd relaxation in 1D.
  13
  14   Keeps the position of the first and last sample.
  15   """
  16   for _ in xrange(0, iterations):
  17     voronoi_boundaries = []
  18     for i in xrange(1, len(samples)):
  19       voronoi_boundaries.append((samples[i] + samples[i-1]) * 0.5)
  20
  21     relaxed_samples = []
  22     relaxed_samples.append(samples[0])
  23     for i in xrange(1, len(samples)-1):
  24       relaxed_samples.append(
  25           (voronoi_boundaries[i-1] + voronoi_boundaries[i]) * 0.5)
  26     relaxed_samples.append(samples[-1])
  27     samples = relaxed_samples
  28   return samples
  29
  30
  31 class StatisticsUnitTest(unittest.TestCase):
  32
  33   def testNormalizeSamples(self):
  34     samples = []
  35     normalized_samples, scale = statistics.NormalizeSamples(samples)
  36     self.assertEquals(normalized_samples, samples)
  37     self.assertEquals(scale, 1.0)
  38
  39     samples = [0.0, 0.0]
  40     normalized_samples, scale = statistics.NormalizeSamples(samples)
  41     self.assertEquals(normalized_samples, samples)
  42     self.assertEquals(scale, 1.0)
  43
  44     samples = [0.0, 1.0/3.0, 2.0/3.0, 1.0]
  45     normalized_samples, scale = statistics.NormalizeSamples(samples)
  46     self.assertEquals(normalized_samples, [1.0/8.0, 3.0/8.0, 5.0/8.0, 7.0/8.0])
  47     self.assertEquals(scale, 0.75)
  48
  49     samples = [1.0/8.0, 3.0/8.0, 5.0/8.0, 7.0/8.0]
  50     normalized_samples, scale = statistics.NormalizeSamples(samples)
  51     self.assertEquals(normalized_samples, samples)
  52     self.assertEquals(scale, 1.0)
  53
  54   def testDiscrepancyRandom(self):
  55     """Tests NormalizeSamples and Discrepancy with random samples.
  56
  57     Generates 10 sets of 10 random samples, computes the discrepancy,
  58     relaxes the samples using Llloyd's algorithm in 1D, and computes the
  59     discrepancy of the relaxed samples. Discrepancy of the relaxed samples
  60     must be less than or equal to the discrepancy of the original samples.
  61     """
  62     random.seed(1234567)
  63     for _ in xrange(0, 10):
  64       samples = []
  65       num_samples = 10
  66       clock = 0.0
  67       samples.append(clock)
  68       for _ in xrange(1, num_samples):
  69         clock += random.random()
  70         samples.append(clock)
  71       samples = statistics.NormalizeSamples(samples)[0]
  72       d = statistics.Discrepancy(samples)
  73
  74       relaxed_samples = Relax(samples)
  75       d_relaxed = statistics.Discrepancy(relaxed_samples)
  76
  77       self.assertTrue(d_relaxed <= d)
  78
  79   def testDiscrepancyAnalytic(self):
  80     """Computes discrepancy for sample sets with known statistics."""
  81     interval_multiplier = 100000
  82
  83     samples = []
  84     d = statistics.Discrepancy(samples, interval_multiplier)
  85     self.assertEquals(d, 1.0)
  86
  87     samples = [0.5]
  88     d = statistics.Discrepancy(samples, interval_multiplier)
  89     self.assertEquals(round(d), 1.0)
  90
  91     samples = [0.0, 1.0]
  92     d = statistics.Discrepancy(samples, interval_multiplier)
  93     self.assertAlmostEquals(round(d, 2), 1.0)
  94
  95     samples = [0.5, 0.5, 0.5]
  96     d = statistics.Discrepancy(samples, interval_multiplier)
  97     self.assertAlmostEquals(d, 1.0)
  98
  99     samples = [1.0/8.0, 3.0/8.0, 5.0/8.0, 7.0/8.0]
 100     d = statistics.Discrepancy(samples, interval_multiplier)
 101     self.assertAlmostEquals(round(d, 2), 0.25)
 102
 103     samples = [0.0, 1.0/3.0, 2.0/3.0, 1.0]
 104     d = statistics.Discrepancy(samples, interval_multiplier)
 105     self.assertAlmostEquals(round(d, 2), 0.5)
 106
 107     samples = statistics.NormalizeSamples(samples)[0]
 108     d = statistics.Discrepancy(samples, interval_multiplier)
 109     self.assertAlmostEquals(round(d, 2), 0.25)
 110
 111     time_stamps_a = [0, 1, 2, 3, 5, 6]
 112     time_stamps_b = [0, 1, 2, 3, 5, 7]
 113     time_stamps_c = [0, 2, 3, 4]
 114     time_stamps_d = [0, 2, 3, 4, 5]
 115     d_abs_a = statistics.FrameDiscrepancy(time_stamps_a, True,
 116                                            interval_multiplier)
 117     d_abs_b = statistics.FrameDiscrepancy(time_stamps_b, True,
 118                                            interval_multiplier)
 119     d_abs_c = statistics.FrameDiscrepancy(time_stamps_c, True,
 120                                            interval_multiplier)
 121     d_abs_d = statistics.FrameDiscrepancy(time_stamps_d, True,
 122                                            interval_multiplier)
 123     d_rel_a = statistics.FrameDiscrepancy(time_stamps_a, False,
 124                                            interval_multiplier)
 125     d_rel_b = statistics.FrameDiscrepancy(time_stamps_b, False,
 126                                            interval_multiplier)
 127     d_rel_c = statistics.FrameDiscrepancy(time_stamps_c, False,
 128                                            interval_multiplier)
 129     d_rel_d = statistics.FrameDiscrepancy(time_stamps_d, False,
 130                                            interval_multiplier)
 131
 132     self.assertTrue(d_abs_a < d_abs_b)
 133     self.assertTrue(d_rel_a < d_rel_b)
 134     self.assertTrue(d_rel_d < d_rel_c)
 135     self.assertEquals(round(d_abs_d, 2), round(d_abs_c, 2))
 136
 137   def testPercentile(self):
 138     # The 50th percentile is the median value.
 139     self.assertEquals(3, statistics.Percentile([4, 5, 1, 3, 2], 50))
 140     self.assertEquals(2.5, statistics.Percentile([5, 1, 3, 2], 50))
 141     # When the list of values is empty, 0 is returned.
 142     self.assertEquals(0, statistics.Percentile([], 50))
 143     # When the given percentage is very low, the lowest value is given.
 144     self.assertEquals(1, statistics.Percentile([2, 1, 5, 4, 3], 5))
 145     # When the given percentage is very high, the highest value is given.
 146     self.assertEquals(5, statistics.Percentile([5, 2, 4, 1, 3], 95))
 147     # Linear interpolation between closest ranks is used. Using the example
 148     # from <http://en.wikipedia.org/wiki/Percentile>:
 149     self.assertEquals(27.5, statistics.Percentile([15, 20, 35, 40, 50], 40))
 150
 151   def testArithmeticMean(self):
 152     # The ArithmeticMean function computes the simple average.
 153     self.assertAlmostEquals(40/3.0, statistics.ArithmeticMean([10, 10, 20], 3))
 154     self.assertAlmostEquals(15.0, statistics.ArithmeticMean([10, 20], 2))
 155     # Both lists of values or single values can be given for either argument.
 156     self.assertAlmostEquals(40/3.0, statistics.ArithmeticMean(40, [1, 1, 1]))
 157     # If the 'count' is zero, then zero is returned.
 158     self.assertEquals(0, statistics.ArithmeticMean(4.0, 0))
 159     self.assertEquals(0, statistics.ArithmeticMean(4.0, []))
 160