summaryrefslogtreecommitdiff
path: root/absl/random/discrete_distribution.cc
diff options
context:
space:
mode:
Diffstat (limited to 'absl/random/discrete_distribution.cc')
-rw-r--r--absl/random/discrete_distribution.cc98
1 files changed, 98 insertions, 0 deletions
diff --git a/absl/random/discrete_distribution.cc b/absl/random/discrete_distribution.cc
new file mode 100644
index 00000000..13a2dbe4
--- /dev/null
+++ b/absl/random/discrete_distribution.cc
@@ -0,0 +1,98 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed 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
+//
+// https://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.
+
+#include "absl/random/discrete_distribution.h"
+
+namespace absl {
+inline namespace lts_2019_08_08 {
+namespace random_internal {
+
+// Initializes the distribution table for Walker's Aliasing algorithm, described
+// in Knuth, Vol 2. as well as in https://en.wikipedia.org/wiki/Alias_method
+std::vector<std::pair<double, size_t>> InitDiscreteDistribution(
+ std::vector<double>* probabilities) {
+ // The empty-case should already be handled by the constructor.
+ assert(probabilities);
+ assert(!probabilities->empty());
+
+ // Step 1. Normalize the input probabilities to 1.0.
+ double sum = std::accumulate(std::begin(*probabilities),
+ std::end(*probabilities), 0.0);
+ if (std::fabs(sum - 1.0) > 1e-6) {
+ // Scale `probabilities` only when the sum is too far from 1.0. Scaling
+ // unconditionally will alter the probabilities slightly.
+ for (double& item : *probabilities) {
+ item = item / sum;
+ }
+ }
+
+ // Step 2. At this point `probabilities` is set to the conditional
+ // probabilities of each element which sum to 1.0, to within reasonable error.
+ // These values are used to construct the proportional probability tables for
+ // the selection phases of Walker's Aliasing algorithm.
+ //
+ // To construct the table, pick an element which is under-full (i.e., an
+ // element for which `(*probabilities)[i] < 1.0/n`), and pair it with an
+ // element which is over-full (i.e., an element for which
+ // `(*probabilities)[i] > 1.0/n`). The smaller value can always be retired.
+ // The larger may still be greater than 1.0/n, or may now be less than 1.0/n,
+ // and put back onto the appropriate collection.
+ const size_t n = probabilities->size();
+ std::vector<std::pair<double, size_t>> q;
+ q.reserve(n);
+
+ std::vector<size_t> over;
+ std::vector<size_t> under;
+ size_t idx = 0;
+ for (const double item : *probabilities) {
+ assert(item >= 0);
+ const double v = item * n;
+ q.emplace_back(v, 0);
+ if (v < 1.0) {
+ under.push_back(idx++);
+ } else {
+ over.push_back(idx++);
+ }
+ }
+ while (!over.empty() && !under.empty()) {
+ auto lo = under.back();
+ under.pop_back();
+ auto hi = over.back();
+ over.pop_back();
+
+ q[lo].second = hi;
+ const double r = q[hi].first - (1.0 - q[lo].first);
+ q[hi].first = r;
+ if (r < 1.0) {
+ under.push_back(hi);
+ } else {
+ over.push_back(hi);
+ }
+ }
+
+ // Due to rounding errors, there may be un-paired elements in either
+ // collection; these should all be values near 1.0. For these values, set `q`
+ // to 1.0 and set the alternate to the identity.
+ for (auto i : over) {
+ q[i] = {1.0, i};
+ }
+ for (auto i : under) {
+ q[i] = {1.0, i};
+ }
+ return q;
+}
+
+} // namespace random_internal
+} // inline namespace lts_2019_08_08
+} // namespace absl