rand()/srand() 亂數種子原理

Posted on Edited on In Comments:

認識 srand() / rand() 算蠻長的時間了，寫過 C/C++ 的人都知道，他們是 標準 C/C++ 用於產生亂數的函數組合。Ming 這次負責迎新活動上面一個小程式，這個小程式用於將各班級不對齊的人數，自動計算並分配成 n 組(實際上就是做直屬分配 / 共 n 人 j 人一組以某班人數 p 為基準共 n 組)。

迎新活動結束後，無聊又拿程式起來 run run 看，赫然發現一件奇怪的事情，有某個學長連續好幾次的結果都跟 Ming 同組(如果是學妹我可能就沒動力修了)，再看看其它人也有這個狀況，一二年級會變動可是 二、三 年級結果都是相似的，慘了有 bug … 。

有 bug 要修阿，原先以為是我分配邏輯寫錯(首次使用不熟的 2d vector)，查了分配部分的程式碼找了許久還是找不到問題點，結果又把程式 run 了幾次，發現有幾次結果是會改變的，接著我就開始懷疑是不是 srand() / rand() 有問題。

簡單提一下我對直屬分配程式的作法是這樣：

example.Cpp
1
2
3
4
5
6
7
8
9

// STL 容器
vector<vector<wstring> > classVector;

// handleVector() 負責處理 各班人員姓名讀入 / classVector 賦值 / 亂數排序(關鍵 - srand() 寫在 handleVector() 中)
handleVector(fileNameOne,classVector,1);
handleVector(fileNameTwo,classVector,2);
handleVector(fileNameThree,classVector,3);
handleVector(fileNameFour,classVector,4);

我懷疑是函數執行間隔速度過短，間接導致 srand((unsigned int)time(NULL)); 中的 time() 函數抓到的時間是幾乎沒有差異性的(每次傳入的 seed 一樣的話，會導致亂數結果相同)。

我初步的處理方式是在 handleVector() 中加入 Sleep(1000)，讓每次執行函數時延遲 1 秒鐘的時間，重新執行程式後，輸出結果前會先延遲四秒鐘左右Sleep(1000) * 4。

不過大致上得到的結果是正確的 -> 每次的結果都是散的(正確)。

興高采烈的以為修好 bug 之後，跟老師討論了這個結果，結果老師說 srand 的 seed 用 time() 是不適合的做法，回去問了一下資深的網友，他說傳 time() 沒有問題，問我是不是重複 srand() 了 … 這句話有點當頭棒喝的感覺。

handleVector 執行了四次 …，srand() 也重覆跑了四次，也就是說當這四次函數執行時間非常非常短的時候，傳入的 seed 是一樣的。(A秒執行 time() 跟 A秒執行 time() 會讓 time() == time()，也就是說傳入的 seed == seed，導致每次 rand() 結果都是一樣的)

把 srand() 搬到 main() 程式入口點中，程式果然正常了，而且又沒有 Sleep(1000) 延遲四秒鐘才輸出的問題。

只知其然，而不知其所以然 不太好，要了解 srand() 的原理，最快的方法當然是直接看內部實現的代碼了(標準 C++ 的優點之一)。

首先看一下 srand() 的代碼：

srand
1
2
3
4
5

void __cdecl srand (unsigned int seed)
{
    _getptd()->_holdrand = (unsigned long)seed;
}

srand 傳入一個 seed (例如我們傳入 time() 返回值)， _getptd()->_holdrand 將 seed 存到 _holdrand 變數，初始化完成。

接下來看一下 rand() 的代碼：

rand
1
2
3
4
5
6

int __cdecl rand (void)
{
    _ptiddata ptd = _getptd();
    return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) » 16) & 0x7fff );
}

呼叫 rand() 後，會對 _holdrand 變數(存 seed) 做 (((_holdrand * 214013L + 2531011L) » 16) & 0x7fff) 操作，並將這個操作後的值返回，且將這個新的值覆蓋原本的 _holdrand 變數。

一直不理解 rand() 為何被稱作”偽亂數”的原因(之前有測試過，rand() 得出的結果蠻平均的)，看完這兩段應該有豁然開朗的感覺，也就是說其實所謂的 rand() 是透過人為的算法去操控的，並非實際意義上的 “亂數”，不過 rand() 得到的值還算穩定，作為小程式開發還算堪用，

也就是說，如果像我一樣一直 srand ，就會讓 _holdrand 一直被刷新，而當 time() == time() 的時候，會導致下一次 rand() 做 (((_holdrand * 214013L + 2531011L) » 16) & 0x7fff) 操作時，得到一樣的結果。

他的過程有點像是根據傳入的 seed 產生一個無窮大的序列，每次 rand() 就會從中取一個數字出來(當然這個序列實際上是不存在的，便於理解)，而上面兩行程式碼就是產生這個序列的作用程式碼，透過原始數字 A 做第一次計算，後面不斷利用這個數字做一定的運算，得到 A2 A3，由於每次計算後的值都會不同，所以可以保持 rand() 的品質。

重複 srand() 或者 srand(常數) 都會導致這個不斷透過固定計算生成的虛擬序列，變成同一個序列。

例如： A 的內部實現是 a*a 那我連續傳入 A(1) A(1) A(1) 都會得到一樣的結果(rand 的計算方式有異曲同工，也是透過實際運算得出後面的數字，所以稱為偽亂數)。

結論：

這次歸根究底其實是自己對於 srand()/rand() 實際原理沒有實際掌握的原因，才犯了重複 set seed 這種低級的錯誤 …。

經過這次 bug，有更深的體會應該要更加關注程式的細節、隨手可得的原始碼(如果看得懂的話，可以便於了解內部實現)。

一次深刻的經驗，了解程式 bug 的影響，這次幸好問題是發生在學校的小 program，出包最多就是修正問題、重新分配一次，如果是實際專案，出包的話影響的是實際的公平性(有違亂數分配程式的初衷)，那可能接下來就是收到一大堆客訴電話、信函了 …。

P.s. 羨慕 Logdown 的 Markdown 編輯器(昨天文章寫到一半電腦放著去上學，結果回來自己莫名關機了，還有 restore 可以按，超溫馨.__.)，Tumblr 一直沒在 Markdown 編輯器下功夫阿 …(有一些很奇怪的解析問題 …)。