从范围生成随机整数

Question

我需要一个能在给定范围内生成随机整数的函数(包括边界值).我没有不合理的质量/随机性要求,我有四个要求:

• 我需要快速.我的项目需要产生数百万(有时甚至数千万)的随机数,而我当前的发电机功能已被证明是一个瓶颈.
• 我需要它合理均匀(使用rand()非常好).
• min-max范围可以是<0,1>到<-32727,32727>.
• 它必须是可播种的.

我目前有以下C++代码:

output = min + (rand() * (int)(max - min) / RAND_MAX)

问题是,它并不是真正统一的 - 只有当rand()= RAND_MAX时才返回max(对于Visual C++,它是1/32727).这是小范围的主要问题,如<-1,1>,其中最后一个值几乎从不返回.

所以我抓住笔和纸,并提出了以下公式(它建立在(int)(n + 0.5)整数舍入技巧):

但它仍然没有给我统一的分配.对于值-1,0,0,重复运行10000个样本给出37:50:13的比率.

你能建议更好的配方吗？(甚至整个伪随机数发生器功能)

Answer 1

最简单(也就是最好的)C++(使用2011标准)的答案是

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

无需重新发明轮子.无需担心偏见.无需担心使用时间作为随机种子.

Answer 2

一个快,比你的好一点,但仍然没有适当的统一分布式解决方案

output = min + (rand() % static_cast<int>(max - min + 1))

除非范围的大小是2的幂,否则该方法产生偏差的非均匀分布数,而不管其质量如何rand().有关此方法质量的全面测试,请阅读此内容.

Answer 3

如果您的编译器支持C++ 0x并且使用它是一个选项,那么新标准<random>头可能会满足您的需求.它具有高质量uniform_int_distribution,可以接受最小和最大边界(包括你需要的),你可以选择各种随机数发生器插入该发行版.

这是int在[-57,365] 中生成一百万随机s均匀分布的代码.我已经使用了新的标准<chrono>设施来计时,因为你提到性能是你的一个主要问题.

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

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
    return c;
}

对我来说(2.8 GHz Intel Core i5)打印出:

每秒2.10268e + 07个随机数.

您可以通过将int传递给其构造函数来为生成器设定种子:

    G g(seed);

如果后来发现int不包括您需要为您分配的范围内,这可以通过改变来弥补uniform_int_distribution,像这样(如到long long):

    typedef std::uniform_int_distribution<long long> D;

如果你后来发现它minstd_rand不是一个足够高质量的发生器,那么它也很容易被换掉.例如:

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

对随机数生成器进行单独控制,随机分布可以非常自由.

我还计算(未显示)此分布的前4个"时刻"(使用minstd_rand),并将它们与理论值进行比较,以尝试量化分布的质量:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

(x_前缀指"预期")

Answer 4

我们将问题分成两部分:

• 生成n0到(max-min)范围内的随机数.
• 将min添加到该数字

第一部分显然是最难的.我们假设rand()的返回值是完全一致的.使用modulo会增加第一个(RAND_MAX + 1) % (max-min+1)数字的偏差.所以,如果我们能幻化RAND_MAX到RAND_MAX - (RAND_MAX + 1) % (max-min+1),也将不再是任何偏见.

事实证明,如果我们愿意允许伪非确定性进入算法的运行时间,我们就可以使用这种直觉.每当rand()返回一个太大的数字时,我们只需要另一个随机数,直到我们得到一个足够小的数字.

运行时间现在是几何分布的,具有预期值1/p,其中p是在第一次尝试时获得足够小数量的概率.由于RAND_MAX - (RAND_MAX + 1) % (max-min+1)总是小于(RAND_MAX + 1) / 2,我们知道p > 1/2,因此对于任何范围,预期的迭代次数总是小于2.使用这种技术,在标准CPU上应该可以在不到一秒的时间内生成数千万个随机数.

编辑:

虽然上述技术上是正确的,但DSimon的答案在实践中可能更有用.你不应该自己实现这些东西.我已经看到很多拒绝采样的实现,通常很难看出它是否正确.

Answer 5

如何在梅森难题？boost实现非常易于使用,并且在许多实际应用程序中经过了充分测试.我自己在几个学术项目中使用它,如人工智能和进化算法.

这是他们的例子,他们做了一个简单的功能来滚动六面模具:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

哦,这里有一些更多拉皮条的发生器,以防万一你不相信你应该使用它超过劣势rand():

Mersenne Twister是Makoto Matsumoto和Takuji Nishimura发明的"随机数"发生器; 他们的网站包括许多算法实现.

从本质上讲,Mersenne Twister是一个非常大的线性反馈移位寄存器.该算法在19,937位种子上运行,存储在32位无符号整数的624元素阵列中.值2 ^ 19937-1是梅森素数; 操纵种子的技术基于较旧的"扭曲"算法 - 因此称为"Mersenne Twister".

Mersenne Twister的一个吸引人的方面是它使用二进制运算 - 而不是耗时的乘法 - 来生成数字.该算法还具有很长的周期和良好的粒度.它对于非加密应用程序既快速又有效.

Answer 6

int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}

这是32768个整数到(nMax-nMin + 1)整数的映射.如果(nMax-nMin + 1)很小(如您的要求),映射将非常好.但请注意,如果(nMax-nMin + 1)很大,则映射将不起作用(例如 - 您无法以相同的概率将32768值映射到30000个值).如果需要这样的范围 - 您应该使用32位或64位随机源,而不是15位rand(),或忽略超出范围的rand()结果.

Answer 7

假设 min 和 max 是 int 值，[ 和 ] 表示包括这个值，( 和 ) 表示不包括这个值，使用上面的使用 c++ rand() 获得正确的值

参考：for()[]定义，访问：

https://en.wikipedia.org/wiki/Interval_(数学)

对于 rand 和 srand 函数或 RAND_MAX 定义，请访问：

http://en.cppreference.com/w/cpp/numeric/random/rand

[最小，最大]

int randNum = rand() % (max - min + 1) + min

（最小，最大]

int randNum = rand() % (max - min) + min + 1

[最小，最大)

int randNum = rand() % (max - min) + min

（最小，最大）

int randNum = rand() % (max - min - 1) + min + 1

Answer 8

这是一个无偏版本，可生成 中的数字[low, high]：

int r;
do {
  r = rand();
} while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;

如果您的范围相当小，则没有理由在循环中缓存比较的右侧do。