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 namespace absl {
18 ABSL_NAMESPACE_BEGIN
19 namespace random_internal {
20
21 // Initializes the distribution table for Walker's Aliasing algorithm, described
22 // in Knuth, Vol 2. as well as in https://en.wikipedia.org/wiki/Alias_method
InitDiscreteDistribution(std::vector<double> * probabilities)23 std::vector<std::pair<double, size_t>> InitDiscreteDistribution(
24 std::vector<double>* probabilities) {
25 // The empty-case should already be handled by the constructor.
26 assert(probabilities);
27 assert(!probabilities->empty());
28
29 // Step 1. Normalize the input probabilities to 1.0.
30 double sum = std::accumulate(std::begin(*probabilities),
31 std::end(*probabilities), 0.0);
32 if (std::fabs(sum - 1.0) > 1e-6) {
33 // Scale `probabilities` only when the sum is too far from 1.0. Scaling
34 // unconditionally will alter the probabilities slightly.
35 for (double& item : *probabilities) {
36 item = item / sum;
37 }
38 }
39
40 // Step 2. At this point `probabilities` is set to the conditional
41 // probabilities of each element which sum to 1.0, to within reasonable error.
42 // These values are used to construct the proportional probability tables for
43 // the selection phases of Walker's Aliasing algorithm.
44 //
45 // To construct the table, pick an element which is under-full (i.e., an
46 // element for which `(*probabilities)[i] < 1.0/n`), and pair it with an
47 // element which is over-full (i.e., an element for which
48 // `(*probabilities)[i] > 1.0/n`). The smaller value can always be retired.
49 // The larger may still be greater than 1.0/n, or may now be less than 1.0/n,
50 // and put back onto the appropriate collection.
51 const size_t n = probabilities->size();
52 std::vector<std::pair<double, size_t>> q;
53 q.reserve(n);
54
55 std::vector<size_t> over;
56 std::vector<size_t> under;
57 size_t idx = 0;
58 for (const double item : *probabilities) {
59 assert(item >= 0);
60 const double v = item * n;
61 q.emplace_back(v, 0);
62 if (v < 1.0) {
63 under.push_back(idx++);
64 } else {
65 over.push_back(idx++);
66 }
67 }
68 while (!over.empty() && !under.empty()) {
69 auto lo = under.back();
70 under.pop_back();
71 auto hi = over.back();
72 over.pop_back();
73
74 q[lo].second = hi;
75 const double r = q[hi].first - (1.0 - q[lo].first);
76 q[hi].first = r;
77 if (r < 1.0) {
78 under.push_back(hi);
79 } else {
80 over.push_back(hi);
81 }
82 }
83
84 // Due to rounding errors, there may be un-paired elements in either
85 // collection; these should all be values near 1.0. For these values, set `q`
86 // to 1.0 and set the alternate to the identity.
87 for (auto i : over) {
88 q[i] = {1.0, i};
89 }
90 for (auto i : under) {
91 q[i] = {1.0, i};
92 }
93 return q;
94 }
95
96 } // namespace random_internal
97 ABSL_NAMESPACE_END
98 } // namespace absl
99