about summary refs log tree commit diff
path: root/third_party/abseil_cpp/absl/random/discrete_distribution.cc
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/abseil_cpp/absl/random/discrete_distribution.cc')
-rw-r--r--third_party/abseil_cpp/absl/random/discrete_distribution.cc98
1 files changed, 0 insertions, 98 deletions
diff --git a/third_party/abseil_cpp/absl/random/discrete_distribution.cc b/third_party/abseil_cpp/absl/random/discrete_distribution.cc
deleted file mode 100644
index 081accee52a4..000000000000
--- a/third_party/abseil_cpp/absl/random/discrete_distribution.cc
+++ /dev/null
@@ -1,98 +0,0 @@
-// 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 {
-ABSL_NAMESPACE_BEGIN
-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
-ABSL_NAMESPACE_END
-}  // namespace absl