[mesos] branch master updated: Added a test to verify the sort correctness of the random sorter.

[mz...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

mzhu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mesos.git


The following commit(s) were added to refs/heads/master by this push:
     new 89c3dd9  Added a test to verify the sort correctness of the random sorter.
89c3dd9 is described below

commit 89c3dd95a421e14044bc91ceb1998ff4ae3883b4
Author: Meng Zhu <mz...@mesosphere.io>
AuthorDate: Sun Apr 7 15:55:42 2019 -0700

    Added a test to verify the sort correctness of the random sorter.
    
    Review: https://reviews.apache.org/r/70418
---
 src/tests/sorter_tests.cpp | 53 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)

diff --git a/src/tests/sorter_tests.cpp b/src/tests/sorter_tests.cpp
index c9a0bda..9aee2b4 100644
--- a/src/tests/sorter_tests.cpp
+++ b/src/tests/sorter_tests.cpp
@@ -170,6 +170,59 @@ TEST(RandomSorterTest, HierarchicalProbabilityDistribution)
 }
 
 
+TEST(RandomSorterTest, ProbabilityDistribution)
+{
+  // Test the behavior of the random sorter by ensuring that the
+  // probability distribution after a number of runs is within
+  // a particular error bound.
+
+  RandomSorter sorter;
+
+  vector<string> clients = {"0", "1", "2", "3", "4"};
+  vector<double> weights = {1.0, 2.0, 3.0, 4.0, 5.0};
+
+  for (size_t i = 0; i < 5; ++i) {
+    sorter.add(clients.at(i));
+    sorter.activate(clients.at(i));
+    sorter.updateWeight(clients.at(i), weights.at(i));
+  }
+
+  // Count of how many times client i returned as the jth client
+  // in the sort result.
+  size_t totalRuns = 1000u;
+  size_t counts[5][5] = {};
+
+  for (size_t run = 0; run < totalRuns; ++run) {
+    vector<string> candidates = sorter.sort();
+    for (size_t i = 0; i < candidates.size(); ++i) {
+      ++counts[std::stoi(candidates.at(i))][i];
+    }
+  }
+
+  // This table was generated by running a weighted shuffle algorithm
+  // for a large number of iterations.
+  double expectedProbabilities[5][5] = {
+    {0.07, 0.08, 0.12, 0.20, 0.54},
+    {0.13, 0.16, 0.20, 0.28, 0.23},
+    {0.20, 0.22, 0.24, 0.22, 0.12},
+    {0.27, 0.26, 0.23, 0.17, 0.07},
+    {0.33, 0.28, 0.21, 0.13, 0.04},
+  };
+
+  double actualProbabilities[5][5];
+
+  for (int i = 0; i < 5; ++i) {
+    for (int j = 0; j < 5; ++j) {
+      actualProbabilities[i][j] = counts[i][j] / (1.0 * totalRuns);
+
+      // Assert that the actual probabilities differ less than
+      // an absolute 5%.
+      ASSERT_NEAR(expectedProbabilities[i][j], actualProbabilities[i][j], 0.05);
+    }
+  }
+}
+
+
 template <typename T>
 class CommonSorterTest : public ::testing::Test {};