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/c9911766 Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/c9911766 Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/c9911766 Branch: refs/heads/master Commit: c9911766a57d0abd11c47276a10e21d4cbee7124 Parents: 0912ff8 Author: Benjamin Mahler <[email protected]> Authored: Sat Jun 2 21:25:58 2018 -0400 Committer: Benjamin Mahler <[email protected]> Committed: Mon Jun 4 17:15:49 2018 -0400 ---------------------------------------------------------------------- src/tests/sorter_tests.cpp | 51 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/mesos/blob/c9911766/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) {
