Function TEST

src/tests/sorter_tests.cpp:57–101

Test the behavior of weighted shuffle by ensuring that the probability distribution after a number of runs is within a particular error bound.

// 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 the behavior of the random sorter by ensuring that the