uniform_int_distribution 范围为零进入无限循环

Question

对于单元测试，我实现了一个模拟随机数生成器。我相信这是 UniformBitGenerator 的有效实现（模拟实际上使用 google 模拟来设置 operator() 的 return，但它的行为相同）。

struct RNG
{
    using result_type = size_t;
    static result_type min() { return 0; }
    static result_type max() { return std::numeric_limits<result_type>::max(); }
    result_type operator()() { return max(); }
};

现在我使用这个模拟从 std::uniform_int_distribution 的范围 [a, b], a == b 中采样。我相信这是允许的，我发现 here 对分布参数的唯一限制是 b >= a。所以我希望下面的程序打印 5.

int main()
{
    auto rng = RNG();
    auto dist = std::uniform_int_distribution<>(5, 5);
    printf("%d\n", dist(rng));
    return 0;
}

相反，它进入了 STL 内部的无限循环，反复从生成器中提取数字，但未能找到指定范围内的数字。我测试了不同版本的不同（当前）编译器（包括 clang、gcc、icc）。 RNG::max 也可以 return 其他值（例如 42），不会改变任何东西。

我正在测试的真实代码将随机索引绘制到一个可能只包含一个元素的容器中。检查这种情况很容易，但这种情况很少见，我想避免这种情况。

我是否遗漏了 STL 中 RNG 规范中的某些内容？我会惊讶地发现所有编译器中的错误...

Answer 1

标准说 ([rand.dist.uni.int]):

A uniform_int_distribution random number distribution produces random integers i, a ≤ i ≤ b, distributed according to the constant discrete probability function

P(i|a,b)=1/(b−a+1)

. . .

explicit uniform_int_distribution(IntType a = 0, IntType b = numeric_limits<IntType>::max());

Requires: a ≤ b.

所以 uniform_int_distribution<>(5,5) 应该 return 5 的概率为 1/1。

进入无限循环的实现有一个错误。

但是，您始终生成相同值的模拟 RNG 不满足 Uniform random bit generator requirements:

A uniform random bit generator g of type G is a function object returning unsigned integer values such that each value in the range of possible results has (ideally) equal probability of being returned. [ Note: The degree to which g's results approximate the ideal is often determined statistically. — end note ]

参见[req.genl]/p1.b:

Throughout this subclause [rand], the effect of instantiating a template:

b) that has a template type parameter named URBG is undefined unless the corresponding template argument is cv-unqualified and satisfies the requirements of uniform random bit generator.

果然，用标准的RNG吧just works:

#include <iostream>
#include <random>

int main() {
    std::mt19937_64 rng;
    std::uniform_int_distribution<> dist(5, 5);
    std::cout << dist(rng) << "\n";
}

打印：

Answer 2

拒绝抽样通常可以实现均匀分布。您不断请求随机数，直到获得符合条件的随机数。你设置了一个不能满足条件的情况，因为你的随机数生成器非常non-random，所以导致死循环

uniform_int_distribution 范围为零进入无限循环

uniform_int_distribution with zero range goes to infinite loop

c++

random

std

language-lawyer