范围为零的uniform_int_distribution进入无限循环



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

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(); }
};

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

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

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

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

我是不是在STL中的RNG规范中遗漏了什么?如果在所有编译器中发现一个错误,我会很惊讶。。。

通常通过拒绝采样来实现均匀分布。你一直在请求随机数字,直到你得到一个符合标准的数字。你已经设置了一个无法满足标准的情况,因为你的随机数生成器是非常非随机的,所以它会导致无限循环。

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

CCD_ 7随机数分布产生随机整数ia≤i≤b,根据常数离散概率函数分布

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

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

需要:a ≤ b

所以uniform_int_distribution<>(5,5)应该以1/1的概率返回5

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

然而,您的模拟RNG总是生成相同的值,不满足统一随机位生成器的要求:

类型为g的统一随机位生成器g是返回无符号整数值的函数对象,使得可能结果范围内的每个值(理想情况下(返回的概率相等[注:g的结果接近理想的程度通常是通过统计确定的。--尾注]

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

在整个子条款[rand]中,实例化模板的效果:

b( 具有名为URBG的模板类型参数的是未定义的,除非相应的模板参数是cv不合格的并且满足统一随机位生成器的要求。

当然,有了标准RNG,它就可以工作了:

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

打印:

5

最新更新