【C++基础】第一百零一课:[标准库特殊设施]随机数

random,随机数引擎类,随机数分布类

Posted by x-jeff on July 16, 2024

【C++基础】系列博客为参考《C++ Primer中文版(第5版)》C++11标准)一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.随机数

程序通常需要一个随机数源。在新标准出现之前,C和C++都依赖于一个简单的C库函数rand来生成随机数。此函数生成均匀分布的伪随机整数,每个随机数的范围在0和一个系统相关的最大值(至少为32767)之间。

rand函数有一些问题:即使不是大多数,也有很多程序需要不同范围的随机数。一些应用需要随机浮点数。一些程序需要非均匀分布的数。而程序员为了解决这些问题而试图转换rand生成的随机数的范围、类型或分布时,常常会引入非随机性。

定义在头文件random中的随机数库通过一组协作的类来解决这些问题:随机数引擎类(random-number engines)和随机数分布类(random-number distribution)。表17.14描述了这些类。一个引擎类可以生成unsigned随机数序列,一个分布类使用一个引擎类生成指定类型的、在给定范围内的、服从特定概率分布的随机数。

C++程序不应该使用库函数rand,而应使用default_random_engine类和恰当的分布类对象。

2.随机数引擎和分布

随机数引擎是函数对象类(参见:函数调用运算符),它们定义了一个调用运算符,该运算符不接受参数并返回一个随机unsigned整数。我们可以通过调用一个随机数引擎对象来生成原始随机数:

1
2
3
4
default_random_engine e; //生成随机无符号数
for (size_t i = 0; i < 10; ++i)
    //e()“调用”对象来生成下一个随机数
    cout << e() << " ";

标准库定义了多个随机数引擎类,区别在于性能和随机性质量不同。每个编译器都会指定其中一个作为default_random_engine类型。此类型一般具有最常用的特性。表17.15列出了随机数引擎操作。

对于大多数场合,随机数引擎的输出是不能直接使用的,这也是为什么早先我们称之为原始随机数。问题出在生成的随机数的值范围通常与我们需要的不符,而正确转换随机数的范围是极其困难的。

2.1.分布类型和引擎

为了得到在一个指定范围内的数,我们使用一个分布类型的对象:

1
2
3
4
5
6
7
//生成0到9之间(包含)均匀分布的随机数
uniform_int_distribution<unsigned> u(0,9);
default_random_engine e; //生成无符号随机整数
for (size_t i = 0; i < 10; ++i)
    //将u作为随机数源
    //每个调用返回在指定范围内并服从均匀分布的值
    cout << u(e) << " ";

此代码生成下面这样的输出:

1
0 1 7 4 5 2 0 6 6 9

类似引擎类型,分布类型也是函数对象类。分布类型定义了一个调用运算符,它接受一个随机数引擎作为参数。分布对象使用它的引擎参数生成随机数,并将其映射到指定的分布。

注意,我们传递给分布对象的是引擎对象本身,即u(e)。如果我们将调用写成u(e()),含义就变为将e生成的下一个值传递给u,会导致一个编译错误。我们传递的是引擎本身,而不是它生成的下一个值,原因是某些分布可能需要调用引擎多次才能得到一个值。

当我们说随机数发生器时,是指分布对象和引擎对象的组合。

2.2.比较随机数引擎和rand函数

调用一个default_random_engine对象的输出类似rand的输出。随机数引擎生成的unsigned整数在一个系统定义的范围内,而rand生成的数的范围在0到RAND_MAX之间。一个引擎类型的范围可以通过调用该类型对象的min和max成员来获得:

1
cout << "min: " << e.min() << " max: " << e.max() << endl;

在我们的系统中,此程序生成下面的输出:

1
min: 1 max: 2147483646

2.3.引擎生成一个数值序列

随机数发生器生成的数看起来是随机的,但对一个给定的发生器,每次运行程序它都会返回相同的数值序列。序列不变这一事实在调试时非常有用。但另一方面,使用随机数发生器的程序也必须考虑这一特性。

作为一个例子,假定我们需要一个函数生成一个vector,包含100个均匀分布在0到9之间的随机数。我们可能认为应该这样编写此函数:

