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


我需要它要快。我的项目需要生成数百万(有时甚至是数千万)的随机数,而我的当前生成器函数已被证明是瓶颈。
我需要它具有合理的统一性(使用rand()完全可以) 。
最小-最大范围可以是<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)整数舍入技巧):



但是它仍然不能使我均匀分布。重复运行10000个样本,得出值-1、0的比率为37:50:13。1.

请您提出更好的公式吗? (甚至整个伪随机数生成器函数)

评论

请参阅:stackoverflow.com/questions/2254498/…

@比尔·马格里夫:是的。它有同样的问题。一个简化的版本是:如何在三个孩子之间平均分配10块糖果(不破坏任何糖果)?答案是,您不能-您必须给每个孩子三个,而不要给任何一个孩子第十个。

您看过Boost.Random吗?

查看Andrew Koenig的文章“几乎无法正确解决的简单问题”:drdobbs.com/blog/archives/2010/11/a_simple_proble.html

@Gene Bushuyev:我和安德鲁都已经在这个问题上思考了很长时间了。请参阅:groups.google.com/group/comp.lang.c++/browse_frm/thread/…,和:groups.google.com/group/comp.os.ms-windows.programmer.tools.mfc/…

#1 楼

一种快速的解决方案,比您的解决方案要好一些,但仍然不能提供统一的分布式解决方案。
output = min + (rand() % static_cast<int>(max - min + 1))


除非范围的大小是2的幂,否则此方法会产生偏差非均匀分布的数字,与rand()的质量无关。有关此方法质量的全面测试,请阅读此内容。

评论


谢谢,从快速测试中看来,这对我来说已经足够了--1、0、1的分布接近33:33:33。

–MatějZábský
2011-2-15在20:23

它总是返回最大值。我在这里想念什么吗? :|

– rohan-patel
2013年9月6日在2:18

rand()在C ++中应该被认为是有害的,有很多更好的方法来获取均匀分布并且实际上是随机的东西。

– Mgetz
2013年9月12日19:14在

它真的会在100%的时间内返回正确的数字吗?我在这里找到了其他一些stackoverflow答案,这些答案使用递归来“正确地进行”:stackoverflow.com/a/6852396/623622

– Czarek Tomczak
2014年1月25日上午11:07

因为这是一个非常令人讨厌的答案(对于期望而言),对于许多新读者来说,这似乎是可靠的信息来源,所以我认为提及此解决方案的质量和潜在危险非常重要,因此我进行了编辑。

–plasmacel
17年5月29日在22:39



#2 楼

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


无需重新发明轮子。无需担心偏见。无需担心将时间用作随机种子。

评论


如今,这应该是答案。有关更多功能的伪随机数生成参考。

– alextoind
15年9月28日在15:11

我同意“最简单”(也是最惯用的),而不是“最好”。不幸的是,标准没有对random_device作出任何保证,在某些情况下可能会完全破坏它。此外,mt19937虽然是一个很好的通用选择,但并不是高质量发生器中最快的(请参见此比较),因此可能不是OP的理想选择。

– Alberto M
2015年12月16日14:13



@AlbertoM不幸的是,您所指的比较没有提供足够的细节,并且无法再现,因此令人怀疑(此外,它是从2015年开始,而我的回答可以追溯到2013年)。可能确实存在更好的方法(并且希望将来,minstd将是这样的方法),但这确实是进步。至于random_device的糟糕实现-这太可怕了,应该被认为是一个错误(如果允许的话,也可能是C ++标准的错误)。

–沃尔特
2015年12月16日15:01



我完全同意你的看法;我实际上并不想批评您的解决方案本身,只是想警告那些不经意的读者,尽管有C ++ 11的承诺,但关于此事的明确答案尚待编写。我将在2015年发布该主题的概述,作为相关问题的答案。

– Alberto M
2015年12月16日15:25

@AndreyPortnoy如果可能的话,我总是将auto用作自动变量,因为这使维护更加容易。即使稍后我将Uniform_int_distribution <>的模板参数更改为其他内容,例如int64_t,它也会自动选择正确的类型。

–沃尔特
18-2-19在6:17



#3 楼

如果您的编译器支持C ++ 0x,并且可以选择使用它,那么新的标准<random>标头可能会满足您的需求。它具有高质量的uniform_int_distribution,可以接受最小和最大范围(包括您所需要的范围),并且您可以在各种随机数生成器中进行选择以插入该分布。

这里的代码可以生成一百万随机int均匀分布在[-57,365]中。我已经使用了新的std <chrono>工具来计时,因为您提到性能是您最关心的问题。打印出:

