c++隨機數問題研究
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>中。
參考文檔：//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
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>;
輸出結果為：
vec: 85 7 58 8 29 17 60 57 81 71 82 93 4 47 84 40 65 79 37 24 3 14 36 25 32 16 91 48 86 38 63 78 80 28 44 39 34 90 69 13 74 1 77 59 88 41 46 56 33 62 21 18 30 52 89 22 87 27 9 53 70 51 2 72 92 42 26 66 73 97 15 43 31 49 100 68 54 35 12 99 6 67 5 96 94 83 10 45 61 50 23 76 19 98 11 55 75 20 95 64 vec2: 37 51 12 62 99 95 65 1 78 29 80 13 48 72 83 23 25 75 97 68 86 40 24 30 84 4 47 28 76 57 33 38 16 18 69 9 70 31 42 49 52 71 91 96 81 73 34 45 10 26 2 93 89 41 54 64 44 22 36 39 87 43 63 55 3 32 27 19 85 79 35 5 58 11 56 59 21 88 15 100 74 53 8 14 60 92 17 50 7 90 6 20 67 77 98 61 66 82 46 94
尊重技術文章，轉載請註明！
c++隨機數問題研究
