C++ 亂數生成(STL 亂數生成)完全攻略

2020-07-16 10:04:32
在亂數生成方面 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