From aa844899c937bde5d2b24f276b59997e5b668bde Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 8 Aug 2019 10:56:58 -0700 Subject: Creation of LTS branch "lts_2019_08_08" - 9ee91d3e430fb33a4590486573792eb0fa146c2d Export of internal Abseil changes by Abseil Team - 8efba58a3b656e9b41fb0471ae6453425a61c520 Export of internal Abseil changes by Abseil Team - b49b8d16b67ec6912899684b732e6367f258cfdb Export of internal Abseil changes by Abseil Team - 67222ffc4c83d918ce8395aa61769eeb77df4c4d Export of internal Abseil changes by Abseil Team - c5c4db4f5191fe5e76cbf68dcc71fb28702f7d2b Export of internal Abseil changes by Abseil Team - 14550beb3b7b97195e483fb74b5efb906395c31e Export of internal Abseil changes. by Abseil Team - 52e88ee56b72cf32bc66534d942c7398ce481331 Export of internal Abseil changes. by Abseil Team - 36d37ab992038f52276ca66b9da80c1cf0f57dc2 Export of internal Abseil changes. by Abseil Team - ad1485c8986246b2ae9105e512738d0e97aec887 Export of internal Abseil changes. by Abseil Team - f3840bc5e33ce4932e35986cf3718450c6f02af2 Export of internal Abseil changes. by Abseil Team - 278b26058c036833a4f7f3047d3f4d9296527f87 Export of internal Abseil changes. by Abseil Team - c6c3c1b498e4ee939b24be59cae29d59c3863be8 Export of internal Abseil changes. by Abseil Team - 44efe96dfca674a17b45ca53fc77fb69f1e29bf4 Export of internal Abseil changes. by Abseil Team - 3c98fcc0461bd2a4b9c149d4748a7373a225cf4b Merge pull request #340 from jtsylve/macos_cxx17_fix by Matt Calabrese <38107210+mattcalabrese-google@users.noreply.github.com> - 74d91756c11bc22f9b0108b94da9326f7f9e376f Export of internal Abseil changes. by Abseil Team - e6b050212c859fbaf67abac76105da10ec348274 Export of internal Abseil changes. by Abseil Team - c964fcffac27bd4a9ff67fe393410dd1146ef8b8 Export of internal Abseil changes. by Abseil Team - 72e09a54d993b192db32be14c65adf7e9bd08c31 Export of internal Abseil changes. by Abseil Team - d65e19dfcd8697076f68598c0131c6930cdcd74d Export of internal Abseil changes. by Abseil Team - 5162fc83d2f3b79a9753ed59594c43966afdd37a Merge pull request #336 from shields/patch-2 by Shaindel Schwartz <31392632+shaindelschwartz@users.noreply.github.com> - 0389f7bf58fa41f35b3ad60be61d32f31e4f8ed6 Merge pull request #335 from shields/patch-1 by Shaindel Schwartz <31392632+shaindelschwartz@users.noreply.github.com> - e9324d926a9189e222741fce6e676f0944661a72 Export of internal Abseil changes. by Abseil Team - 43ef2148c0936ebf7cb4be6b19927a9d9d145b8f Export of internal Abseil changes. by Abseil Team - a13d3df2b3ba68aeead92e2d078fba0510d55024 Merge pull request #323 from gosnik/master by Gennadiy Rozental - 310a11865c97c5cdcc42a4ee2c2e3578423afe69 Merge pull request #324 from RasPat1/patch-1 by Gennadiy Rozental - 8f11724067248acc330b4d1f12f0c76d03f2cfb1 Export of internal Abseil changes. by Abseil Team - b1dd425423380126f6441ce4fbb6f8f6c75b793a Export of internal Abseil changes. by Abseil Team - 361cb8a9db2f2130442389fd80593255be26d681 Export of internal Abseil changes. by Abseil Team - 0238ab0a831f179518c1a814f9584e99da2d75a3 Merge pull request #321 from christoph-cullmann/c4245_fix... by Xiaoyi Zhang - 61c9bf3e3e1c28a4aa6d7f1be4b37fd473bb5529 Export of internal Abseil changes. by Abseil Team - bc9101f9982391019521161a36179b52555ed212 Merge pull request #320 from christoph-cullmann/master by Xiaoyi Zhang - 2f76a9bf50046e396138cc8eeb3cdc17b7a5ac24 Export of internal Abseil changes. by Abseil Team - 4adaf5490921f13028b55018c9f550277de5aebb Export of internal Abseil changes. by Abseil Team - 27c30ec671cb7b5ba84c4e79feff7fd0b0ac6338 Avoid undefined behavior when nullptr is passed to memcpy... by Roman Gershman - ce65f5ac3cbf897bb5e3de1a51d80fd00866abaa Export of internal Abseil changes. by Abseil Team - a18fc7461e7409c2ad64e28537261db1e02e76fa Export of internal Abseil changes. by Abseil Team - 8a394b19c149cab50534b04c5e21d42bc2217a7d Export of internal Abseil changes. by Abseil Team - daf381e8535a1f1f1b8a75966a74e7cca63dee89 Export of internal Abseil changes. by Abseil Team - fa00c321073c7ea40a4fc3dfc8a06309eae3d025 Export of internal Abseil changes. by Abseil Team - 436ba6c4a0ea3a06eca6e055f9c8d296bf3bae12 Export of internal Abseil changes. by Abseil Team - 0cbdc774b97f7e80ab60dbe2ed4eaca3b2e33fc8 Export of internal Abseil changes. by Abseil Team - 27c2f6e2f3b5929fbd322b0f0ca392eb02efd9f8 Export of internal Abseil changes. by Abseil Team - aa468ad75539619b47979911297efbb629c52e44 Export of internal Abseil changes. by Abseil Team - cd86d0d20ab167c33b23d3875db68d1d4bad3a3b Export of internal Abseil changes. by Abseil Team - 33841c5c963aa9c3f096ef8e6c1e71624b941940 Export of internal Abseil changes. by Abseil Team - ca3f87560a0eef716195cadf66dc6b938a579ec6 Export of internal Abseil changes. by Abseil Team - d902eb869bcfacc1bad14933ed9af4bed006d481 Export of internal Abseil changes. by Abseil Team - a02f62f456f2c4a7ecf2be3104fe0c6e16fbad9a Export of internal Abseil changes. by Abseil Team - 0b545b460141b882b244a1efcef7621d59278160 Export of internal Abseil changes. by Abseil Team - dbae8764fbd429bf7d7745e24bcf73962177a7c0 Export of internal Abseil changes. by Abseil Team - 044da8a29c923506af0f0b46bc46f43c1e1300b5 Export of internal Abseil changes. by Abseil Team - 6cc6ac44e065b9e8975fadfd6ccb99cbcf89aac4 Export of internal Abseil changes. by Abseil Team - 666fc1266bccfd8e6eaaa084e7b42580bb8eb199 Export of internal Abseil changes. by Abseil Team - 93dfcf74cb5fccae3da07897d8613ae6cab958a0 Export of internal Abseil changes. by Abseil Team - 2c8421e1c6cef0da9e8a20b01c15256ec9ec116d Export of internal Abseil changes. by Abseil Team - 5b65c4af5107176555b23a638e5947686410ac1f Export of internal Abseil changes. by Abseil Team - eab2078b53c9e3d9d240135c09d27e3393acb50a Export of internal Abseil changes. by Abseil Team - 253eb7416421661873afbaa33828a850db978541 [CMake] Set correct flags for clang-cl (#278) by Loo Rong Jie - e75672f6afc7e8f23ee7b532e86d1b3b9be3984e Export of internal Abseil changes. by Abseil Team - bf29470384a101b307873b26d358433138c857fc Export of internal Abseil changes. by Abseil Team - 6fd827124facd8336981e73218997f9e73029b4f Merge pull request #280 from chiumichael/master by Derek Mauro <761129+derekmauro@users.noreply.github.com> - 7c7754fb3ed9ffb57d35fe8658f3ba4d73a31e72 Export of internal Abseil changes. by Abseil Team - 256be563447a315f2a7993ec669460ba475fa86a Export of internal Abseil changes. by Abseil Team - 88a152ae747c3c42dc9167d46c590929b048d436 Export of internal Abseil changes. by Abseil Team - c1cecb25a94c075725e9d2640f6b978a8f61957b Implement Span::first and Span::last from C++20 (#274) by Girts - 38b704384cd2f17590b3922b97744be0b43622c9 Changed HTTP URLs to HTTPS where possible (#270) by nik7273 - febc5ee6a92d0eb7dac1fceaa6c648cf6521b4dc Export of internal Abseil changes. by Abseil Team - 9fdf5e5b805412cb2a2e624d3e9a11588120465f Export of internal Abseil changes. by Abseil Team - 419f3184f8ebcdb23105295eadd2a569f3351eb9 Export of internal Abseil changes. by Abseil Team - b312c3cb53a0aad75a85ac2bf57c4a614fbd48d4 Export of internal Abseil changes. by Abseil Team - 308ce31528a7edfa39f5f6d36142278a0ae1bf45 Export of internal Abseil changes. by Abseil Team - 93d155bc4414f6c121bb1f19dba9fdb27c8943bc Export of internal Abseil changes. by Abseil Team - 426eaa4aa44e4580418bee46c1bd13911151bfb1 Export of internal Abseil changes. by Abseil Team - 2901ec32a919311384d6ad4194e2d927c06831f7 Export of internal Abseil changes. by Abseil Team - d78310fe5a82f2e0e6e16509ef8079c8d7e4674e Export of internal Abseil changes. by Abseil Team - a4cb1c8ba61531a63f9d309eea01ac1d43d8371d Export of internal Abseil changes. by Abseil Team - 540e2537b92cd4abfae6ceddfe24304345461f32 Export of internal Abseil changes. by Abseil Team - 89ea0c5ff34aaa5855cfc7aa41f323b8a0ef0ede Merge pull request #255 from uilianries/hotfix/conan by ahedberg - 5e0dcf72c64fae912184d2e0de87195fe8f0a425 Export of internal Abseil changes. by Abseil Team - 0dffca4e36791c7beeda04da10460b534283948a Export of internal Abseil changes. by Abseil Team - 6b4201f9ef650637510a21b8d6cbcc3bee4a606f Fix GCC8 warnings by Boris Staletic - 0b1e6d417b414aad9282e32e8c49c719edeb63c1 Export of internal Abseil changes. by Abseil Team - efccc502606bed768e50a6cd5806d8eb13e4e935 Export of internal Abseil changes. by Abseil Team - 5e6a78131f7bd5940218462c07d88cdefdd75dbe Export of internal Abseil changes. by Abseil Team - 5eea0f713c14ac17788b83e496f11903f8e2bbb0 Export of internal Abseil changes. by Abseil Team - 66f9becbb98ecc083f4db349b4b1e0ca9de93b15 Export of internal Abseil changes. by Abseil Team - 018b4db1d73ec8238e6dc4b17fd9e1fd7468d0ed Export of internal Abseil changes. by Abseil Team - 9449ae94397f2fd683851348e25ed8c93f75b3b9 Merge pull request #243 from ThomsonTan/FixIntrinsic by Alex Strelnikov - b16aeb6756bdab08cdf12d40baab5b51f7d15b16 Export of internal Abseil changes. by Abseil Team - 7ffbe09f3d85504bd018783bbe1e2c12992fe47c Export of internal Abseil changes. by Abseil Team - 01b471d9f3ebef27f5aaca14b66509099fa8cd6c Export of internal Abseil changes. by Abseil Team - 7bd8f36c741c7cbe311611d7981bf38ba04c6fef Export of internal Abseil changes. by Abseil Team - 968a34ffdaadd7db062a9621dfbdf8b2d16e05af Export of internal Abseil changes. by Abseil Team - 3e2e9b5557e76d098de4b8a2a659125b98ca519b Merge pull request #231 from uilianries/feature/conan by Mark Barolak - 111ca7060a6ff50115ca85b59f6b5d8c8c5e9105 Export of internal Abseil changes. by Abseil Team - 389ec3f906f018661a5308458d623d01f96d7b23 Export of internal Abseil changes. by Abseil Team - 8fbcdb90952c57828c4a9c2f6d79fcd7cae9088f Export of internal Abseil changes. by Abseil Team - 455dc17ba1af9635f0b60155bc565bc572a1e722 Export of internal Abseil changes. by Abseil Team - f197d7c72a54064cfde5a2058f1513a4a0ee36fb Export of internal Abseil changes. by Abseil Team - 284378a71b32dfb3af4e3661f585e671d1b603a3 Export of internal Abseil changes. by Abseil Team GitOrigin-RevId: 9ee91d3e430fb33a4590486573792eb0fa146c2d Change-Id: Ia06e548bc106cc9d136f6c65714be6645317aced --- absl/random/zipf_distribution_test.cc | 423 ++++++++++++++++++++++++++++++++++ 1 file changed, 423 insertions(+) create mode 100644 absl/random/zipf_distribution_test.cc (limited to 'absl/random/zipf_distribution_test.cc') diff --git a/absl/random/zipf_distribution_test.cc b/absl/random/zipf_distribution_test.cc new file mode 100644 index 00000000..4d4a0fcf --- /dev/null +++ b/absl/random/zipf_distribution_test.cc @@ -0,0 +1,423 @@ +// 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/zipf_distribution.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/random/internal/chi_square.h" +#include "absl/random/internal/sequence_urbg.h" +#include "absl/random/random.h" +#include "absl/strings/str_cat.h" +#include "absl/strings/str_replace.h" +#include "absl/strings/strip.h" + +namespace { + +using ::absl::random_internal::kChiSquared; +using ::testing::ElementsAre; + +template +class ZipfDistributionTypedTest : public ::testing::Test {}; + +using IntTypes = ::testing::Types; +TYPED_TEST_CASE(ZipfDistributionTypedTest, IntTypes); + +TYPED_TEST(ZipfDistributionTypedTest, SerializeTest) { + using param_type = typename absl::zipf_distribution::param_type; + + constexpr int kCount = 1000; + absl::InsecureBitGen gen; + for (const auto& param : { + param_type(), + param_type(32), + param_type(100, 3, 2), + param_type(std::numeric_limits::max(), 4, 3), + param_type(std::numeric_limits::max() / 2), + }) { + // Validate parameters. + const auto k = param.k(); + const auto q = param.q(); + const auto v = param.v(); + + absl::zipf_distribution before(k, q, v); + EXPECT_EQ(before.k(), param.k()); + EXPECT_EQ(before.q(), param.q()); + EXPECT_EQ(before.v(), param.v()); + + { + absl::zipf_distribution via_param(param); + EXPECT_EQ(via_param, before); + } + + // Validate stream serialization. + std::stringstream ss; + ss << before; + absl::zipf_distribution after(4, 5.5, 4.4); + + EXPECT_NE(before.k(), after.k()); + EXPECT_NE(before.q(), after.q()); + EXPECT_NE(before.v(), after.v()); + EXPECT_NE(before.param(), after.param()); + EXPECT_NE(before, after); + + ss >> after; + + EXPECT_EQ(before.k(), after.k()); + EXPECT_EQ(before.q(), after.q()); + EXPECT_EQ(before.v(), after.v()); + EXPECT_EQ(before.param(), after.param()); + EXPECT_EQ(before, after); + + // Smoke test. + auto sample_min = after.max(); + auto sample_max = after.min(); + for (int i = 0; i < kCount; i++) { + auto sample = after(gen); + EXPECT_GE(sample, after.min()); + EXPECT_LE(sample, after.max()); + if (sample > sample_max) sample_max = sample; + if (sample < sample_min) sample_min = sample; + } + ABSL_INTERNAL_LOG(INFO, + absl::StrCat("Range: ", +sample_min, ", ", +sample_max)); + } +} + +class ZipfModel { + public: + ZipfModel(size_t k, double q, double v) : k_(k), q_(q), v_(v) {} + + double mean() const { return mean_; } + + // For the other moments of the Zipf distribution, see, for example, + // http://mathworld.wolfram.com/ZipfDistribution.html + + // PMF(k) = (1 / k^s) / H(N,s) + // Returns the probability that any single invocation returns k. + double PMF(size_t i) { return i >= hnq_.size() ? 0.0 : hnq_[i] / sum_hnq_; } + + // CDF = H(k, s) / H(N,s) + double CDF(size_t i) { + if (i >= hnq_.size()) { + return 1.0; + } + auto it = std::begin(hnq_); + double h = 0.0; + for (const auto end = it; it != end; it++) { + h += *it; + } + return h / sum_hnq_; + } + + // The InverseCDF returns the k values which bound p on the upper and lower + // bound. Since there is no closed-form solution, this is implemented as a + // bisction of the cdf. + std::pair InverseCDF(double p) { + size_t min = 0; + size_t max = hnq_.size(); + while (max > min + 1) { + size_t target = (max + min) >> 1; + double x = CDF(target); + if (x > p) { + max = target; + } else { + min = target; + } + } + return {min, max}; + } + + // Compute the probability totals, which are based on the generalized harmonic + // number, H(N,s). + // H(N,s) == SUM(k=1..N, 1 / k^s) + // + // In the limit, H(N,s) == zetac(s) + 1. + // + // NOTE: The mean of a zipf distribution could be computed here as well. + // Mean := H(N, s-1) / H(N,s). + // Given the parameter v = 1, this gives the following function: + // (Hn(100, 1) - Hn(1,1)) / (Hn(100,2) - Hn(1,2)) = 6.5944 + // + void Init() { + if (!hnq_.empty()) { + return; + } + hnq_.clear(); + hnq_.reserve(std::min(k_, size_t{1000})); + + sum_hnq_ = 0; + double qm1 = q_ - 1.0; + double sum_hnq_m1 = 0; + for (size_t i = 0; i < k_; i++) { + // Partial n-th generalized harmonic number + const double x = v_ + i; + + // H(n, q-1) + const double hnqm1 = + (q_ == 2.0) ? (1.0 / x) + : (q_ == 3.0) ? (1.0 / (x * x)) : std::pow(x, -qm1); + sum_hnq_m1 += hnqm1; + + // H(n, q) + const double hnq = + (q_ == 2.0) ? (1.0 / (x * x)) + : (q_ == 3.0) ? (1.0 / (x * x * x)) : std::pow(x, -q_); + sum_hnq_ += hnq; + hnq_.push_back(hnq); + if (i > 1000 && hnq <= 1e-10) { + // The harmonic number is too small. + break; + } + } + assert(sum_hnq_ > 0); + mean_ = sum_hnq_m1 / sum_hnq_; + } + + private: + const size_t k_; + const double q_; + const double v_; + + double mean_; + std::vector hnq_; + double sum_hnq_; +}; + +using zipf_u64 = absl::zipf_distribution; + +class ZipfTest : public testing::TestWithParam, + public ZipfModel { + public: + ZipfTest() : ZipfModel(GetParam().k(), GetParam().q(), GetParam().v()) {} + + absl::InsecureBitGen rng_; +}; + +TEST_P(ZipfTest, ChiSquaredTest) { + const auto& param = GetParam(); + Init(); + + size_t trials = 10000; + + // Find the split-points for the buckets. + std::vector points; + std::vector expected; + { + double last_cdf = 0.0; + double min_p = 1.0; + for (double p = 0.01; p < 1.0; p += 0.01) { + auto x = InverseCDF(p); + if (points.empty() || points.back() < x.second) { + const double p = CDF(x.second); + points.push_back(x.second); + double q = p - last_cdf; + expected.push_back(q); + last_cdf = p; + if (q < min_p) { + min_p = q; + } + } + } + if (last_cdf < 0.999) { + points.push_back(std::numeric_limits::max()); + double q = 1.0 - last_cdf; + expected.push_back(q); + if (q < min_p) { + min_p = q; + } + } else { + points.back() = std::numeric_limits::max(); + expected.back() += (1.0 - last_cdf); + } + // The Chi-Squared score is not completely scale-invariant; it works best + // when the small values are in the small digits. + trials = static_cast(8.0 / min_p); + } + ASSERT_GT(points.size(), 0); + + // Generate n variates and fill the counts vector with the count of their + // occurrences. + std::vector buckets(points.size(), 0); + double avg = 0; + { + zipf_u64 dis(param); + for (size_t i = 0; i < trials; i++) { + uint64_t x = dis(rng_); + ASSERT_LE(x, dis.max()); + ASSERT_GE(x, dis.min()); + avg += static_cast(x); + auto it = std::upper_bound(std::begin(points), std::end(points), + static_cast(x)); + buckets[std::distance(std::begin(points), it)]++; + } + avg = avg / static_cast(trials); + } + + // Validate the output using the Chi-Squared test. + for (auto& e : expected) { + e *= trials; + } + + // The null-hypothesis is that the distribution is a poisson distribution with + // the provided mean (not estimated from the data). + const int dof = static_cast(expected.size()) - 1; + + // NOTE: This test runs about 15x per invocation, so a value of 0.9995 is + // approximately correct for a test suite failure rate of 1 in 100. In + // practice we see failures slightly higher than that. + const double threshold = absl::random_internal::ChiSquareValue(dof, 0.9999); + + const double chi_square = absl::random_internal::ChiSquare( + std::begin(buckets), std::end(buckets), std::begin(expected), + std::end(expected)); + + const double p_actual = + absl::random_internal::ChiSquarePValue(chi_square, dof); + + // Log if the chi_squared value is above the threshold. + if (chi_square > threshold) { + ABSL_INTERNAL_LOG(INFO, "values"); + for (size_t i = 0; i < expected.size(); i++) { + ABSL_INTERNAL_LOG(INFO, absl::StrCat(points[i], ": ", buckets[i], + " vs. E=", expected[i])); + } + ABSL_INTERNAL_LOG(INFO, absl::StrCat("trials ", trials)); + ABSL_INTERNAL_LOG(INFO, + absl::StrCat("mean ", avg, " vs. expected ", mean())); + ABSL_INTERNAL_LOG(INFO, absl::StrCat(kChiSquared, "(data, ", dof, ") = ", + chi_square, " (", p_actual, ")")); + ABSL_INTERNAL_LOG(INFO, + absl::StrCat(kChiSquared, " @ 0.9995 = ", threshold)); + FAIL() << kChiSquared << " value of " << chi_square + << " is above the threshold."; + } +} + +std::vector GenParams() { + using param = zipf_u64::param_type; + const auto k = param().k(); + const auto q = param().q(); + const auto v = param().v(); + const uint64_t k2 = 1 << 10; + return std::vector{ + // Default + param(k, q, v), + // vary K + param(4, q, v), param(1 << 4, q, v), param(k2, q, v), + // vary V + param(k2, q, 0.5), param(k2, q, 1.5), param(k2, q, 2.5), param(k2, q, 10), + // vary Q + param(k2, 1.5, v), param(k2, 3, v), param(k2, 5, v), param(k2, 10, v), + // Vary V & Q + param(k2, 1.5, 0.5), param(k2, 3, 1.5), param(k, 10, 10)}; +} + +std::string ParamName( + const ::testing::TestParamInfo& info) { + const auto& p = info.param; + std::string name = absl::StrCat("k_", p.k(), "__q_", absl::SixDigits(p.q()), + "__v_", absl::SixDigits(p.v())); + return absl::StrReplaceAll(name, {{"+", "_"}, {"-", "_"}, {".", "_"}}); +} + +INSTANTIATE_TEST_SUITE_P(All, ZipfTest, ::testing::ValuesIn(GenParams()), + ParamName); + +// NOTE: absl::zipf_distribution is not guaranteed to be stable. +TEST(ZipfDistributionTest, StabilityTest) { + // absl::zipf_distribution stability relies on + // absl::uniform_real_distribution, std::log, std::exp, std::log1p + absl::random_internal::sequence_urbg urbg( + {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull, + 0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, + 0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull, + 0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull}); + + std::vector output(10); + + { + absl::zipf_distribution dist; + std::generate(std::begin(output), std::end(output), + [&] { return dist(urbg); }); + EXPECT_THAT(output, ElementsAre(10031, 0, 0, 3, 6, 0, 7, 47, 0, 0)); + } + urbg.reset(); + { + absl::zipf_distribution dist(std::numeric_limits::max(), + 3.3); + std::generate(std::begin(output), std::end(output), + [&] { return dist(urbg); }); + EXPECT_THAT(output, ElementsAre(44, 0, 0, 0, 0, 1, 0, 1, 3, 0)); + } +} + +TEST(ZipfDistributionTest, AlgorithmBounds) { + absl::zipf_distribution dist; + + // Small values from absl::uniform_real_distribution map to larger Zipf + // distribution values. + const std::pair kInputs[] = { + {0xffffffffffffffff, 0x0}, {0x7fffffffffffffff, 0x0}, + {0x3ffffffffffffffb, 0x1}, {0x1ffffffffffffffd, 0x4}, + {0xffffffffffffffe, 0x9}, {0x7ffffffffffffff, 0x12}, + {0x3ffffffffffffff, 0x25}, {0x1ffffffffffffff, 0x4c}, + {0xffffffffffffff, 0x99}, {0x7fffffffffffff, 0x132}, + {0x3fffffffffffff, 0x265}, {0x1fffffffffffff, 0x4cc}, + {0xfffffffffffff, 0x999}, {0x7ffffffffffff, 0x1332}, + {0x3ffffffffffff, 0x2665}, {0x1ffffffffffff, 0x4ccc}, + {0xffffffffffff, 0x9998}, {0x7fffffffffff, 0x1332f}, + {0x3fffffffffff, 0x2665a}, {0x1fffffffffff, 0x4cc9e}, + {0xfffffffffff, 0x998e0}, {0x7ffffffffff, 0x133051}, + {0x3ffffffffff, 0x265ae4}, {0x1ffffffffff, 0x4c9ed3}, + {0xffffffffff, 0x98e223}, {0x7fffffffff, 0x13058c4}, + {0x3fffffffff, 0x25b178e}, {0x1fffffffff, 0x4a062b2}, + {0xfffffffff, 0x8ee23b8}, {0x7ffffffff, 0x10b21642}, + {0x3ffffffff, 0x1d89d89d}, {0x1ffffffff, 0x2fffffff}, + {0xffffffff, 0x45d1745d}, {0x7fffffff, 0x5a5a5a5a}, + {0x3fffffff, 0x69ee5846}, {0x1fffffff, 0x73ecade3}, + {0xfffffff, 0x79a9d260}, {0x7ffffff, 0x7cc0532b}, + {0x3ffffff, 0x7e5ad146}, {0x1ffffff, 0x7f2c0bec}, + {0xffffff, 0x7f95adef}, {0x7fffff, 0x7fcac0da}, + {0x3fffff, 0x7fe55ae2}, {0x1fffff, 0x7ff2ac0e}, + {0xfffff, 0x7ff955ae}, {0x7ffff, 0x7ffcaac1}, + {0x3ffff, 0x7ffe555b}, {0x1ffff, 0x7fff2aac}, + {0xffff, 0x7fff9556}, {0x7fff, 0x7fffcaab}, + {0x3fff, 0x7fffe555}, {0x1fff, 0x7ffff2ab}, + {0xfff, 0x7ffff955}, {0x7ff, 0x7ffffcab}, + {0x3ff, 0x7ffffe55}, {0x1ff, 0x7fffff2b}, + {0xff, 0x7fffff95}, {0x7f, 0x7fffffcb}, + {0x3f, 0x7fffffe5}, {0x1f, 0x7ffffff3}, + {0xf, 0x7ffffff9}, {0x7, 0x7ffffffd}, + {0x3, 0x7ffffffe}, {0x1, 0x7fffffff}, + }; + + for (const auto& instance : kInputs) { + absl::random_internal::sequence_urbg urbg({instance.first}); + EXPECT_EQ(instance.second, dist(urbg)); + } +} + +} // namespace -- cgit v1.2.3