1

在比较bernoulli_distributions 的默认构造函数（真/假的可能性为 50/50）和uniform_int_distribution{0, 1}（0 或 1 的均匀可能性）时，我发现bernoulli_distributions 的速度至少比它们慢2 倍和 6 倍以上，uniform_int_distribution尽管它们给出了相同的结果。

我希望bernoulii_distribition表现更好，因为它是专门为只有两种结果（真或假）的概率而设计的；然而，事实并非如此。

鉴于上述和以下的性能指标，伯努利分布在 uniform_int_distributions 上是否有实际用途？

超过 5 次运行的结果（发布模式，x64 位）：（请参阅下面的编辑以了解未附加调试器的发布运行）

bernoulli: 58 ms
false: 500690
true: 499310

uniform: 9 ms
1: 499710
0: 500290
----------
bernoulli: 57 ms
false: 500921
true: 499079

uniform: 9 ms
0: 499614
1: 500386
----------
bernoulli: 61 ms
false: 500440
true: 499560

uniform: 9 ms
0: 499575
1: 500425
----------
bernoulli: 59 ms
true: 498798
false: 501202

uniform: 9 ms
1: 499485
0: 500515
----------
bernoulli: 58 ms
true: 500777
false: 499223

uniform: 9 ms
0: 500450
1: 499550
----------

分析代码：

#include <chrono>
#include <random>
#include <iostream>
#include <unordered_map>

int main() {

    auto gb = std::mt19937{std::random_device{}()};
    auto bd = std::bernoulli_distribution{};
    auto bhist = std::unordered_map<bool, int>{};

    auto start = std::chrono::steady_clock::now();
    for(int i = 0; i < 1'000'000; ++i) {
        bhist[bd(gb)]++;
    }
    auto end = std::chrono::steady_clock::now();
    auto dif = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    std::cout << "bernoulli: " << dif.count() << " ms\n";
    std::cout << std::boolalpha;
    for(auto& b : bhist) {
        std::cout << b.first << ": " << b.second << '\n';
    }
    std::cout << std::noboolalpha;
    std::cout << '\n';

    auto gu = std::mt19937{std::random_device{}()};
    auto u = std::uniform_int_distribution<int>{0, 1};
    auto uhist = std::unordered_map<int, int>{};

    start = std::chrono::steady_clock::now();
    for(int i = 0; i < 1'000'000; ++i) {
        uhist[u(gu)]++;
    }
    end = std::chrono::steady_clock::now();
    dif = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    std::cout << "uniform: " << dif.count() << " ms\n";
    for(auto& b : uhist) {
        std::cout << b.first << ": " << b.second << '\n';
    }
    std::cout << '\n';
}

编辑

我在没有附加调试符号的情况下重新运行了测试，但 bernoulli 的运行速度仍然慢了 4 倍：

bernoulli: 37 ms
false: 500250
true: 499750

uniform: 9 ms
0: 500433
1: 499567
-----
bernoulli: 36 ms
false: 500595
true: 499405

uniform: 9 ms
0: 499061
1: 500939
-----
bernoulli: 36 ms
false: 500988
true: 499012

uniform: 8 ms
0: 499596
1: 500404
-----
bernoulli: 36 ms
true: 500425
false: 499575

uniform: 8 ms
0: 499974
1: 500026
-----
bernoulli: 36 ms
false: 500847
true: 499153

uniform: 8 ms
0: 500082
1: 499918
-----
4

3 回答 3

2

构造的默认值std::bernoulli_distribution对两种结果赋予相同的权重，但您可以为其赋予不同的分布参数以更改概率。这可能会导致额外的复杂性。更好的比较是使用 astd::uniform_real_distribution<double>并将其结果与 0.5 进行比较（默认情况下，它会给出 range 中的随机数[0, 1)）。

请参阅此处的示例：

gcc 输出：

bernoulli: 28 ms
false: 499818
true: 500182

uniform: 31 ms
1: 500686
0: 499314

real: 29 ms
1: 500191
0: 499809

铿锵输出：

bernoulli: 106 ms
false: 500662
true: 499338

uniform: 23 ms
1: 501263
0: 498737

real: 101 ms
1: 499683
0: 500317

使用 gcc 的结果大致相同（与您看到的相反，多次运行往往会使统一的 int 时间更长）。使用 clang 我得到 bernoulli 和 real 大致相同，统一的 int 时间要少得多。这两个都在使用-O3.

于 2021-04-14T19:54:06.927 回答
1

该类bernoulli_distribution用于生成具有可能不均匀比率的布尔值。为了实现这一点，它必须在 [0,1] 范围内生成一个浮点，然后将其与给定的概率进行比较。或任何等效的东西。

很明显，此例程可能比取模 2 的随机整数要慢 - 这几乎是{0,1}从随机数创建统一数所需的全部内容。

怎么惊喜？只有编译器以某种方式设法找出不必要的操作，同时在编译过程中意识到它是 50/50，性能才能达到平均水平。

于 2021-04-14T19:52:43.050 回答
0

一些评论和答案建议uniform_real_distribution改用。

我测试uniform_real_distribution(0.0f, nextafter(1.0f, 20.f))了（考虑到urd一个半封闭的范围）vs bernoulli_distribution，bernoulli_distribution无论概率如何，它都快了大约 20%-25%（并给出了更正确的结果。我测试了1.0真实概率和我使用上述urd值的实现实际上给出了假阴性（在 5 次 100 万次运行中获得一到两次）并且bernoulli没有给出正确的结果。

因此，速度方面：bernoulli_distribution比 快uniform_real_distribution但比 慢uniform_int_distribution。

长话短说，为工作使用正确的工具，不要重新发明轮子，STL 构建良好，等等，根据用例，一个比另一个更好。

对于是-否概率 ( IsPercentChance(float probability))，bernoulli_distribution更快更好。

对于纯粹的“给我一个随机的随机布尔值”，uniform_int_distribution更快更好。

于 2021-04-16T02:26:13.990 回答