c++亂數問題研究

2021-03-07 22:00:55

1、問題背景

某專案中有個複雜的排序，先是各種規則依次排序，最後如果依然並列的話，那就隨機位置，名次並列。測試中發現一個詭異現象，並列時隨機排序但隨機後2個case列印的順序每次都一樣，亂數沒有起到任何作用。經過分析發現，亂數種子srand(clock())，本意是希望連續呼叫這個函數，給多個亂數設定種子，實際上設定的種子相同，最後產生的亂數是偽亂數。那麼有沒有一種亂數方法可以在較快的迴圈中，保證隨機性呢？

原問題較複雜，給個類似的例子說明具體場景：

void test_random()
{
    vector<int> vec;
    vec.resize(100);
    iota(vec.begin(), vec.end(), 1);
    vector<int> vec2(vec);
    
    srand(clock());
    random_shuffle(vec.begin(), vec.end());
    srand(clock());
    random_shuffle(vec2.begin(), vec2.end());

    int cnt = 0;
    cout << "vec:" << endl;
    for (auto v : vec) { 
        cout << v << "  "; 
        if ((++cnt % 10) == 0) cout << endl;
    }
    cout << endl<< endl;

    cnt = 0;
    cout << "vec2:" << endl;
    for (auto v : vec2) {
        cout << v << "  ";
        if ((++cnt % 10) == 0) cout << endl;
    }
}

輸出結果為：

2、rand()和srand()

rand()和srand()是c函數，在stdlib.h中定義，rand()能產生0--32767範圍的亂數。

如果只使用rand，則每次輸出的亂數都是一樣的，相當於使用srand(1)作為預設種了。如果給定種了，則能產生不同的亂數，所以time或clock函數就是一個好種子，獲取計算機的時間，用秒或毫秒來做亂數種子以產生不同的亂數。但是在某些場景下，會引發下列問題：

問題1：在程式執行較慢或不需要連續產生亂數時，用時鐘當做種子沒有問題，但要快速產生不同的組數的亂數時，就會出現前面出現的現象，較大概率出現相同的亂數。

問題2：如果希望生成某個範圍的亂數，則不好控制，通常會採用取模的方式，而這種方式會破壞亂數的分佈概率。

// 0--10 的亂數
srand((unsigned int)time(NULL));
int r = rand() % 10

// 100--200的亂數
int min = 100;
int max = 200;
srand((unsigned int)time(NULL));
int r = rand() % (max - min) + min
    
// [0--1.0] 浮點數
srand((unsigned int)time(NULL));
float r = rand() % RAND_MAX

3、c++11 亂數

c++11引入了random標頭檔案，可以更加精確的產生亂數，並且提供了完善的操作介面。C++標準規定了亂數設施，包括均勻隨機位生成器（Uniform random bit generators，URBG）和亂數分佈等，定義在<random>中。

參考檔案：http://www.cplusplus.com/reference/random/?kw=random

This library allows to produce random numbers using combinations of generators and distributions:

Generators: Objects that generate uniformly distributed numbers.

Distributions: Objects that transform sequences of numbers generated by a generator into sequences of numbers that follow a specific random variable distribution, such as uniform, Normal or Binomial.

random標準款主要包括：

生成器：生成均勻分佈偽亂數的物件

分佈：將生成器生成的數序列轉換為某種特定數學概率分佈的序列，如均勻分佈、正態分佈、泊松分佈等。

3.1、生成器

1）random_device生成器

C++11提供了一個random_device亂數類，英文叫「Non-deterministic random number generator」，這是一個非確定性亂數生成器，它並不是由某一個數學演演算法得到的隨機序列，而是通過讀取檔案，讀什麼檔案看具體的實現(Linux可以通過讀取/dev/random檔案來獲取)。檔案的內容是隨機的，簡單理解即這個類依靠系統的噪聲產生亂數。

2）偽亂數引擎

偽亂數引擎，實現方式屬於模板類，是使用演演算法根據初始種子生成偽亂數的生成器。

