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 <m...@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 {};