2.10268e + 07每秒随机数。

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

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


如果以后发现int不能满足分配范围,可以通过更改uniform_int_distribution来解决(例如更改为long long): >
    G g(seed);


如果以后您发现minstd_rand的质量不够高,也可以轻松换出。例如:

    typedef std::uniform_int_distribution<long long> D;


具有对随机数生成器的单独控制,并且随机分布可以完全解放。

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

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


x_前缀表示“预期”)

评论


此答案可以使用简短的摘要代码段,该摘要代码段仅显示从范围生成随机整数所需的代码。

– Arekolek
15年11月27日在15:37

分布的最小值和最大值永不变,这一事实使问题变得更加容易。如果必须在每次迭代中使用不同的边界创建d怎么办?它会减慢回路多少?

–quant_dev
18年1月7日在17:47

#4 楼

让我们将问题分为两部分:


生成一个从0到(max-min)范围内的随机数n
将min添加到该数

第一部分显然是最难的。假设rand()的返回值是完全统一的。使用模将在第一个(RAND_MAX + 1) % (max-min+1)数字上增加bias
。因此,如果我们可以将RAND_MAX神奇地更改为RAND_MAX - (RAND_MAX + 1) % (max-min+1),就不会再有任何偏差了。算法。每当rand()返回一个太大的数字时,我们只要求另一个随机数,直到得到一个足够小的数字为止。是在第一次尝试中获得足够小的数字的概率。由于1/p始终小于p
我们知道RAND_MAX - (RAND_MAX + 1) % (max-min+1),因此对于任何范围,预期的迭代次数始终小于2。通过这种技术,应该可以在不到一秒钟的时间内在标准CPU上生成数千万个随机数。

编辑:

尽管以上在技术上是正确的,在实践中,DSimon的答案可能更有用。您不应该自己实现这些东西。我已经看到了很多拒绝采样的实现,通常很难看到它是否正确。

评论


出于完整性考虑:这是拒绝采样。

–战争
2011-02-15 21:22

有趣的事实:Joel Spolsky曾经提到此问题的一个版本,作为StackOverflow擅长回答的一个示例。我浏览了当时涉及拒绝抽样的站点上的答案,每个答案都不正确。

–Jørgen Fogh
14-10-29在22:40

#5 楼

Mersenne Twister怎么样? 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素数;
操纵种子的技术基于一种较旧的“扭曲”算法-因此,其名称为“ Mersenne Twister”。

Mersenne
Twister是使用二进制
运算-与
费时的乘法相反-用于
生成数字。该算法还具有很长的周期,并且粒度很好。对于非加密应用程序,它既快速又有效。


评论


梅森捻线机是一个很好的生成器,但不管基础生成器本身如何,他所要解决的问题仍然存在。

–杰里·科芬(Jerry Coffin)
2011-2-15在20:21

我不想仅将Boost用于随机生成器,因为(因为我的项目是一个库),这意味着要对该项目引入另一个依赖关系。将来无论如何我可能都会被迫使用它,因此我可以切换到该生成器。

–MatějZábský
2011-2-15在20:26

@Jerry Coffin哪个问题?我之所以提供它,是因为它满足了他的所有要求:快速,统一(使用boost :: uniform_int分布),您可以将最小最大范围转换为所需的任何值,并且可以播种。

– Aphex
2011-2-15在20:29



@mzabsky我可能不会阻止我,当我不得不将我的项目发送给我的教授进行提交时,我只包含了我正在使用的相关的boost头文件;您不必将整个40mb boost库与您的代码打包在一起。当然,在您的情况下,由于版权等其他原因,这可能不可行。

– Aphex
2011-2-15在20:32

@Aphex我的项目不是真正的科学模拟器,也不是真正需要统一分发的东西。我使用旧的生成器1.5年没有任何问题,当我第一次需要它生成非常小的范围内的数字(在这种情况下为3)时,我才注意到有偏分布。速度仍然是考虑采用升压解决方案的理由。我将研究它的许可证,看看是否可以将一些需要的文件添加到我的项目中-我现在喜欢“签出-> F5->准备使用”。

–MatějZábský
2011-2-15在20:44

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

评论


尽管它不受欢迎,但这也是我在非科学项目中使用的方法。易于理解(不需要数学学位)并且表现出色(无需使用它来分析任何代码)。 :)在大范围的情况下,我想我们可以将两个rand()值串在一起,并获得一个30位的值来使用(假设RAND_MAX = 0x7fff,即15个随机位)

–efotinis
2011年5月21日在20:48



