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
InitDiscreteDistribution(std::vector<double> * probabilities)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
109