[3/6] mesos git commit: Introduced a weighted shuffle algorithm implementation.

[bm...@apache.org]

Introduced a weighted shuffle algorithm implementation.

This will be used by the random sorter in order to support weights.

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


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

Branch: refs/heads/master
Commit: 0912ff8aa7f283994fbdbaa9f6a95a114310af5e
Parents: 6ed9882
Author: Benjamin Mahler <bm...@apache.org>
Authored: Sat Jun 2 21:23:08 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Mon Jun 4 17:15:49 2018 -0400

----------------------------------------------------------------------
 src/Makefile.am                              |  1 +
 src/master/allocator/sorter/random/utils.hpp | 92 +++++++++++++++++++++++
 2 files changed, 93 insertions(+)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/mesos/blob/0912ff8a/src/Makefile.am
----------------------------------------------------------------------
diff --git a/src/Makefile.am b/src/Makefile.am
index 874305a..dcf8d5f 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1168,6 +1168,7 @@ libmesos_no_3rdparty_la_SOURCES +=					\
   master/allocator/sorter/sorter.hpp					\
   master/allocator/sorter/drf/metrics.hpp				\
   master/allocator/sorter/drf/sorter.hpp				\
+  master/allocator/sorter/random/utils.hpp				\
   master/contender/standalone.hpp					\
   master/contender/zookeeper.hpp					\
   master/detector/standalone.hpp					\

http://git-wip-us.apache.org/repos/asf/mesos/blob/0912ff8a/src/master/allocator/sorter/random/utils.hpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/random/utils.hpp b/src/master/allocator/sorter/random/utils.hpp
new file mode 100644
index 0000000..1329359
--- /dev/null
+++ b/src/master/allocator/sorter/random/utils.hpp
@@ -0,0 +1,92 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
+#define __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
+
+#include <algorithm>
+#include <cmath>
+#include <numeric>
+#include <random>
+#include <vector>
+
+#include <stout/check.hpp>
+
+namespace mesos {
+namespace internal {
+namespace master {
+namespace allocator {
+
+// A weighted variant of std::shuffle. Items with higher weight
+// have a higher chance of being towards the front of the list,
+// equivalent to weighted random sampling without replacement.
+// Code adapted from the following paper:
+//
+// http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
+// Found from: https://softwareengineering.stackexchange.com/a/344274
+//
+// This has O(n log n) runtime complexity.
+template <class RandomAccessIterator, class URBG>
+void weightedShuffle(
+    RandomAccessIterator begin,
+    RandomAccessIterator end,
+    const std::vector<double>& weights,
+    URBG&& urbg)
+{
+  CHECK_EQ(end - begin, (int) weights.size());
+
+  std::vector<double> keys(weights.size());
+
+  for (size_t i = 0; i < weights.size(); ++i) {
+    CHECK_GT(weights[i], 0.0);
+
+    // Make the key negative so that we don't have to reverse sort.
+    double random = std::uniform_real_distribution<>(0.0, 1.0)(urbg);
+    keys[i] = 0.0 - std::pow(random, (1.0 / weights[i]));
+  }
+
+  // Sort from smallest to largest keys. We store the sort permutation
+  // so that we can apply it to `items`.
+  std::vector<size_t> permutation(keys.size());
+  std::iota(permutation.begin(), permutation.end(), 0);
+
+  std::sort(permutation.begin(), permutation.end(),
+      [&](size_t i, size_t j){ return keys[i] < keys[j]; });
+
+  // Now apply the permutation to `items`.
+  //
+  // TODO(bmahler): Consider avoiding the copy of entries in `items`
+  // via an in-place application of the permutation:
+  //   https://blog.merovius.de/2014/08/12/applying-permutation-in-constant.html
+  std::vector<typename std::iterator_traits<RandomAccessIterator>::value_type>
+    shuffled(end - begin);
+
+  std::transform(
+      permutation.begin(),
+      permutation.end(),
+      shuffled.begin(),
+      [&](size_t i){ return begin[i]; });
+
+  // Move the shuffled copy back into the `items`.
+  std::move(shuffled.begin(), shuffled.end(), begin);
+}
+
+} // namespace allocator {
+} // namespace master {
+} // namespace internal {
+} // namespace mesos {
+
+#endif // __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__