将RAND_MAX更改为(double)RAND_MAX,以避免整数溢出警告。

– alex
17 Mar 2 '17 at 16:21

#7 楼

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

参考:
对于()[]定义,请访问:

https://en.wikipedia.org/wiki/Interval_(mathematics)

有关rand和srand函数或RAND_MAX的定义,请访问:

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

[min,max]

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


(min,max]

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


[min,max)

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


(最小,最大)

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


#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循环。

评论


海事组织,提出的解决方案都没有真正改善。他的基于循环的解决方案有效,但效率可能很低,尤其是对于OP讨论的小范围。他的统一偏差解决方案实际上根本不会产生统一偏差。至多它伪装缺乏统一性。

–杰里·科芬(Jerry Coffin)
2011-2-15在20:15

@Jerry:请检查新版本。

–耶利米·威尔考克(Jeremiah Willcock)
2011-2-15在20:21



我不确定是否可以正常工作。可能,但是正确性似乎并不明显,至少对我而言。

–杰里·科芬(Jerry Coffin)
2011-2-15在21:03

@Jerry:这是我的理由:为简单起见,假设范围为[0,h)。调用rand()有RAND_MAX + 1个可能的返回值。将rand()%h折叠到其中的h个输出值中的每个(RAND_MAX + 1)/ h,除了(RAND_MAX + 1)/ h +1中的每个值映射到小于(RAND_MAX + 1 )%h(由于通过h输出的最后一个部分循环)。因此,我们删除(RAND_MAX + 1)%h可能的输出以获得无偏分布。

–耶利米·威尔考克(Jeremiah Willcock)
2011-2-16在0:11

#9 楼

我建议使用Boost.Random库,它非常详细且文档齐全,可让您显式指定所需的分布,并且在非加密方案中实际上可以胜过典型的C库rand实现。

#10 楼

在该线程拒绝采样中已经讨论过,但是我想基于rand() % 2^something不会引入任何偏差(如上所述)的事实提出一种优化方法。

算法非常简单:


计算大于间隔长度2的最小幂次
在“新”间隔中随机分配一个数字
如果该数字小于原始间隔的长度,请返回该数字


否则拒绝该文件



示例代码:

int randInInterval(int min, int max) {
    int intervalLen = max - min + 1;
    //now calculate the smallest power of 2 that is >= than `intervalLen`
    int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen)));

    int randomNumber = rand() % ceilingPowerOf2; //this is "as uniform as rand()"

    if (randomNumber < intervalLen)
        return min + randomNumber;      //ok!
    return randInInterval(min, max);    //reject sample and try again
} 


这特别适用于小间隔,因为2的幂会“接近”实际间隔长度,因此未命中的次数会更小。

PS
显然避免递归会更有效(无需反复计算对数上限。)但我认为此示例更具可读性。

#11 楼

请注意,在大多数建议中,您从rand()函数获得的初始随机值(通常是0到RAND_MAX)被简单地浪费了。您只能在其中创建一个随机数,而有一个合理的过程可以为您提供更多信息。我们从[0,max-min]

开始,取底数b = max-min + 1

从代表从底数b的rand()得到的数字开始。

这样,您就有了floor(log(b,RAND_MAX)),因为基b中的每个数字(可能除了最后一个数字)都表示[0,max-min]范围内的随机数。

当然,对于每个随机数r + min,最终移至[min,max]很简单。

int n = NUM_DIGIT-1;
while(n >= 0)
{
    r[n] = res % b;
    res -= r[n];
    res /= b;
    n--;
}


如果NUM_DIGIT是可以提取的基数b中的位数,即
NUM_DIGIT = floor(log(b,RAND_MAX))

的一个RAND_MAX随机数之一,提供b

#12 楼

公式很简单,因此请尝试使用此表达式,

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


评论


整个问题是使用C / C ++的rand来返回运行时指定范围内的整数。如该线程所示,如果要避免破坏它们的统计属性或性能,将随机整数从[0,RAND_MAX]映射到[MIN,MAX]并不是很简单。如果您在[0,1]范围内有双精度数,则映射很容易。

–MatějZábský
2014年8月6日上午11:10

您的答案是错误的,应该改用模数:int num =(int)rand()%(max-min)+ min;

–Jaime Ivan Cervantes
17年6月28日在5:28



#13 楼

如果我没记错的话,下面的表达式应该是公正的:包括1.0,且max和min是整数,且min

评论


std :: floor返回double,在这里我们需要一个整数值。我只是将其转换为int而不是使用std :: floor。

–音乐爱好者
13年9月30日在18:27