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

認識 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 編輯器下功夫阿 …(有一些很奇怪的解析問題 …)。