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 <[email protected]> Authored: Sat Jun 2 21:23:08 2018 -0400 Committer: Benjamin Mahler <[email protected]> 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__
