编程C++

【STL】随机数

字数统计: 1.6k字   |   阅读时长: 6分
, , ,

摘要: 本文介绍在 C++ STL 中，如何使用随机数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文介绍在 C++ STL 中，如何使用随机数，主要参考《C++标准库》 第2版，作者 Nicolai M. josuttis，侯捷 译 $17.1。

$1 随机数与分布

1
#include <random>

引擎: 随机性的源头，产生随机的无符号值，居于分布于一个预定义的最大值和最小值之间
分布: 把引擎产生的数字转换为随机数

C++ 标准库提供多个引擎，这些引擎在质量，大小，速度上有不同。

数学上存在多种创在随机数的办法，其算法和实现均会影响产出的质量和效率。

使用例子

产生随机数的流程: 定义引擎，定义分布，将引擎和分布结合起来，其中引擎是函数对象。

1
2
3
4
5
6
std::default_random_engine dre;
std::uniform_int_distribution<int> di(10, 20); // [10, 20]
std::uniform_real_distribution<long double> dr(-1.0, 1.0); // [-1.0, 1.0)
std::uniform_real_distribution<> d; // [0.0, 1.0)
double random_int = di(dre);
double random_real = dr(dre);

以 di(dre) 为例，std::uniform_int_distribution<int> di(10, 20); 定义 di 生成的随机数分布在 [10, 20]
di(dre) 产生随机数的过程: 调用分布(di)的 operator() 并将引擎作为实参传入。

引擎的初始化

引擎的初始状态都有明确定义，并非随机的。因此以下写法会输出相同的数值两次：

1
2
3
4
5
std::default_random_engine dre1;
std::default_random_engine dre2;
std::uniform_int_distribution<int> di(10, 20);
int n1 = di(dre1);
int n2 = di(dre2);

若要一个不可预测的随机值，则必须随机地给引擎设定初态，即无法以代码影响的行为，例如两次鼠标点击之间的毫秒数。

1
2
unsigned int seed = ...
std::default_random_engine dre(seed);

也可以调用成员函数用种子改变引擎状态。

避免临时引擎

当函数的参数为随机数引擎时，不应该传入临时引擎，而应该传引用，因为每次初始化引擎时，其初始状态相同。

因此以下写法是错的: 

1
std::shuffle(vec.begin(), vec.end(), std::default_random_engine());

正确的写法：

1
2
std::default_random_engine dre;
std::shuffle(vec.begin(), vec.end(), dre);

引擎需要搭配分布

引擎产生的值直接作为线性随机数，如果区间不吻合，加上取模运算。

这种做法不好: 这种做法类似于 C 标准随机值生成器 rand()，用 rand() % n 作为线性随机数的做法。

Ref: 《Accelerate C++》$7-4-4

$2 引擎

随机数引擎是一个函数对象，引擎的 operator() 可以生成数值。

随机数引擎是一个带有状态的随机性源头，其状态决定了它将生成哪一个随机值序列。

对于除了 std::default_random_engine 之外的引擎，在任何平台上带有相同状态的同类性引擎将产生相同的随机值。std::default_random_engine 例外是因为它依赖于实现，但它依然是可预期值，至少不同平台用的算法可能有所不同。

C++ 标准库提供 16 个随机数引擎

  • 基础引擎

    • Class std::linear_congruential_engine
    • Class std::mersenne_twister_engine
    • Class std::substract_with_carry_engine

  • 引擎适配器

    • Class std::discard_block_engine
    • Class std::independent_bits_engine
    • Class std::shuffle_order_engine

  • 适配器并带预定义参数

    • std::minstd_rand0
    • std::minstd_rand
    • std::mt19937
    • std::mt19937_64
    • std::ranlux24_base
    • std::ranlux48_base
    • std::ranlux24
    • std::ranlux48
    • std::kruth_b

此外 std::default_random_engine 是一个由实现决定的类型定义。

引擎的操作

1
2
3
4
5
6
7
8
9
10
11
12
engine e         默认构造
engine e(seed)   指定初态
engine e2(e1)    拷贝构造，e2 和 e1 有相同状态
e.seed()         将引擎设为初始状态
e.seed(seed)     将引擎状态设定为指定值
e()              返回下一个随机值，并前进其状态
e.discard(n)     前进接下来的 n 个状态
e1 == e2         返回 e1, e2 是否拥有相同状态 
e1 != e2         返回 e1, e2 是否拥有不同状态
ostrm << e       将 e 的状态写入 ostrm, 是一系列十进制数，以空格分隔
                 该序列并不是随机值，仅保证它被同类型引擎 e2 读取后 e2 也持有了相同状态
istrm >> e       从 istrm 读取一个新状态放入 e

$3 分布

分布：把引擎产生的值转换为真实有用的随机数，产出数字的概率取决于使用何种分布。分布可以带可调的参数。

几乎所有分布都是模板，以其生成值的类型为模板参数。唯一例外是 bernoulli_distribution，它是一个类，因为它只生成 bool。

C++ 标准库提供的分布

各个分布的密度函数：《C++标准库》 第2版，$17-1-5

均匀分布

  • std::uniform_int_distribution, 整数
  • std::uniform_real_distribution, 实数

伯努利分布

  • std::bernoulli_distribution, 布尔
  • std::binomial_distribution, 整数
  • std::geometric_distribution, 整数
  • std::negative_binomial_distribution, 整数

泊松分布

  • std::poisson_distribution, 整数
  • std::exponential_distribution, 实数
  • std::gamma_distribution, 实数
  • std::weibull_distribution, 实数
  • std::extreme_value_distribution, 实数

正态分布

  • std::normal_distribution, 实数
  • std::lognormal_distribution, 实数
  • std::chi_squared_distribution, 实数
  • std::cauchy_distribution, 实数
  • std::fisher_f_distribution, 实数
  • std::student_t_distribution, 实数

抽样分布

  • std::discrete_distribution, 整数
  • std::piecewise_constant_distribution, 实数
  • std::piecewise_linear_distribution, 实数

分布的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
distr::result_type      被生成值的算术形式
distr d                 默认构造
distr d(args)           指定分布的参数
d(e)                    返回引擎搭配分布的下一个值并推进引擎状态

d.min()                 返回最小值
d.max()                 返回最大值
d1 == d2                返回 d1 和 d2 是否有相同状态
d1 != d2                返回 d1 和 d2 是否有不同状态    
ostrm << d
istrm >> d

distr::param_type       distr 的参数化类型
distr d(pt)             创建分布以 param_type pt 完成参数化
d.param(pt)             将当前的参数化类型设为 param_type pt
d.param()               返回当前参数化类型和值，类型为 param_type
d(e, pt)                根据引擎 e 和 param_type pr 返回下一个值，并推进 e 状态

参数化的例子: 均匀分布有两个参数 a 和 b，可以分别传实参

1
2
3
4
5
std::uniform_int_distribution<> d(0, 20);
d.a()
d.b()
d.param().a()
d.param().b()

也可以使用 param_type 把参数当整体传递。

1
2
3
std::uniform_int_distribution<>::param_type pt(100, 200);
d(e, pt);
d.param(pt);

$4 Tips

生成双闭实数区间

std::uniform_real_distribution<double>(0.0, 1.0) 生成的是 [0.0, 1.0)，若要生成 [0.0, 1.0] 可以

1
std::uniform_real_distribution<double>(0.0, std::nextafter(1.0, std::numeric_limits<double>::max()));
Share