【CPP】(伪)随机数生成大法
C 随机库
C语言提供的 <cstdlib>
库,包含 两个函数和一个常量
定义
int rand();
:返回 [0
…RAND_MAX
] 的随机数。void srand( unsigned seed );
:以值seed
播种 随机数生成器,用于后续的rand()
。RAND_MAX
:rand()
生成的最大可能值。依赖于编译器实现,保证至少为32767
。
基本用法
基于以下四点
- 以相同的
seed
播种,产生的随机数序列相同。 - 若未调用
srand()
,则rand()
表现如同它以srand(1)
播种。 - 通常来说,在程序开始或者任何到
rand()
的调用前,应该只播种一次随机数生成器。 - 标准实践是以当前时间作为种子。
1 |
|
模偏差
在上述生成0到99的随机数算法中,如果只关心一个随机数,那没问题。但如果要生成随机数序列,就会存在模偏差问题。即 rand()%100
并不能以相等的概率产生介于0和99之间的数字!
因为 rand()%n
的结果并不一定能等概率映射到0~n-1上,除非 RAND_MAX%n == n - 1
。
均匀分布
为了解决模偏差问题,首先定义一个新的 RAND_MAX_N =RAND_MAX - RAND_MAX % n
,则 RAND_MAX_N%n == n - 1
,这样就能等概率映射了;其次为了得到 0
到 RAND_MAX_N
的随机数,需要引入拒绝采样。简单来说就是,一直生成,拒绝超出范围的,直到符合条件。
为什么不直接用拒绝采样生成0到n-1的随机数?
因为执行次数的数学期望太高了。每次只有 n/RAND_MAX的概率在规定范围内获得一个值,平均需要调用RAND_MAX/n 次 rand()。
1 |
|
C++ 标准库
stl
包含了随机数库<random>
,其中定义了一组随机数引擎类模板和随机数分布类模板。它通过随机数引擎产生均匀的随机数序列,随机数分布使用随机数引擎生成服从特定概率分布的随机数。
对于随机数生成,有多个分布类模板的原因是:我们在给定场景下生成的序列需要依靠数据的特性。医院前来就诊的病人的模式可能和到商店的顾客的模式有很大不同,因此需要运用不同的分布。而且,商店顾客的模式可能会有所不同,取决于商店的种类及其位置,因此对于不同商店的顾客的到达模型,可能也需要运用不同的分布。
之所以有多种随机数引擎和生成器,是因为没有一种算法可以生成适合所有情况的随机数。相比其他算法,有一些算法可以生成更长的无重复序列;一些算法要求的计算开销更小。当知道想模型化的数据的特性时,就能够决定使用哪种分布和哪种随机序列生成能力。
随机数引擎
标准库定义了一组随机数引擎类模板和适配器模板,同时使用不同的算法预定义了一组随机数引擎类模板的实例作为随机数生成器。此外还提供了基于硬件源的非确定随机数生成器。
随机数引擎类
随机数引擎类是一个定义了生成随机位序列的无符号整数序列机制的类模板。STL
定义了3个代表随机数引擎的类模板。这些是可以定制的。
linear_congruential_engine,实现线性同余算法
mersenne_twister_engine,实现梅森旋转器算法
subtract_with_carry_engine,实现带进位减(一种延迟斐波那契)算法
随机数引擎适配器
随机数引擎适配器是一个类模板,它通过修改另一个随机数引擎生成的序列来生成随机数序列。<random>
中提供了三种不同功能的适配器。
discard_block_engine,舍弃随机数引擎的某些输出
independent_bits_engine,将一个随机数引擎的输出打包为指定位数的块
shuffle_order_engine,以不同顺序发送一个随机数引擎的输出
预定义随机数生成器
随机数生成器是随机数引擎类模板的一个预定义的实例。每一个生成器都会将一套具体的模板参数应用到随机数引擎的类模板上,因此它是一个类型别名。STL
提供了几个预定义的随机数生成器,为了生成随机数,它们实现了一些著名的算法。因为是对三种随机数引擎类模板的实例化,所以也分成三组:同组之间使用相同的算法,只是参数类型不同。
- LCG线性同余法随机数生成器
minstd_rand0
minstd_rand
- 梅森旋转随机数生成器
mt19937
mt19937_64
- 带进位减法随机数生成器
ranlux24_base
ranlux48_base
这些预定义生成器定义了算法的最佳实践,避免了参数的选择,可以直接选择引擎,设定分布即可。
此外,根据编译器设置的默认引擎类型(上述三种之一),还可以使用类型别名default_random_engine
来简单快捷地生成随机数。
非确定随机数生成器
std::random_device 定义的函数对象可以生成用来作为种子的随机的无符号整数值。这个类使用非确定性数据源,它通常是由操作系统提供的,通过硬件生成真正的不确定随机数(如果硬件不支持,标准也允许使用伪随机生成方法实现此函数)。
非确定性数据源可以是连续敲打键盘的时间区间,或者鼠标点击的区间,或者当前的时钟时间,或者一些物理特性。
随机数分布
随机数分布处理随机数生成器的输出序列,使得产生的随机数序列服从指定的概率密度函数分布。STL
提供了为各种不同的分布定义函数对象的类模板。
下面只给出部分代表类模板,更多请参考 STL random。
- 均匀分布
uniform_int_distribution
,产生在一个范围上均匀分布的整数值uniform_real_distribution
,产生在一个范围上均匀分布的实数值
- 伯努利分布
bernoulli_distribution
,产生伯努利分布上的bool
值binomial_distribution
,产生二项分布上的整数值
- 泊松分布
poisson_distribution
,产生泊松分布上的整数值exponential_distribution
,产生指数分布上的实数值
- 正态分布
normal_distribution
,产生标准正态(高斯)分布上的实数值lognormal_distribution
,产生对数正态分布上的实数值
- 采样分布
discrete_distribution
,产生离散分布上的随机整数
快速使用
生成服从指定分布的随机数一般分为四步
- 生成随机数种子
- 为随机数生成器播种
- 定义随机数分布
- 按照指定的分布生成随机数
以下是一个快速使用 <random>
的例子,在具体使用上仍有许多可探究之处,留待下次一定。。。
1 |
|
输出如下图所示。
参考资料
https://www.delftstack.com/howto/cpp/generate-random-number-in-range-cpp/
https://zh.cppreference.com/w/cpp/numeric/random
http://c.biancheng.net/view/635.html