我需要它要快。我的项目需要生成数百万(有时甚至是数千万)的随机数,而我的当前生成器函数已被证明是瓶颈。
我需要它具有合理的统一性(使用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.
请您提出更好的公式吗? (甚至整个伪随机数生成器函数)
#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
评论
请参阅: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/…