linear_congruential_engine：線性同餘生成引擎，是最常用也是速度最快的，但隨機效果一般
mersenne_twister_engine：梅森旋轉演演算法，隨機效果最好。
subtract_with_carry_engine：滯後Fibonacci演演算法。

亂數引擎需要一個整型引數作為種子，對於給定的單個或多個種子，亂數生成器總會生成相同的序列，這在測試時非常有用。當測試完成，則需要隨機的種子以產出不同的亂數，推薦使用random_device作為亂數種子。

3.2、介面卡

除了生成器模板庫外，c++11還設計了幾種介面卡。

discard_block_engine: Discard-block random number engine adaptor (class template ) independent_bits_engine: Independent-bits random number engine adaptor (class template ) shuffle_order_engine :Shuffle-order random number engine adaptor (class template )

3.3、隨機分佈模板類

亂數引擎產生的亂數值都比較大，使用時經常需要限定到一個範圍內，c++11提供了符合各種概率分佈的亂數生成模板類，比如：均勻分佈，正態分佈，泊松分佈等。

以均勻分佈為例：

template< class IntType = int > class uniform_int_distribution;
template< class RealType = double > class uniform_real_distribution;

測試1：直接使用引擎產生亂數，範圍很大。

random_device rd;
mt19937 g(rd());
for (int n = 0; n < 10; ++n)
{
    cout << g() << " ";
}
/* 輸出
case 1： 
649838310 2697128147 116396177 1728659882 2608399735 1196122003 1824385544 3670102805 2610106284 1577110367
case 2：
2220490604 2877041131 4118289859 1423499548 3901014967 230558428 3106974485 2887363336 1389836600 4020707730
*/

測試2：使用均勻分佈類別範本產生亂數，可以限定生成的亂數的範圍。

random_device rd;
mt19937 g(rd());
uniform_int_distribution<> dis(1, 100);
for (int n = 0; n < 10; ++n)
{
    cout << dis(g) << " ";
}
/* 輸出
case 1：  67 23 61 3 91 88 81 61 57 60
case 2：  51 1 29 75 81 32  8  8 47 5
cae  3:  92 1 22 24 84 20 72 27 66 39
*/

3.4、用法總結

1、定義種子，可以是隨機種子或者固定種子，固定種子方便測試用，但每次產生的亂數都一致。

2、選擇隨機引擎，把種子值傳入當做引數。

3、選擇合適分佈方式，建立隨機分佈物件，可以在此時指定需要的亂數的範圍。

4、把引擎傳入亂數分佈模板類物件，輸出亂數。

4、問題解決

c++ 提供了一個shuffle函數，相比於random_shuffle，shuffle可以指定亂數引擎，如果指定一個非確定性引擎，則能保證連續生成的兩組亂數各不相同，達到設計效果。

template <class _RanIt, class _Urng>
void shuffle(_RanIt _First, _RanIt _Last, _Urng&& _Func)

修改後的測試函數：

void test_random()
{
    vector<int> vec;
    vec.resize(100);
    iota(vec.begin(), vec.end(), 1);
    vector<int> vec2(vec);
    
    auto engine = std::default_random_engine(std::random_device()());
    shuffle(vec.begin(), vec.end(), engine);
    shuffle(vec2.begin(), vec2.end(), engine);
     

    int cnt = 0;
    cout << "vec:" << endl;
    for (auto v : vec) { 
        cout << v << "  "; 
        if ((++cnt % 10) == 0) cout << endl;
    }
    cout << endl<< endl;

    cnt = 0;
    cout << "vec2:" << endl;
    for (auto v : vec2) {
        cout << v << "  ";
        if ((++cnt % 10) == 0) cout << endl;
    }
}

上面例子using default_random_engine = mt19937; 其中，mt19937是一個引擎，最大值為0Xffffffff。

using mt19937 = mersenne_twister_engine<unsigned int, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15,  0xefc60000, 18, 1812433253>;