1
2
3
4
5
6
7
8
9
10
11
//几乎肯定是生成随机整数vector的错误方法
//每次调用这个函数都会生成相同的100个数!
vector<unsigned> bad_randVec()
{
    default_random_engine e;
    uniform_int_distribution<unsigned> u(0,9);
    vector<unsigned> ret;
    for (size_t i = 0; i < 100; ++i)
        ret.push_back(u(e));
    return ret;
}

但是,每次调用这个函数都会返回相同的vector:

1
2
3
4
vector<unsigned> v1(bad_randVec());
vector<unsigned> v2(bad_randVec());
//将打印“equal”
cout << ((v1 == v2) ? "equal" : "not equal") << endl;

此代码会打印equal,因为vector v1和v2具有相同的值。

编写此函数的正确方法是将引擎和关联的分布对象定义为static的:

1
2
3
4
5
6
7
8
9
10
11
12
//返回一个vector,包含100个均匀分布的随机数
vector<unsigned> good_randVec()
{
    //由于我们希望引擎和分布对象保持状态,因此应该将它们
    //定义为static的,从而每次调用都生成新的数
    static default_random_engine e;
    static uniform_int_distribution<unsigned> u(0,9);
    vector<unsigned> ret;
    for (size_t i = 0; i < 100; ++i)
        ret.push_back(u(e));
    return ret;
}

由于e和u是static的,因此它们在函数调用之间会保持住状态。第一次调用会使用u(e)生成的序列中的前100个随机数,第二次调用会获得接下来100个,依此类推。

一个给定的随机数发生器一直会生成相同的随机数序列。一个函数如果定义了局部的随机数发生器,应该将其(包括引擎和分布对象)定义为static的。否则,每次调用函数都会生成相同的序列。

2.4.设置随机数发生器种子

随机数发生器会生成相同的随机数序列这一特性在调试中很有用。但是,一旦我们的程序调试完毕,我们通常希望每次运行程序都会生成不同的随机结果,可以通过提供一个种子(seed)来达到这一目的。种子就是一个数值,引擎可以利用它从序列中一个新位置重新开始生成随机数。

为引擎设置种子有两种方式:在创建引擎对象时提供种子,或者调用引擎的seed成员:

1
2
3
4
5
6
7
8
9
10
11
12
default_random_engine e1; //使用默认种子
default_random_engine e2(2147483646); //使用给定的种子值
//e3和e4将生成相同的序列,因为它们使用了相同的种子
default_random_engine e3; //使用默认种子值
e3.seed(32767); //调用seed设置一个新种子值
default_random_engine e4(32767); //将种子值设置为32767
for (size_t i = 0; i != 100; ++i) {
    if (e1() == e2())
        cout << "unseeded match at iteration: " << i << endl;
    if (e3() != e4())
        cout << "seeded differs at iteration: " << i << endl;
}

本例中我们定义了四个引擎。前两个引擎e1和e2的种子不同,因此应该生成不同的序列。后两个引擎e3和e4有相同的种子,它们将生成相同的序列。

选择一个好的种子,与生成好的随机数所涉及的其他大多数事情相同,是极其困难的。可能最常用的方法是调用系统函数time。这个函数定义在头文件ctime中,它返回从一个特定时刻到当前经过了多少秒。函数time接受单个指针参数,它指向用于写入时间的数据结构。如果此指针为空,则函数简单地返回时间:

1
default_random_engine e1(time(0)); //稍微随机些的种子

由于time返回以秒计的时间,因此这种方式只适用于生成种子的间隔为秒级或更长的应用。

3.其他随机数分布

随机数引擎生成unsigned数,范围内的每个数被生成的概率都是相同的。而应用程序常常需要不同类型或不同分布的随机数。标准库通过定义不同随机数分布对象来满足这两方面的要求,分布对象和引擎对象协同工作,生成要求的结果。表17.16列出了分布类型所支持的操作。

3.1.生成随机实数

程序常需要一个随机浮点数的源。特别是,程序经常需要0到1之间的随机数。

最常用但不正确的从rand获得一个随机浮点数的方法是用rand()的结果除以RAND_MAX,即,系统定义的rand可以生成的最大随机数的上界。这种方法不正确的原因是随机整数的精度通常低于随机浮点数,这样,有一些浮点值就永远不会被生成了。

