首页 > STL > 随机数 阅读:1,107

C++ 随机数生成(STL 随机数生成)完全攻略

在随机数生成方面 STL 有 4 个术语:
  1. 随机数生成引擎是一个定义了生成随机位序列的无符号整数序列机制的类模板。STL定义了3个代表随机数引擎的类模板。本章的后面会对它们进行简短的介绍,但除非你对它们所使用的算法已经有深入的了解,否则不要直接使用它们,而应该使用随机数生成器。
  2. 随机数生成器是随机数引擎类模板的一个预定义的实例。每一个生成器都会将一套具体的模板参数应用到随机数引擎的类模板上,因此它是一个类型别名。STL提供了几个预定义的随机数生成器,为了生成随机数,它们实现了一些著名的算法。
  3. 随机数引擎适配器是一个类模板,它通过修改另一个随机数引擎生成的序列来生成随机数序列。
  4. 分布表示的是随机序列中的数出现在序列中的概率。STL定义了为各种不同的分布定义函数对象的类模板。

对于随机数生成,有多个分布类模板的原因是:我们在给定场景下生成的序列需要依靠数据的特性。医院前来就诊的病人的模式可能和到商店的顾客的模式有很大不同,因此需要运用不同的分布。而且,商店顾客的模式可能会有所不同,取决于商店的种类及其位置,因此对于不同商店的顾客的到达模型,可能也需要运用不同的分布。

之所以有多种随机数引擎和生成器,是因为没有一种算法可以生成适合所有情况的随机数。相比其他算法,有一些算法可以生成更长的无重复序列;一些算法要求的计算开销更小。当知道想模型化的数据的特性时,就能够决定使用哪种分布和哪种随机序列生成能力。

生成随机数的种子

随机数的生成算法总是从单个或多个种子开始的,它们代表着产生随机数的计算的初始输入。种子决定了随机数生成器的初始状态和全部序列。随机数生成器的状态由用来计算序列的下一个值的所有数据组成。算法是递归的,因此种子会创建一个初始状态,它被用来生成序列的第一个值;生成的值会改变状态,然后用它来生成下一个值,以此类推。

对于给定的单个或多个种子,随机数生成器总会生成相同的序列。显然在测试时,这很有帮助;可以确定程序是否正常工作,输入数据从任意一个运行到下一个至少也不是那么容易。当然,一旦程序被测试,我们希望程序每次运行都使用随机数生成器生成的不同序列。总是做同样事情的游戏程序也不会有趣。为了每次能够产生不同的序列,必须提供不同的种子(理想的随机值)。它们被叫作不确定的值,因为它们是不可预测的。

STL 中的所有随机数生成算法都可以用单个种子来初始化。如果定义的初始状态需要更多的种子,它们可以自动生成。显然,随机数序列的熵取决于种子。种子的比特数是至关重要的,对于 1 字节的种子,只有 255 个可能的值,所以最多可生成 255 个不同的序列。为了使随机序列的熵达到最大,需要做两件事:需要一个真随机(不是伪随机)的种子,以及种子的最大可能范围。

获取随机种子

random_device 类定义的函数对象可以生成用来作为种子的随机的无符号整数值。这个类应该使用非确定性数据源,它通常是由操作系统提供的。C++14 标准允许在非确定数据源不可用时,使用随机数引擎,但在大多数实现中,这没有必要。非确定性数据源可以是连续敲打键盘的时间区间,或者鼠标点击的区间,或者当前的时钟时间,或者一些物理特性。

可以按如下方式创建 random_device 对象:
std::random_device rd; // Source of seeds!
构造函数有一个 string& 类型的参数,它有定义的默认值。在我们像这样省略它时,会得到我们环境中默认的 random_device 对象。理论上,参数允许我们提供一个字符串来标识使用的非确定性数据源,但需要检查我们的文档,看看我们的 C++ 库的这个选项是否可用。下面演示如何用 random_device  对象生成一个种子值:
auto my_lst_seed = rd();
这里用从函数对象 rd 得到的初始值生成了 my_lst_seed。下面是一个成功生成连续种子的程序:
// Generating a succession of 8 seeds
#include <random>                                // For random_device class
#include <iostream>                              // For standard streams

int main()
{
    std::random_device rd;                         // A function object for generating seeds
    for(size_t n {}; n < 8; ++n)
        std::cout << rd() << " ";
    std::cout << std::endl;
}
这段代码调用 8 次 rd 所表示的函数并输出它所返回的值。运行上述代码两次,得到了下面两行输出:

3638171046 3646201712 2185708196 587272045 1669986587 2512598564 1822700048 3845359386 360481879 3886461477 1775290740 2501731026 161066623 1931751494 751233357 3821236773

可以注意到,两次运行得到的输出是完全不同的。除了 operator()(),random_device 类只定义了其他的 3 个成员函数。成员函数 min() 和 max() 分别返回的是输出的最小和最大可能值。如果是用随机数引擎而不是非确定性数据源实现的,成员函数 entropy() 返回的是将数据源看作 double 或 0 后的熵的估计值。

种子序列

seed_seq 类是用来帮助设置随机数生成器的初始状态的。正如我们看到的那样,可以生成一个随机数生成器,然后通过传入单个种子值到它的构造函数来设置它的初始状态。构造函数的参数也可以是 seed_seq 对象,它可以生成几个 32 位的无符号值,这些值为生成器提供的熵比单个整数多。也可以用 seed_seq 对象生成的值作为几个随机数生成器的种子。

