Apache Mesos
utils.hpp
Go to the documentation of this file.
1 // Licensed to the Apache Software Foundation (ASF) under one
2 // or more contributor license agreements. See the NOTICE file
3 // distributed with this work for additional information
4 // regarding copyright ownership. The ASF licenses this file
5 // to you under the Apache License, Version 2.0 (the
6 // "License"); you may not use this file except in compliance
7 // with the License. You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 
17 #ifndef __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
18 #define __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
19 
20 #include <algorithm>
21 #include <cmath>
22 #include <numeric>
23 #include <random>
24 #include <vector>
25 
26 #include <stout/check.hpp>
27 
28 namespace mesos {
29 namespace internal {
30 namespace master {
31 namespace allocator {
32 
33 // A weighted variant of std::shuffle. Items with higher weight
34 // have a higher chance of being towards the front of the list,
35 // equivalent to weighted random sampling without replacement.
36 // Code adapted from the following paper:
37 //
38 // http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
39 // Found from: https://softwareengineering.stackexchange.com/a/344274
40 //
41 // This has O(n log n) runtime complexity.
42 template <class RandomAccessIterator, class URBG>
44  RandomAccessIterator begin,
45  RandomAccessIterator end,
46  const std::vector<double>& weights,
47  URBG&& urbg)
48 {
49  CHECK_EQ(end - begin, (int) weights.size());
50 
51  std::vector<double> keys(weights.size());
52 
53  for (size_t i = 0; i < weights.size(); ++i) {
54  CHECK_GT(weights[i], 0.0);
55 
56  // Make the key negative so that we don't have to reverse sort.
57  double random = std::uniform_real_distribution<>(0.0, 1.0)(urbg);
58  keys[i] = 0.0 - std::pow(random, (1.0 / weights[i]));
59  }
60 
61  // Sort from smallest to largest keys. We store the sort permutation
62  // so that we can apply it to `items`.
63  std::vector<size_t> permutation(keys.size());
64  std::iota(permutation.begin(), permutation.end(), 0);
65 
66  std::sort(permutation.begin(), permutation.end(),
67  [&](size_t i, size_t j){ return keys[i] < keys[j]; });
68 
69  // Now apply the permutation to `items`.
70  std::vector<typename std::iterator_traits<RandomAccessIterator>::value_type>
71  shuffled(end - begin);
72 
74  permutation.begin(),
75  permutation.end(),
76  shuffled.begin(),
77  [&](size_t i){ return begin[i]; });
78 
79  // Move the shuffled copy back into the `items`.
80  std::move(shuffled.begin(), shuffled.end(), begin);
81 }
82 
83 } // namespace allocator {
84 } // namespace master {
85 } // namespace internal {
86 } // namespace mesos {
87 
88 #endif // __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
Definition: master.hpp:27
Definition: agent.hpp:25
int random()
Definition: os.hpp:580
void weightedShuffle(RandomAccessIterator begin, RandomAccessIterator end, const std::vector< double > &weights, URBG &&urbg)
Definition: utils.hpp:43
process::Future< Nothing > transform(process::Owned< Reader< T >> &&reader, const std::function< std::string(const T &)> &func, process::http::Pipe::Writer writer)
This is a helper function that reads records from a Reader, applies a transformation to the records a...
Definition: recordio.hpp:112
Definition: attributes.hpp:24