使用新标准库设施,可以很容易地获得随机浮点数。我们可以定义一个uniform_real_distribution类型的对象,并让标准库来处理从随机整数到随机浮点数的映射。与处理uniform_int_distribution一样,在定义对象时,我们指定最小值和最大值:

1
2
3
4
5
default_random_engine e; //生成无符号随机整数
//0到1(包含)的均匀分布
uniform_real_distribution<double> u(0,1);
for (size_t i = 0; i < 10; ++i)
    cout << u(e) << " ";

3.2.使用分布的默认结果类型

分布类型都是模板,具有单一的模板类型参数,表示分布生成的随机数的类型,对此有一个例外,我们会在后续介绍。这些分布类型要么生成浮点类型,要么生成整数类型。

每个分布模板都有一个默认模板实参。生成浮点值的分布类型默认生成double值,而生成整型值的分布默认生成int值。由于分布类型只有一个模板参数,因此当我们希望使用默认随机数类型时要记得在模板名之后使用空尖括号:

1
2
//空<>表示我们希望使用默认结果类型
uniform_real_distribution<> u(0,1); //默认生成double值

3.3.生成非均匀分布的随机数

除了正确生成在指定范围内的数之外,新标准库的另一个优势是可以生成非均匀分布的随机数。

作为一个例子,我们将生成一个正态分布的值的序列,并画出值的分布。由于normal_distribution生成浮点值,我们的程序使用头文件cmath中的lround函数将每个随机数舍入到最接近的整数。我们将生成200个数,它们以均值4为中心,标准差为1.5。由于使用的是正态分布,我们期望生成的数中大约99%都在0到8之间(包含)。我们的程序会对这个范围内的每个整数统计有多少个生成的数映射到它:

1
2
3
4
5
6
7
8
9
10
default_random_engine e; //生成随机整数
normal_distribution<> n(4,1.5); //均值4,标准差1.5
vector<unsigned> vals(9); //9个元素均为0
for (size_t i = 0; i != 200; ++i) {
    unsigned v = lround(n(e)); //舍入到最接近的整数
    if (v < vals.size()) //如果结果在范围内
        ++vals[v]; //统计每个数出现了多少次
}
for (size_t j = 0; j != vals.size(); ++j)
    cout << j << ": " << string(vals[j], '*') << endl;

当循环结束时,我们打印vals的内容,可能会打印出像下面这样的结果:

1
2
3
4
5
6
7
8
9
0: **
1: ********
2: ***************************
3: ************************************************
4: *********************************************
5: **************************************
6: ************************
7: *******
8: *

3.4.bernoulli_distribution类

有一个分布不接受模板参数,即bernoulli_distribution,因为它是一个普通类,而非模板。此分布总是返回一个bool值,它返回true的概率是一个常数,此概率的默认值是0.5。

作为一个这种分布的例子,我们可以编写一个程序,这个程序与用户玩一个游戏。为了进行这个游戏,其中一个游戏者——用户或是程序——必须先行。我们可以用一个值范围是0到1的uniform_int_distribution来选择先行的游戏者,但也可以用伯努利分布来完成这个选择。假定已有一个名为play的函数来进行游戏,我们可以编写像下面这样的循环来与用户交互:

1
2
3
4
5
6
7
8
9
10
string resp;
default_random_engine e; //e应保持状态,所以必须在循环外定义!
bernoulli_distribution b; //默认是50/50的机会
do {
    bool first = b(e); //如果为true,则程序先行
    cout << (first ? "We go first" : "You get to go first") << endl;
    //传递谁先行的指示,进行游戏
    cout << ((play(first)) ? "sorry, you lost" : "congrats, you won") << endl;
    cout << "play again? Enter 'yes' or 'no'" << endl;
} while (cin >> resp && resp[0] == 'y');

由于引擎返回相同的随机数序列,所以我们必须在循环外声明引擎对象。否则,每步循环都会创建一个新引擎,从而每步循环都会生成相同的值。类似的,分布对象也要保持状态,因此也应该在循环外定义。

1
bernoulli_distribution b(.55); //给程序一个微小的优势

如果b定义如上,则程序有55/45的机会先行。