seed_seq 类不仅仅是包含一系列值的简单容器。seed_seq 对象可以根据传入构造函数的一系列整数来生成任意个数的无符号整数值。这些生成的值是通过运用预定义的算法产生的。可以在 seed_seq 构造函数中指定一个或多个整数作为一个序列,或者作为一个初始化列表。不管输入值是如何分布的或者它们有多少个,这些生成的值都会分布到 32 位的无符号整数的全部范围内。对于相同的 seed_seq 构造函数的参数,总是可以得到相同的生成值序列。下面几个句子展示了生成一个 seed_seq 的几种方式:
std::seed_seq seeds1;   // Default object
std::seed_seq seeds2 {2, 3, 4, 5};  // Create from simple integers
std::vector<unsigned int> data {25, 36, 47, 58}; // A vector of integers
std::seed_seq seeds3 {std::begin(data), std::end(data)};
// Create from a range of integers
当然,也可以用 random_device 对象返回的值作为 seed_seq 构造函数的参数:
std::random_device rd {};
std::seed_seq seeds4 {rd(), rd()}; // Create from non-deterministic integers
每次运行这段代码,seed4 对象都会生成不同的值。

通过将两个指定范围的迭代器传给 seed_seq 对象的成员函数 generate(),可以将从 seed_seq 对象得到的给定个数的值保存到容器中。例如:
std::vector<unsigned int> numbers (10); // Stores 10 integers
seeds4.generate(std::begin(numbers), std::end(numbers));
调用 seeds4 的成员函数 generate() 可以保存 numbers 数组中被生成的值。通过一个示例,我们可以看到 seed_seq 对象在不同条件下生成的值的种类:
// Values generated by seed_seq objects
#include <random>                                        // For seed_seq, random_device
#include <iostream>                                      // For standard streams
#include <iterator>                                      // For iterators
#include <string>                                        // For string class
using std::string;

// Generates and list integers from a seed_seq object
void gen_and_list(const std::seed_seq& ss, const string title = "Values:", size_t count = 8)
{
    std::vector<unsigned int> values(count);
    ss.generate(std::begin(values), std::end(values));
    std::cout << title << std::endl;
    std::copy(std::begin(values), std::end(values), std::ostream_iterator<unsigned int>{std::cout, " "});
    std::cout << std::endl;
}

int main()
{
    std::random_device rd {};                                // Non-deterministic source - we hope!
    std::seed_seq seeds1;                                    // Default constructor
    std::seed_seq seeds2 {3, 4, 5};                          // From consecutive integers
    std::seed_seq seeds3 {rd(), rd()};

    std::vector<unsigned int> data {25, 36, 47, 58};            
    std::seed_seq seeds4(std::begin(data), std::end(data));  // From a range
    gen_and_list(seeds1, "seeds1");
    gen_and_list(seeds1, "seeds1 again");
    gen_and_list(seeds1, "seeds1 again", 12);
    gen_and_list(seeds2, "seeds2");
    gen_and_list(seeds3, "seeds3");
    gen_and_list(seeds3, "seeds3 again");
    gen_and_list(seeds4, "seeds4");
    gen_and_list(seeds4, "seeds4 again");
    gen_and_list(seeds4, "seeds4 yet again", 12);
    gen_and_list(seeds4, "seeds4 for the last time", 6);
}
gen_and_list() 是一个用来从 seed_seq 对象生成给定个数的值的辅助函数,并且按照标识标题输出它们。在 main() 中展示了以不同的方式生成的 Seed_seq 对象所生成的值(读者可自行复制代码查看运行结果)。

输出显示了关于 seed_seq 对象生成的值的如下事项:
  • 无论如何生成 seed_seq 对象,都会得到范围广泛的 32 位的整数,甚至由默认构造函数构造的对象生成的值都会超出这个范围。
  • 成员函数 generate() 会生成尽可能多的不同值来填充指定的序列。
  • 可以调用 generate() 任意次数。

成员函数 generate() 在序列中生成的值取决于序列的长度。给定长度的序列将会是完全相同的。不同长度的序列将会包含不同的值。

如果执行这个程序两次,可以看到对于 seed_seq 构造函数,相同的参数会生成相同的值。如果为构造函数提供不同的参数,不同的运行得到的序列是不同的,正如用 rd 函数对象返回的值。

seed_seq 类有两个其他的成员函数。成员函数 size() 会返回用来生成对象的种子值的个数。成员函数 param() 会保存原始种子的值;它期待用一个指定值的目的位置的输出迭代器作为参数,并且没有返回值。param() 会将我们提供的原始种子值保存到迭代器参数所指定的开始位置。下面是一个展示这两个函数如何工作的代码段:
std::seed_seq seeds {3, 4, 5};
std::vector<unsigned int> data(seeds.size()); // Element for each seed value
seeds.param(std::begin(data)); // Stores 3 4 5 in data
这里会用 seeds 对象的成员函数 size() 返回的值来确定生成的 vector 中元素的个数。seeds 的成员函数 param() 会将传给构造函数的 3 个值保存到 data 中。也可以按如下方式将这些值添加到容器中:
seeds.param(std::back_inserter(data));  // Appends 3 4 5 to data
当然,不需要保存这些值——可以传入一个输出流迭代器作为 param() 的参数:
seeds.param (std::ostream_iterator<unsigned int>{std::cout," "}); // 3 4 5 to cout