从范围生成随机整数

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

  • 我需要它快速。 我的项目需要生成数百万(甚至有时甚至数千万)的随机数,而我目前的生成器function已经被certificate是一个瓶颈。
  • 我需要它是相当统一的(使用rand()是完美的)。
  • 最小 – 最大范围可以是从<0,1>到<-32727,32727>之间的任何值。
  • 它必须是可以种植的。

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

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

问题是,它不是一致的 – 只有当rand()= RAND_MAX(对于Visual C ++,它是1/32727),才返回max。 对于像<-1,1>这样的小范围来说,这是最后一个值几乎从不返回的主要问题。

于是我抓起笔和纸,拿出下面的公式(它是build立在(int)(n + 0.5)整数舍入技巧上的):

在这里输入图像描述

但它仍然没有给我统一的分配。 用10000个样品重复运行,给出比值为37:50:13,值为-1,0.1。

你能否build议更好的配方? (甚至是整个伪随机数发生器的function)

快一点,比你的好一点,但是分布式解决scheme还不够好

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

除了范围的大小是2的幂, 这种方法不piperand()的质量如何都会产生有偏差的不均匀分布的数字 。 对于这种方法的质量的全面testing,请阅读 。

最简单的(因此是最好的)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); 

不需要重新发明轮子。 没有必要担心偏见。 无需担心使用时间作为随机种子。

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

这里是生成一百万个随机int的代码,均匀分布在[-57,365]。 我已经使用了新的std <chrono>设施来logging时间,因为你提到的是性能是你最关心的一个问题。

 #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的英特尔酷睿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_前缀是指“预期的”)

我们将问题分成两部分:

  • 在0到(max-min)范围内生成一个随机数n
  • 添加分钟到该号码

第一部分显然是最难的。 假设rand()的返回值是完全一致的。 使用模数会给第一个(RAND_MAX + 1) % (max-min+1)数字增加偏差。 所以如果我们可以奇迹般地把RAND_MAX变成RAND_MAX - (RAND_MAX + 1) % (max-min+1) ,就不会有任何偏差。

事实certificate,如果我们愿意让伪非确定性进入我们algorithm的运行时间,我们可以使用这种直觉。 每当rand()返回一个太大的数字,我们只要求另一个随机数,直到得到一个足够小的数。

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

编辑:

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

怎么样梅森扭转者 ? boost实现相当容易使用,并且在许多真实世界的应用程序中都经过了很好的testing。 我自己在几个学术项目中使用它,例如人工智能和演化algorithm。

这里是他们的例子,他们做一个简单的function,滚动一个六面骰子:

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

哦,这里是更多的这个发生器的pimping,以防万一你不相信你应该使用它在极其低劣的rand()

Mersenne Twister是由松本诚和西村拓二发明的“随机数”发生器; 他们的网站包含了该algorithm的许多实现。

实质上,Mersenne Twister是一个非常大的线性反馈移位寄存器。 该algorithm在一个19,937位的种子上运行,存储在一个由32位无符号整数组成的624个元素的数组中。 价值2 ^ 19937-1是一个梅森素数; 操纵种子的技术是基于一个较老的“扭曲”algorithm – 因此被称为“梅森扭转者”。

Mersenne Twister的一个吸引人的方面是使用二进制运算 – 而不是耗时的乘法 – 来产生数字。 该algorithm还具有很长的周期,且粒度较好。 对于非encryption应用程序来说,它既快速又有效。

 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()结果。

这是一个无偏的版本,可以生成[low, high]

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

如果你的范围相当小,没有理由在do循环中caching比较的右边。

我推荐Boost.Random库 ,它是超级详细和有据可查的,可以让你明确地指定你想要的发行版本,而在非encryption场景中,实际上可以超越典型的C库rand实现。

如果我没有弄错,下面的expression应该是没有偏见的:

 std::floor( ( max - min + 1.0 ) * rand() ) + min; 

我在这里假定rand()给出了一个在0.0到1.0之间的随机值,不包括1.0,max和min是满足条件min <max的整数。

这个公式很简单,所以试试这个expression式,

  int num = (int) rand() * (max - min) + min; //Where rand() returns a random number between 0.0 and 1.0