C++生成隨機數

2020 年 4 月 18 日
筆記
C++, C++11

C++為隨機數提供了兩套工具：C風格的和C++風格的。

C風格

C為隨機數提供的工具是rand、srand和RAND_MAX，定義在<stdlib.h>中。

srand為rand設置種子，如果不設置，相當於調用過srand(1)。rand產生偽隨機數，其範圍為0到RAND_MAX，RAND_MAX至少是32767，在MSVC和GCC中這個值都是32767。

偽隨機數看似隨機，實則是有規律可循的，對於相同的種子值，rand產生的序列完全相同，也就是說無論你給srand一個什麼數字，多次運行程式的結果都將相同——除非你給srand的是不同的數字，比如時間。<time.h>中的time函數返回整數表示的系統時間，可用於設置種子。

如果我們只需要0到9的隨機數，可以把rand的返回值% 10；如果是42到233，可以寫rand() % 192 + 42。下面的random函數封裝了這項工作。注意只有在b - a + 1遠小於或整除RAND_MAX時隨機數的分布才比較均勻。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int random(int a, int b)
{
    return rand() % (b - a + 1) + a;
}

int main()
{
    srand(time(NULL));
    printf("RAND_MAX = %d\n", RAND_MAX);
    for (int i = 0; i < 10; i++)
        printf("%d ", rand());
    printf("\n");
    int count[10] = {0};
    for (int i = 0; i < 10000; i++)
        count[random(0, 9)]++;
    for (int i = 0; i < 10; i++)
    {
        printf("%d: ", i);
        for (int j = 0; j < count[i] / 10; j++)
            printf("*");
        printf("\n");
    }
}

C++風格

從C++11開始，C++標準規定了隨機數設施，包括均勻隨機位生成器（Uniform random bit generators，URBG）和隨機數分布等，定義在<random>中。

URBG分為隨機數引擎、引擎適配器、預置隨機數生成器和非確定隨機數生成器4類，通常後兩類就夠用了。

標準規定了3種隨機數引擎：

線性同餘linear_congruential_engine（LCG），時間空間消耗都少；
梅森旋轉mersenne_twister_engine（MT），佔用較多記憶體（在PC上可以忽略），計算量較大；
帶進位減法（屬於滯後斐波那契生成器，LFG）subtract_with_carry_engine，性能與效果折中。

隨機數引擎都需要一個種子，生成的都是偽隨機數。

引擎適配器可以套一個隨機數引擎：

discard_block_engine在連續若干個偽隨機數中選擇若干個；
independent_bits_engine把位數多的偽隨機數壓縮成位數少的；
shuffle_order_engine把連續若干個偽隨機數重排。

套娃的方式是模板，理論上你還可以用適配器套適配器，不過CPU可能會有意見。

隨機數引擎的模板參數怎麼取？標準定義了一些數學家們發現的效果良好的隨機數引擎：LCG minstd_rand0、minstd_rand、knuth_b；MT mt19937、mt19937_64；LFG ranlux24_base、ranlux48_base、ranlux24、ranlux48。如果你還是無從下手，那就用default_random_engine，編譯器的開發者們為你選好了他們認為最合適的，在MSVC中是mt19937，在GCC中是minstd_rand0。

以上工具都生成偽隨機數，標準還定義了真·隨機數引擎random_device，儘管標準也允許它是偽隨機的。如果它是真隨機的，那麼使用起來它的效果無疑是最好的，但是多次調用後性能會急劇下降，通常只用於生成偽隨機數引擎的種子。

隨機數生成器類型都定義了靜態方法min和max，返回生成的隨機數的範圍，以及無參數的函數調用運算符operator()，返回隨機數。

#include <iostream>
#include <random>

int main()
{
    auto engine = std::default_random_engine(std::random_device()());
    std::cout << "min = " << engine.min() << "; max = " << engine.max() << std::endl;
    std::cout << "random numbers: ";
    for (int i = 0; i != 10; ++i)
        std::cout << engine() << ' ';
    std::cout << std::endl;
}

大多數情況下我們不需要min到max範圍的整數，而需要一定分布的整數或實數。標準規定了許多隨機數分布類型，我數學不好，不太懂這些。

均勻分布uniform_int_distribution、uniform_real_distribution；
伯努利分布bernoulli_distribution、binomial_distribution、negative_binomial_distribution、geometric_distribution；
泊松分布poisson_distribution、exponential_distribution、gamma_distribution、weibull_distribution、extreme_value_distribution；
正態分布normal_distribution、lognormal_distribution、chi_squared_distribution、cauchy_distribution、fisher_f_distribution、student_t_distribution；
抽樣分布discrete_distribution、piecewise_constant_distribution、piecewise_linear_distribution。

構造分布實例時傳入分布的參數。調用operator()獲得結果，參數為隨機數引擎。

#include <iostream>
#include <random>
#include <string>

int main()
{
    auto engine = std::default_random_engine(std::random_device()());
    std::uniform_int_distribution<int> uniform(0, 9);
    int count[10] = {0};
    for (int i = 0; i != 10000; ++i)
        ++count[uniform(engine)];
    for (int i = 0; i != 10; ++i)
        std::cout << i << ": " << std::string(count[i] / 10, '*') << std::endl;
}

注意，與STL中左閉右開的習慣不同，uniform_int_distribution構造函數接受的參數是閉區間。

Tags: C++ C++11