discrete_distribution.cc (3544B)
1 // Copyright 2017 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "absl/random/discrete_distribution.h" 16 17 #include <cassert> 18 #include <cmath> 19 #include <cstddef> 20 #include <iterator> 21 #include <numeric> 22 #include <utility> 23 #include <vector> 24 25 #include "absl/base/config.h" 26 27 namespace absl { 28 ABSL_NAMESPACE_BEGIN 29 namespace random_internal { 30 31 // Initializes the distribution table for Walker's Aliasing algorithm, described 32 // in Knuth, Vol 2. as well as in https://en.wikipedia.org/wiki/Alias_method 33 std::vector<std::pair<double, size_t>> InitDiscreteDistribution( 34 std::vector<double>* probabilities) { 35 // The empty-case should already be handled by the constructor. 36 assert(probabilities); 37 assert(!probabilities->empty()); 38 39 // Step 1. Normalize the input probabilities to 1.0. 40 double sum = std::accumulate(std::begin(*probabilities), 41 std::end(*probabilities), 0.0); 42 if (std::fabs(sum - 1.0) > 1e-6) { 43 // Scale `probabilities` only when the sum is too far from 1.0. Scaling 44 // unconditionally will alter the probabilities slightly. 45 for (double& item : *probabilities) { 46 item = item / sum; 47 } 48 } 49 50 // Step 2. At this point `probabilities` is set to the conditional 51 // probabilities of each element which sum to 1.0, to within reasonable error. 52 // These values are used to construct the proportional probability tables for 53 // the selection phases of Walker's Aliasing algorithm. 54 // 55 // To construct the table, pick an element which is under-full (i.e., an 56 // element for which `(*probabilities)[i] < 1.0/n`), and pair it with an 57 // element which is over-full (i.e., an element for which 58 // `(*probabilities)[i] > 1.0/n`). The smaller value can always be retired. 59 // The larger may still be greater than 1.0/n, or may now be less than 1.0/n, 60 // and put back onto the appropriate collection. 61 const size_t n = probabilities->size(); 62 std::vector<std::pair<double, size_t>> q; 63 q.reserve(n); 64 65 std::vector<size_t> over; 66 std::vector<size_t> under; 67 size_t idx = 0; 68 for (const double item : *probabilities) { 69 assert(item >= 0); 70 const double v = item * n; 71 q.emplace_back(v, 0); 72 if (v < 1.0) { 73 under.push_back(idx++); 74 } else { 75 over.push_back(idx++); 76 } 77 } 78 while (!over.empty() && !under.empty()) { 79 auto lo = under.back(); 80 under.pop_back(); 81 auto hi = over.back(); 82 over.pop_back(); 83 84 q[lo].second = hi; 85 const double r = q[hi].first - (1.0 - q[lo].first); 86 q[hi].first = r; 87 if (r < 1.0) { 88 under.push_back(hi); 89 } else { 90 over.push_back(hi); 91 } 92 } 93 94 // Due to rounding errors, there may be un-paired elements in either 95 // collection; these should all be values near 1.0. For these values, set `q` 96 // to 1.0 and set the alternate to the identity. 97 for (auto i : over) { 98 q[i] = {1.0, i}; 99 } 100 for (auto i : under) { 101 q[i] = {1.0, i}; 102 } 103 return q; 104 } 105 106 } // namespace random_internal 107 ABSL_NAMESPACE_END 108 } // namespace absl