[2/7] mesos git commit: Added a test for weighted shuffling.

[bm...@apache.org]

Added a test for weighted shuffling.

Review: https://reviews.apache.org/r/67370/


Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/16b9eb20
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/16b9eb20
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/16b9eb20

Branch: refs/heads/1.6.x
Commit: 16b9eb20eea035db0cbba989356ceb78933101fe
Parents: 15d54f0
Author: Benjamin Mahler <bm...@apache.org>
Authored: Sat Jun 2 21:25:58 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Fri Jun 29 16:32:24 2018 -0700

----------------------------------------------------------------------
 src/tests/sorter_tests.cpp | 51 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/mesos/blob/16b9eb20/src/tests/sorter_tests.cpp
----------------------------------------------------------------------
diff --git a/src/tests/sorter_tests.cpp b/src/tests/sorter_tests.cpp
index da4e0f6..b86e8b5 100644
--- a/src/tests/sorter_tests.cpp
+++ b/src/tests/sorter_tests.cpp
@@ -26,6 +26,8 @@
 
 #include "master/allocator/sorter/drf/sorter.hpp"
 
+#include "master/allocator/sorter/random/utils.hpp"
+
 #include "tests/mesos.hpp"
 #include "tests/resources_utils.hpp"
 
@@ -40,6 +42,55 @@ namespace mesos {
 namespace internal {
 namespace tests {
 
+// Test the behavior of weighted shuffle by ensuring that the
+// probability distribution after a number of runs is within
+// a particular error bound.
+TEST(WeightedShuffleTest, ProbabilityDistribution)
+{
+  std::mt19937 generator(0); // Pass a consistent seed.
+
+  // Count of how many times item i was shuffled into position j.
+  size_t totalRuns = 1000u;
+  size_t counts[5][5] = {};
+
+  for (size_t run = 0; run < totalRuns; ++run) {
+    //   Items: [  0, ...,   4]
+    // Weights: [1.0, ..., 5.0]
+    vector<size_t> items = {0, 1, 2, 3, 4};
+    vector<double> weights = {1.0, 2.0, 3.0, 4.0, 5.0};
+
+    mesos::internal::master::allocator::weightedShuffle(
+        items.begin(), items.end(), weights, generator);
+
+    for (size_t i = 0; i < items.size(); ++i) {
+      // Count the item landing in position i.
+      ++counts[items[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);
+    }
+  }
+}
+
 
 TEST(SorterTest, DRFSorter)
 {