隨機(jī)數(shù)漫談
隨機(jī)數(shù)對(duì)程序設(shè)計(jì)來(lái)說(shuō)很重要，今天就從幾方面探討下一些常見(jiàn)的隨機(jī)數(shù)相關(guān)的問(wèn)題。
本文只討論整數(shù)相關(guān)的隨機(jī)數(shù)，另外需要你對(duì)概率論有最基本的了解（至少知道古典概型是什么）。
本文索引
如何從rand7生成rand5
首先是和某個(gè)知名算法題相反的問(wèn)題。
這里給定一個(gè)可以概率均等地生成0到6的隨機(jī)數(shù)生成器，要求用這個(gè)生成器創(chuàng)造出能概率均等地生成0到4的隨機(jī)數(shù)生成器。
有人可能會(huì)立刻給出這樣的答案：
func rand5() int {
return rand7() % 5
}
然而這個(gè)答案只滿足了輸出的范圍在0到4，不滿足概率均等，所以不正確。這種時(shí)候列表法的作用就顯現(xiàn)出來(lái)了：
| rand7的輸出 | rand7 % 5 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 0 |
| 6 | 1 |
發(fā)現(xiàn)問(wèn)題了嗎，0和1出現(xiàn)了兩次，它們出現(xiàn)的概率是其他數(shù)字的兩倍，因此概率分布并不均等。
通過(guò)列表法我們其實(shí)也發(fā)現(xiàn)了這個(gè)問(wèn)題真正的解法：除掉5和6的話剩下的輸出不僅符合要求概率也是均等的，所以代碼會(huì)變成這樣：
func rand5() int {
n := rand7()
for n >= 5 {
n = rand7()
}
return n
}
上面的代碼其實(shí)就是隨機(jī)采樣算法中非常重要的一種：拒絕采樣。同樣上面的rand7生成rand5也可以歸類成一大類問(wèn)題：給定一組滿足規(guī)律或者特征是g(x)的樣本，現(xiàn)在需要從這些樣本中篩選出或者生成另一組滿足特征是f(x)的樣本。解決這類問(wèn)題的算法很多，而拒絕采樣是比較直觀的：判斷g(x)的樣本是否符合要求，不符合的就排除取下一個(gè)樣本，符合要求的就歸類到滿足f(x)的樣本集合中。
按照這個(gè)角度來(lái)看，上面的問(wèn)題可以劃分為幾個(gè)基本元素：
- g(x)：rand7
- f(x): rand5
- 需要拒絕的樣本：大于等于5的整數(shù)
拒絕采樣在大多數(shù)時(shí)間都能獲得理想的結(jié)果，但還有采樣率需要注意。采樣率就是g(x)的樣本中有多少可以被接受，采樣率太低的時(shí)候意味著算法的效率也會(huì)非常低。所以我們簡(jiǎn)單算算rand5的采樣率，是七分之五，大約70%。這個(gè)概率不大不小，勉強(qiáng)合適。
當(dāng)采樣率過(guò)低的時(shí)候要么得改變拒絕采樣的標(biāo)準(zhǔn)或范圍，要么就不能再使用拒絕采樣了。
go標(biāo)準(zhǔn)庫(kù)的做法
標(biāo)準(zhǔn)庫(kù)里當(dāng)然不會(huì)有rand5和rand7，但它提供了一個(gè)叫Int63n的函數(shù)，它解決的問(wèn)題是如何從均勻分布在[0, 2??)范圍上的隨機(jī)整數(shù)中生成均勻分布在范圍[0, n)上的隨機(jī)整數(shù)。換句話說(shuō)，雖然范圍不一樣了，但還是同一個(gè)問(wèn)題。
我們肯定不能像上面那樣把大于等于n的樣本全丟了，因?yàn)???包含至少1844京（1E16）個(gè)整數(shù)樣本，這會(huì)帶來(lái)低得無(wú)法接受的采樣率。
但因?yàn)槲覀兪怯胢od來(lái)選擇范圍內(nèi)的隨機(jī)數(shù)的，因此我們可以選擇n的倍數(shù)，這個(gè)證明太簡(jiǎn)單了，列表法加歸納就行。或者還可以這么想，有一個(gè)整數(shù)常數(shù)C，x % n和Cx % n能產(chǎn)生的輸出的種類和它們的數(shù)量都是完全相同的，所以如果樣本能均勻分布在[0, n)的范圍上，那么范圍[0, C·n]只不過(guò)是[0, n)重復(fù)了C次，所以樣本在每一段上都是均勻分布的，整個(gè)合起來(lái)的區(qū)間上也是均勻的。
有了常數(shù)C，這樣使得我們可以盡可能地讓更多的樣本被采樣，這樣能降低重試的次數(shù)。
C其實(shí)也很好選擇，取一個(gè)2??內(nèi)的n的最大的倍數(shù)就行，如果C本身能被2??整除，那么C就是2??/n。
所以標(biāo)準(zhǔn)庫(kù)是這樣寫(xiě)的:
func (r *Rand) Int63n(n int64) int64 {
if n <= 0 {
panic("invalid argument to Int63n")
}
if n&(n-1) == 0 { // n is power of two, can mask
return r.Int63() & (n - 1)
}
max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
v := r.Int63()
for v > max {
v = r.Int63()
}
return v % n
}
代碼還是很簡(jiǎn)單的，超過(guò)C·n的樣本全部拒絕采樣，剩下的樣本就能保證在mod n的時(shí)候獲得分布均勻的隨機(jī)整數(shù)了。
采樣率是多少？我們可以利用拒絕率來(lái)反推，這里拒絕率還挺好算的，就是(1<<63)%uint64(n)，算下來(lái)拒絕了少的時(shí)候是百億分之一，多的時(shí)候是數(shù)千萬(wàn)分之一——都很低，基本上大多數(shù)時(shí)間最多兩次重試就能獲得想要的結(jié)果了。
但作為標(biāo)準(zhǔn)庫(kù)，它的性能還不夠，尤其是go的編譯優(yōu)化非常弱的現(xiàn)實(shí)下，更需要高效的算法彌補(bǔ)。問(wèn)題出在哪？首先不是采樣率，這個(gè)采樣率是足夠的，問(wèn)題出在它需要兩次64位除法，除法運(yùn)算相比其他運(yùn)算比如右移要慢很多，何況還是兩次，別的語(yǔ)言中的標(biāo)準(zhǔn)庫(kù)采用的算法只需要0到1次除法就夠了。
好在go提供了math/rand/v2，采用了更高效的算法。
新算法依舊基于拒絕采樣，但對(duì)采樣的范圍進(jìn)行了變更，具體是這樣的：
- 依然用概率均等的rand64生成一個(gè)隨機(jī)整數(shù)x
- 現(xiàn)在把
x*n，這樣生成的值的范圍是[0, n·2??) - 因?yàn)槭菍?duì)已有范圍的等比擴(kuò)大，所以
x*n在[0, n·2??)依舊是均勻分布的（不過(guò)要注意，范圍擴(kuò)展了，但樣本的總量不變還是2??個(gè)） [0, n·2??)可以均等分成n個(gè)范圍，分別是[0, 2??),[2??, 2*2??),[2*2??, 3*2??)...[(n-1)*2??, n*2??)- 這樣每一個(gè)均等分割的范圍整除以2??就可以得到一個(gè)整數(shù)k，k一定在
[0, n)內(nèi) - k可以當(dāng)作符合要求的結(jié)果，而整除以2??實(shí)際上可以轉(zhuǎn)換成位運(yùn)算，這樣除法運(yùn)算可以減少一次。
新算法有幾個(gè)問(wèn)題，第一個(gè)是x*n在大多數(shù)情況下會(huì)超過(guò)2??，但這不用擔(dān)心，因?yàn)間o提供了高性能128位整數(shù)運(yùn)算。
第二個(gè)是x*n雖然在[0, n·2??)均勻分布，但我們?cè)趺幢ＷC在均等分割的每個(gè)[(k-1)*2??, k*2??)上也是均等分布的呢？
答案是如果只有上面寫(xiě)的六個(gè)步驟，我們保證不了。原因是因?yàn)橐氡ＷCx*n均勻分布在每個(gè)[(k-1)*2??, k*2??)上，我們就要保證x本身要均勻分布在[(k-1)*(2??/n), k*(2??/n))上，換人話說(shuō)，就是把2??分割成n份，每份里的樣本數(shù)量都要一致。因?yàn)槲覀兊臉颖径际钦麛?shù)而不是實(shí)數(shù)，所以動(dòng)動(dòng)腳趾就能想到很多數(shù)是不能整除2??的，因此會(huì)留下“余數(shù)”。但我們的新算法實(shí)際上假設(shè)了x均勻分布在2??分割出來(lái)的均等的范圍內(nèi)。不能整除的情況下意味著即使按最均勻的辦法分割，也會(huì)存在一部分范圍比其他的范圍多幾個(gè)樣本或者少幾個(gè)樣本，會(huì)多還是會(huì)少取決與你對(duì)2??/N取整的方式。
但這問(wèn)題不大，通常分段直接的數(shù)量差異對(duì)概率產(chǎn)生的誤差非常小，比如我們把n取6，按盡可能均勻的分割，就存在4個(gè)分段比剩下的分段里的樣本總數(shù)多1個(gè)，但每個(gè)分段的樣本數(shù)量都有超過(guò)3E18個(gè)，多一個(gè)還是多兩個(gè)帶來(lái)的影響幾乎可以忽略不計(jì)。
然而標(biāo)準(zhǔn)庫(kù)最重要的是要保證結(jié)果的正確性，即使可能性是3E18分之一，它依舊不是0，函數(shù)的實(shí)現(xiàn)是不正確的，更何況根據(jù)n的選擇，n越大分段的樣本數(shù)量越少，分段之間數(shù)量差異帶來(lái)的影響就會(huì)越來(lái)越大，總有一個(gè)n能讓結(jié)果的誤差大到無(wú)法忽略。
問(wèn)題其實(shí)也好解決，因?yàn)槲覀冎朗冀K會(huì)有一些分組的樣本是多余的，我們只要保證分組里的樣本數(shù)量一致就行，不需要關(guān)心具體剔除的樣本是什么。假設(shè)我們采用向下取整的辦法，那么會(huì)存在一些理論上應(yīng)該在分段k上的樣本跑到k+1的分組上，這些樣本通常分布在分段的起始位置上，我們可以把這些樣本拒絕采樣，這樣比較容易實(shí)現(xiàn)。這些樣本乘以n之后會(huì)落在[k*2??, k*2??+(2??%n))上。
剔除這些樣本后，我們就能保證x*n在每個(gè)[(k-1)*(2??/n), k*(2??/n))上都是均勻分布的了。
思路理解了看代碼也就不難了：
func (r *Rand) uint64n(n uint64) uint64 {
if is32bit && uint64(uint32(n)) == n {
return uint64(r.uint32n(uint32(n)))
}
if n&(n-1) == 0 { // n is power of two, can mask
return r.Uint64() & (n - 1)
}
hi, lo := bits.Mul64(r.Uint64(), n)
if lo < n {
thresh := -n % n // 2?? % n 的簡(jiǎn)化形式
for lo < thresh {
hi, lo = bits.Mul64(r.Uint64(), n)
}
}
return hi
}
精髓在于利用(x*n) >> 64來(lái)避免了x % n帶來(lái)的除法運(yùn)算。而且新算法不用一開(kāi)始就算余數(shù)，因此運(yùn)氣好的時(shí)候可以一次除法都不做。
還有一個(gè)小疑問(wèn)，128位乘法夠了嗎？肯定夠了，因?yàn)閚最大也只能取到2??，這意味這x*n的范圍最大也只到[0, 2??·2??)，128位乘法剛好夠用。
最后做下性能測(cè)試，標(biāo)準(zhǔn)庫(kù)里已經(jīng)提供了，在我的10代i5上舊算法一次調(diào)用需要18ns，新算法只需要5ns，兩者使用的隨機(jī)數(shù)發(fā)生器是一樣的，因此可以說(shuō)新算法快了3倍，提升還是很可觀的。
從rand5生成rand7
上一節(jié)討論了從更大的樣本空間里篩選出特定特征的子集，這一節(jié)我們反過(guò)來(lái)：從范圍更小的樣本空間里派生出有某一特征的超集。
同時(shí)，這也是一道常見(jiàn)的中等難度的算法題。
首先要考慮的是如何把受限的樣本空間盡量擴(kuò)張。上一節(jié)我們用乘法來(lái)擴(kuò)展了樣本分布的范圍，然而乘法尤其是乘以常數(shù)是沒(méi)法增加樣本數(shù)量的，因此這個(gè)做法只能pass。加法可以平移樣本的范圍，但也不能增加樣本總量，而且我們需要樣本空間是[0, x)平移之后起點(diǎn)都變了，因此也不行。
那剩下的可行的也最穩(wěn)定的辦法是rand5() * rand5()。它像乘法一樣能擴(kuò)張樣本的范圍，同時(shí)因?yàn)椴皇浅艘猿?shù)因此還有機(jī)會(huì)產(chǎn)生新的樣本。我們列個(gè)表看看：
| rand5 | rand5 | rand5 * rand5 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 2 | 0 |
| 0 | 3 | 0 |
| 0 | 4 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| 1 | 2 | 2 |
| 1 | 3 | 3 |
| 1 | 4 | 4 |
| 2 | 0 | 0 |
| 2 | 1 | 2 |
| 2 | 2 | 4 |
| 2 | 3 | 6 |
| 2 | 4 | 8 |
| 3 | 0 | 0 |
| 3 | 1 | 3 |
| 3 | 2 | 6 |
| 3 | 3 | 9 |
| 3 | 4 | 12 |
| 4 | 0 | 0 |
| 4 | 1 | 4 |
| 4 | 2 | 8 |
| 4 | 3 | 12 |
| 4 | 4 | 16 |
確實(shí)有新樣本出現(xiàn)了，但不夠連續(xù)，比如沒(méi)有7和10。因此這條路是不通的。
這時(shí)候就要上原汁原味的拒絕采樣算法了，我們使用5 * rand5 + rand5：
| rand5 | rand5 | 5 * rand5 + rand5 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 2 | 2 |
| 0 | 3 | 3 |
| 0 | 4 | 4 |
| 1 | 0 | 5 |
| 1 | 1 | 6 |
| 1 | 2 | 7 |
| 1 | 3 | 8 |
| 1 | 4 | 9 |
| 2 | 0 | 10 |
| 2 | 1 | 11 |
| 2 | 2 | 12 |
| 2 | 3 | 13 |
| 2 | 4 | 14 |
| 3 | 0 | 15 |
| 3 | 1 | 16 |
| 3 | 2 | 17 |
| 3 | 3 | 18 |
| 3 | 4 | 19 |
| 4 | 0 | 20 |
| 4 | 1 | 21 |
| 4 | 2 | 22 |
| 4 | 3 | 23 |
| 4 | 4 | 24 |
沒(méi)錯(cuò)，正好產(chǎn)生了均等分布的0到24的整數(shù)。很神奇吧，其實(shí)想明白為什么不難。我們先看5 * rand5，這樣或產(chǎn)生0、5、10、15、20這五個(gè)數(shù)字，我們要想有機(jī)會(huì)生成連續(xù)的整數(shù)，就一定需要把缺少的1到4，11到14這些數(shù)字補(bǔ)上。這時(shí)候正巧一個(gè)+ rand5就可以把這些缺的空洞全部填上。當(dāng)然用進(jìn)位來(lái)理解會(huì)更簡(jiǎn)單。
總結(jié): n * randn + randn可以產(chǎn)生連續(xù)的范圍在[0, n*n)的均勻分布的整數(shù)。注意這里沒(méi)有結(jié)合律，因?yàn)閞andn每次的結(jié)果都是不一樣的
這個(gè)樣本空間是遠(yuǎn)超rand7的要求的，因此現(xiàn)在問(wèn)題回到了第一節(jié)：如何從rand25生成rand7？現(xiàn)在大家都知道了：
func rand7() int {
x := 5*rand5() + rand5()
max := 25 - 25%7
for x >= max {
x = 5*rand5() + rand5()
}
return x % 7
}
你也可以改寫(xiě)成上一節(jié)說(shuō)的更高效的做法。
充分利用每一個(gè)bit
rand.Uint64()返回的隨機(jī)數(shù)有足足64bits，而我們通常不需要這么大的隨機(jī)數(shù)，舉個(gè)例子，假如我們只需要0到15的隨機(jī)數(shù)，這個(gè)數(shù)字只需要4bits就夠了，如果用rand.Uint64N(16)來(lái)生成，我們會(huì)浪費(fèi)掉60bits的數(shù)據(jù)。
為啥這么說(shuō)？因?yàn)?code>rand.Uint64()保證能概率均等的生成[0, 2??)范圍內(nèi)的整數(shù)，這其實(shí)說(shuō)明了兩件事，第一是這個(gè)隨機(jī)數(shù)的每一個(gè)bit也都是隨機(jī)的，這個(gè)很明顯；第二個(gè)是每個(gè)bits是0還是1的概率也是均等的，這個(gè)可以靠列表加歸納法得出。我們來(lái)看看第二點(diǎn)這么證明。
先假設(shè)我們有一個(gè)能均勻生成[0, 8)范圍內(nèi)數(shù)字的隨機(jī)數(shù)發(fā)生器，現(xiàn)在我們看看所有可能的情況：
| 生成的數(shù)字 | 二進(jìn)制表示 | 從左到右第一位 | 從左到右第二位 | 從左到右第三位 |
|---|---|---|---|---|
| 0 | 000 | 0 | 0 | 0 |
| 1 | 001 | 0 | 0 | 1 |
| 2 | 010 | 0 | 1 | 0 |
| 3 | 011 | 0 | 1 | 1 |
| 4 | 100 | 1 | 0 | 0 |
| 5 | 101 | 1 | 0 | 1 |
| 6 | 110 | 1 | 1 | 0 |
| 7 | 111 | 1 | 1 | 1 |
不難注意到，三個(gè)bit各有八種輸出，0占四種，1占剩下四種，0和1的概率均等。這個(gè)結(jié)論能推廣到任意的[0, 2^n)范圍上。
同樣，基于這個(gè)結(jié)論，我們還能得到這樣一個(gè)結(jié)論，任意連續(xù)的n個(gè)bit，都能產(chǎn)生均勻分布在[0, 2^n)上的隨機(jī)數(shù)，這個(gè)證明太簡(jiǎn)單了，所以我們集中注意力就行了。
現(xiàn)在回頭看看為什么我說(shuō)會(huì)浪費(fèi)60bits，因?yàn)楦鶕?jù)上面的結(jié)論，我們64位的隨機(jī)整數(shù)完全可以按每四位劃分一次，這樣可以分成16組，而每組正好能產(chǎn)生[0, 16)范圍內(nèi)的隨機(jī)數(shù)，且概率同樣的均等的。也就是說(shuō)一次rand.Uint64()理論上應(yīng)該可以產(chǎn)生16個(gè)我們需要的隨機(jī)數(shù)，但實(shí)際上我們只生成了一個(gè)。這里就有很大的提升空間了。
怎么做呢？我們需要一點(diǎn)位運(yùn)算，把64位整數(shù)分組四位一組：
n := rand.Uint64()
mask := uint64(0xf) // 0b1111
for i := range 10 {
a[i] = int(n & mask) // 只讓最右邊四位有效（書(shū)寫(xiě)順序的右邊，這里不討論大小端了因?yàn)檎f(shuō)明起來(lái)太麻煩）
n >>= 4 // 把剛剛使用過(guò)的四位去掉
}
代碼很簡(jiǎn)單，下面看看性能測(cè)試：
// 不要這樣寫(xiě)代碼
// 我這么做是為了避免內(nèi)存分配和回收會(huì)對(duì)測(cè)試產(chǎn)生不必要的雜音
func getRand(a []int) {
if len(a) < 10 {
panic("length wrong")
}
for i := range 10 {
a[i] = int(rand.Int32N(16))
}
}
// 不要這樣寫(xiě)代碼
// 我這么做是為了避免內(nèi)存分配和回收會(huì)對(duì)測(cè)試產(chǎn)生不必要的雜音
func getRandSplit(a []int) {
if len(a) < 10 {
panic("length wrong")
}
n := rand.Uint64()
mask := uint64(0xf)
for i := range 10 {
// 這里不需要mod
a[i] = int(n & mask)
n >>= 4
}
}
func BenchmarkGetRand(b *testing.B) {
var a [10]int
for range b.N {
getRand(a[:])
}
}
func BenchmarkGetRandSplit(b *testing.B) {
var a [10]int
for range b.N {
getRandSplit(a[:])
}
}
測(cè)試結(jié)果：
goos: windows
goarch: amd64
pkg: benchrand
cpu: Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
BenchmarkGetRand-8 15623799 79.31 ns/op 0 B/op 0 allocs/op
BenchmarkGetRandSplit-8 100000000 11.18 ns/op 0 B/op 0 allocs/op
充分利用每一個(gè)bit之后我們的性能提升了整整6倍。
到目前為止還不錯(cuò)，如果你不在乎生成的隨機(jī)數(shù)的概率分布或者你只想生成[0, 2^n)范圍的隨機(jī)數(shù)且這個(gè)n可以整除64，那么可以直接跳到下一節(jié)繼續(xù)看了。
接著往下看的人肯定是希望不管在什么范圍內(nèi)都能生成概率均勻的隨機(jī)數(shù)且盡量多利用已生成的隨機(jī)bits的。但事情往往不盡人意，比如，[0, 13)和[0, 7)就是兩個(gè)例子。前者右邊界不是2的冪，后者雖然是2的冪但3不能整除64。
我們先從簡(jiǎn)單的問(wèn)題開(kāi)始解決，[0, 13)。受先表示數(shù)字12至少得用4個(gè)bit，4能整除64，所以我們還可以每4個(gè)連續(xù)的bit分割成一組，但這時(shí)概率分布均勻的條件是滿足不了的。無(wú)法保證的原因很簡(jiǎn)單，和我們第一節(jié)里說(shuō)的“rand7生成rand5”的情況一樣，每個(gè)均勻分割出來(lái)的一組連續(xù)的bits的組合里有我們不需要的樣本存在。處理這個(gè)情況的方法在第一節(jié)里已經(jīng)有表述了，那就是拒絕采樣。確定拒絕的范圍也使用第一節(jié)說(shuō)到的辦法，注意到每一組bits能生成[0, 16)的隨機(jī)數(shù)，再考慮到13本身是素?cái)?shù)，這里只需要簡(jiǎn)單地把≥13的樣本全部剔除即可。
所以代碼變成了下面這樣：
func getRandSplit(a []int) {
if len(a) < 10 {
panic("length wrong")
}
mask := uint64(0xf)
count := 0
for {
n := rand.Uint64()
for i := 0; i < 16; i++ {
sample := int(n & mask)
n >>= 4
// 不符合要求后直接跳到下一組去
if sample >= 13 {
continue
}
// 這里也不需要mod
a[count] = sample
count++
if count >= 10 {
return
}
}
}
}
如果一組不滿足采樣要求，我們就跳過(guò)直接去下一組，因此有可能16組里無(wú)法獲得足夠的隨機(jī)數(shù)，因此我們得重新獲取一次64位的隨機(jī)數(shù)，然后再次進(jìn)入分割計(jì)算。這么做會(huì)對(duì)性能產(chǎn)生一點(diǎn)點(diǎn)負(fù)面影響，但依舊很快：
goos: linux
goarch: amd64
pkg: benchrand
cpu: Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
BenchmarkGetRand-8 16242730 72.22 ns/op 0 B/op 0 allocs/op
BenchmarkGetRandSplit-8 37794038 31.81 ns/op 0 B/op 0 allocs/op
這時(shí)候性能就只提升了一倍。
上面那種情況還是最簡(jiǎn)單的，但[0, 7)就不好辦了。首先表示6需要至少3個(gè)bit，而3不能整除64，其次6也不是2的冪。這個(gè)怎么處理呢？
有兩個(gè)辦法，核心思想都是拒絕采樣，但拒絕的范圍有區(qū)別。
第一個(gè)想法是，既然3不能整除64，那我們選個(gè)能被3整除的，這里是63，也就是說(shuō)超過(guò)2?3-1的樣本全部丟棄，然后把符合要求的樣本按每連續(xù)的3bits進(jìn)行分割。這樣我們先保證了3bits分割出來(lái)的每一組都能均等的生成[0, 8)范圍內(nèi)的隨機(jī)整數(shù)。現(xiàn)在問(wèn)題轉(zhuǎn)化成了“rand8怎么生成rand7”，這題我們會(huì)做而且做了好多回了，最終代碼會(huì)是這樣：
func getRandSplit(a []int) {
if len(a) < 10 {
panic("length wrong")
}
// 注意，mask現(xiàn)在只要三位也就是0b111了
mask := uint64(0x7)
count := 0
for {
n := rand.Uint64()
// 先拒絕大于2?3-1的樣本
if n > 1<<63-1 {
continue
}
for i := 0; i < 21; i++ {
sample := int(n & mask)
n >>= 3
// 一組bits如果組合出來(lái)的數(shù)大于等于7也拒絕采樣
if sample > 6 {
continue
}
// 這里是不用mod的，因?yàn)楫a(chǎn)生的sample本身只會(huì)在0-6之間
a[count] = sample
count++
if count >= 10 {
return
}
}
}
}
代碼變得很長(zhǎng)也很復(fù)雜，而且需要兩步拒絕采樣，相對(duì)的我們一次也能分割出21組，比4bits的時(shí)候多了5組，所以難說(shuō)性能下降還是不變，因此我們看看測(cè)試：
goos: linux
goarch: amd64
pkg: benchrand
cpu: Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
BenchmarkGetRand-8 16500700 73.77 ns/op 0 B/op 0 allocs/op
BenchmarkGetRandSplit-8 31098928 39.54 ns/op 0 B/op 0 allocs/op
確實(shí)慢了一些，但總體上還是提速了85%。
第二種想法只需要一步拒絕采樣，既然3不能整除64，那么就找到一個(gè)離3最近的可以整除64且大于3的整數(shù)。在這里我們可以直接注意到4符合條件，實(shí)際開(kāi)發(fā)中如果要找到任意符合條件的數(shù)，可以依賴一下線性探測(cè)。現(xiàn)在我們按連續(xù)的4位把64位隨機(jī)整數(shù)分割，這樣分割出來(lái)的每一組可以生成均勻分布在[0, 16)上的整數(shù)。然后問(wèn)題變成了“從rand16生成rand7”。代碼這樣寫(xiě)：
func getRandSplit2(a []int) {
if len(a) < 10 {
panic("length wrong")
}
mask := uint64(0xf)
count := 0
for {
n := rand.Uint64()
for i := 0; i < 16; i++ {
sample := int(n & mask)
n >>= 4
if sample > 13 {
continue
}
// mod不能漏了，因?yàn)槲覀儠?huì)產(chǎn)生大于等于7的結(jié)果
a[count] = sample % 7
count++
if count >= 10 {
return
}
}
}
}
代碼簡(jiǎn)單了，也只需要一步拒絕采樣就行，但問(wèn)題在于每一組的生成范圍變大導(dǎo)致我們不得不使用取模操作。看看性能怎么樣：
goos: linux
goarch: amd64
pkg: benchrand
cpu: Intel(R) Core(TM) i5-10200H CPU @ 2.40GHz
BenchmarkGetRand-8 16451838 75.86 ns/op 0 B/op 0 allocs/op
BenchmarkGetRandSplit-8 30802065 39.15 ns/op 0 B/op 0 allocs/op
BenchmarkGetRandSplit2-8 38995390 30.75 ns/op 0 B/op 0 allocs/op
想法2比想法1快了近20%，看來(lái)兩步拒絕采樣成了硬傷，不僅僅是因?yàn)槎喃@取幾次64位隨機(jī)數(shù)更慢，多出來(lái)的一個(gè)if還可能會(huì)影響分支預(yù)測(cè)，即便最后我們多了5組可以采樣也無(wú)濟(jì)于事了。
所以，當(dāng)你需要的隨機(jī)數(shù)范圍比較有限的時(shí)候，充分利用每一個(gè)bit是非常理想的性能提升手段。
帶有權(quán)重的隨機(jī)數(shù)
討論了半天概率均勻分布的情況，但業(yè)務(wù)中還有一種常見(jiàn)場(chǎng)景：一組樣本進(jìn)行采樣，既要有隨機(jī)性，又要樣本之間在統(tǒng)計(jì)上盡量滿足某些比例關(guān)系。
這個(gè)場(chǎng)景我想大家最先想到的應(yīng)該是抽獎(jiǎng)。是的沒(méi)錯(cuò)，這是帶權(quán)重隨機(jī)數(shù)的常見(jiàn)應(yīng)用。但還有一個(gè)場(chǎng)景，一個(gè)負(fù)載均衡器連接著一組權(quán)重不同的服務(wù)器硬件，現(xiàn)在想要盡量按權(quán)重來(lái)分配鏈接，這時(shí)候帶權(quán)重隨機(jī)數(shù)就有用武之地了。
假設(shè)我們有樣本(1, 2, 3, 4)四個(gè)整數(shù)，然后要按1:2:3:4的比例來(lái)隨機(jī)生成樣本，該怎么做呢？
按比例，我們可以得到1，2，3，4生成的概率是0.1，0.2，0.3，0.4，這些概率加起來(lái)是一定等于1的，所以我們不妨來(lái)想象有一個(gè)數(shù)軸上的0到1的區(qū)間，然后我們把這些比例“塞進(jìn)”數(shù)軸里：
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
|_______________________|
4
|_____|
1
|_________________|
3
|___________|
2
我故意打亂了順序，實(shí)際上順序并不影響結(jié)果。每個(gè)樣本可以有一個(gè)數(shù)軸上的范圍，范圍的長(zhǎng)度之間也是符合比重的，因此當(dāng)存在一個(gè)可以均勻生成[0, 1)之間所有實(shí)數(shù)的隨機(jī)數(shù)生成器時(shí)，這個(gè)生成器生成的數(shù)落在哪個(gè)范圍里，我們就選擇生成這個(gè)范圍對(duì)應(yīng)的樣本，舉個(gè)例子，如果生成的實(shí)數(shù)落在[0.0, 0.4)這個(gè)區(qū)間里，那么就生成樣本“4”，如果落在[0.8, 1.0)這個(gè)區(qū)間，就生成“2”。這樣帶權(quán)重的隨機(jī)數(shù)就生成了。這個(gè)看上面那個(gè)圖還是挺好理解的，我就不費(fèi)筆墨去證明了。
但我不是很想用這個(gè)方法。為啥呢，因?yàn)槟憧吹搅耍瑓^(qū)間的左邊是閉合的，這意味著要做浮點(diǎn)數(shù)的等值比較，雖然很簡(jiǎn)單，但我很懶不想多寫(xiě)，而且浮點(diǎn)數(shù)沒(méi)法精確表示所有情況的比例導(dǎo)致我們區(qū)間的兩端都有精度損失，這就需要考慮誤差率，雖然通常這點(diǎn)精度損失帶來(lái)的誤差可以忽略不記（尤其是在統(tǒng)計(jì)意義上）但只是考慮到這點(diǎn)我就渾身難受了。
所以我要找一種不需要浮點(diǎn)數(shù)的解決方案。想出來(lái)其實(shí)不難，假設(shè)我們有0到9的整數(shù)，正好10個(gè)，現(xiàn)在樣本“1”按比例需要占用其中1個(gè)樣本，樣本“4”按比例要占用其中四個(gè)樣本，現(xiàn)在我們獲得了一個(gè)能均勻生成0到9的整數(shù)的隨機(jī)數(shù)生成器，那只要生成的隨機(jī)數(shù)正好是樣本“4”占用的那幾個(gè)隨機(jī)數(shù)我們就生成“4”，生成的隨機(jī)數(shù)是樣本“1”占用的那就生成“1”。可以看到只要占?jí)蛞欢〝?shù)量的不同的樣本，那么我們一樣能生成帶權(quán)重的隨機(jī)數(shù)。
下面有幾個(gè)問(wèn)題，一是樣本總數(shù)怎么確定，這個(gè)簡(jiǎn)單，每個(gè)比例當(dāng)成整數(shù)相加即可，比如1:2:3:4就是1+2+3+4=10，2:2:3:5就是2+2+3+5=12，依此類推。如果比例是實(shí)數(shù)呢？2.3 : 3.4 : 4.7怎么辦？這就要用到比例的性質(zhì)了，等比擴(kuò)大后比例不變，所以我們每個(gè)實(shí)數(shù)都乘以10，然后去掉小數(shù)點(diǎn)后的0全部當(dāng)成整數(shù)，所以23+34+47=104，理論上任意比例都能這么整，不過(guò)整數(shù)最終有大小限制的，你總不能生成個(gè)隨機(jī)數(shù)還用big.Int吧，所以注意總和別超過(guò)整數(shù)范圍限制。
二是樣本的范圍怎么算，雖然我們只需要不相同的滿足1里總數(shù)的離散的點(diǎn)就行，但為了方便計(jì)算我們還是選擇連續(xù)的整數(shù)比較好，所以范圍限定為[0, sum-1]。這樣我們能直接利用rand.Uint64N()來(lái)生成需要的隨機(jī)數(shù)生成器。
最后我們只要讓樣本按比例隨機(jī)占領(lǐng)一些連續(xù)的整數(shù)就行了。而且我們只需要記錄右邊界就夠了，我們從范圍是[0, n]的第一個(gè)樣本開(kāi)始比較，如果生成器給出的隨機(jī)數(shù)小于等于某個(gè)右邊界，那它一定落在邊界代表的樣本上（因?yàn)槭菑淖钚〉倪吔玳_(kāi)始比較的，所以隨機(jī)數(shù)必然不可能落在前一個(gè)范圍的樣本上）。
其實(shí)就是把連續(xù)的實(shí)數(shù)換成了離散的整數(shù)點(diǎn)罷了，換湯不換藥。
搞明白思路后代碼寫(xiě)起來(lái)就是快：
type WeightRandom[T comparable] struct {
entries []entry[T]
upperBoundary uint64
}
type entry[T comparable] struct {
value T
end uint64
}
首先是數(shù)據(jù)結(jié)構(gòu)，WeightRandom是我們的帶權(quán)重隨機(jī)數(shù)生成器，upperBoundary是樣本數(shù)量的總和，entries則是各個(gè)樣本和樣本占領(lǐng)的連續(xù)整數(shù)的右邊界。
接著來(lái)看構(gòu)造WeightRandom對(duì)象的方法：
func NewWeightRandom[T comparable](rndMap map[T]uint64) *WeightRandom[T] {
var lowerBoundary uint64
entries := make([]entry[T], 0, len(rndMap))
for k, v := range rndMap {
if v == 0 {
panic("weight cannot be zero")
}
if lowerBoundary+v < lowerBoundary {
panic("overflow")
}
lowerBoundary += v
entries = append(entries, entry[T]{
value: k,
end: lowerBoundary,
})
}
slices.SortFunc(entries, func(a, b entry[T]) int {
return cmp.Compare(a.end, b.end)
})
if len(entries) == 0 {
panic("no valid sample")
}
return &WeightRandom[T]{
entries: entries,
upperBoundary: lowerBoundary,
}
}
lowerBoundary用來(lái)統(tǒng)計(jì)有多少樣本，我們最終選擇了左閉右開(kāi)的區(qū)間，這樣方便算。rndMap的key是樣本，value則是比例。當(dāng)樣本的范圍計(jì)算并保存結(jié)束之后，我們需要按照右邊界從小到大排序這些樣本，因?yàn)楹竺娴牟檎曳秶綐颖镜膶?duì)應(yīng)關(guān)系需要右邊界滿足從小到大的順序。
最后是查找函數(shù)：
func (w *WeightRandom[T]) RandomGet() T {
x := rand.Uint64N(w.upperBoundary)
for i := range w.entries {
if x < w.entries[i].end {
return w.entries[i].value
}
}
panic("not possible")
}
查找時(shí)先生成一個(gè)范圍在[0, upperBoundary)之間的隨機(jī)數(shù)，然后我們從最小的邊界開(kāi)始逐一比較，一旦發(fā)現(xiàn)比自己大的邊界，那么就說(shuō)明需要生成邊界對(duì)應(yīng)的樣本。底部那句panic如字面意思，理論上是執(zhí)行不到的，但go不知道，我們要么返回個(gè)空值要么panic，考慮到能走到這里那說(shuō)明我們的程序或者標(biāo)準(zhǔn)庫(kù)的代碼有重大bug，panic了去調(diào)試才是比較好的辦法。
根據(jù)upperBoundary的大小，實(shí)際上我們還能復(fù)用上一節(jié)充分利用每一個(gè)bit的辦法，不需要每次都生成新的隨機(jī)數(shù)，等分割出來(lái)的分組都消耗完了再生成，這樣可以大大加速這個(gè)函數(shù)。不過(guò)為了通用性和盡量簡(jiǎn)化代碼，我就不這樣寫(xiě)了。
最后附加一個(gè)用例：
func main() {
w := NewWeightRandom(map[string]uint64{
"a": 15,
"b": 30,
"c": 45,
"d": 60,
})
m := make(map[string]int, 4)
const limit = 100_0000_0000
for range limit {
m[w.RandomGet()]++
}
for k, v := range m {
fmt.Printf("key: %s, count: %d, p: %g\n", k, v, float64(v)/limit)
}
}
我們按權(quán)重生成“abcd”四個(gè)字母，比例是15:30:45:60，簡(jiǎn)化一下就是1:2:3:4，所以理論上概率應(yīng)該接近10%，20%，30%和40%。不過(guò)統(tǒng)計(jì)上的概率總是有點(diǎn)誤差的，只要大致趨勢(shì)接近于這個(gè)比例就行了。我們運(yùn)行100億次來(lái)看看結(jié)果：
$ go run main.go
key: b, count: 2000011606, p: 0.2000011606
key: a, count: 1000058297, p: 0.1000058297
key: d, count: 3999943022, p: 0.3999943022
key: c, count: 2999987075, p: 0.2999987075
非常符合預(yù)期。作為一項(xiàng)優(yōu)化措施，我們可以利用類似二分查找的辦法來(lái)定位樣本，因?yàn)橛疫吔绫旧硎怯行虻模@可以顯著改善在有大量樣本時(shí)的性能表現(xiàn)。不過(guò)如果你的樣本不超過(guò)10個(gè)的話我覺(jué)得現(xiàn)在這樣的線性查找就足夠了。
怎么說(shuō)呢，簡(jiǎn)單粗暴但有效解決了問(wèn)題。只是和浮點(diǎn)數(shù)的方案比還是有缺點(diǎn)的：
- 因?yàn)檎麛?shù)有范圍限制，這導(dǎo)致了樣本總量會(huì)被限制在一個(gè)比浮點(diǎn)數(shù)方案更小的范圍內(nèi)
- 同樣因?yàn)檎麛?shù)大小限制，比例的選擇范圍會(huì)比浮點(diǎn)數(shù)更小
因?yàn)橄拗聘伲栽谕ㄓ玫墓ぞ邘?kù)里用浮點(diǎn)數(shù)方案的人更多，但業(yè)務(wù)場(chǎng)景和通用工具庫(kù)是不一樣的，很多時(shí)候選整數(shù)方案也沒(méi)啥問(wèn)題，最終你應(yīng)該選擇一個(gè)符合業(yè)務(wù)需求并且自己和同事都看得懂的方案。
至于性能怎么樣，浮點(diǎn)數(shù)方案的查找過(guò)程和整數(shù)方案是一樣的，性能需要做一次完整的測(cè)試才能看出孰高孰低，我不好在這憑空幻想。當(dāng)然測(cè)試我就不做了，我偷個(gè)懶。
隨機(jī)數(shù)種子
“種子”其實(shí)是指一些偽隨機(jī)數(shù)生成算法需要的一些初始狀態(tài)，這些算法會(huì)根據(jù)初始狀態(tài)來(lái)生成一系列有隨機(jī)性的數(shù)值序列。
所以相同的種子通常會(huì)帶來(lái)相同的序列，這時(shí)候雖然每個(gè)序列都有隨機(jī)性，但兩個(gè)序列之間是沒(méi)有隨機(jī)性的——有了其中一個(gè)序列就可以精準(zhǔn)預(yù)測(cè)另一個(gè)序列的排列。具體表現(xiàn)很可能會(huì)是你編寫(xiě)了一個(gè)游戲，其中敵人會(huì)隨機(jī)采取一些行動(dòng)，然而因?yàn)榉N子沒(méi)設(shè)置好，導(dǎo)致每次見(jiàn)到這個(gè)敵人的時(shí)候它都會(huì)采取一模一樣的行動(dòng)步驟，這樣的游戲是極其無(wú)聊的。
不僅如此，產(chǎn)生相同的數(shù)值序列后還會(huì)帶來(lái)無(wú)數(shù)安全問(wèn)題。
種子通常只用設(shè)置一次，并且在程序第一次需要隨機(jī)數(shù)的地方設(shè)置——理想情況是這樣的，然而總是有倒霉蛋忘記了這一點(diǎn)，于是隨機(jī)算法經(jīng)常只能使用默認(rèn)的低質(zhì)量且相同的種子。所以比較現(xiàn)代的語(yǔ)言，比如go1.22和python3都選擇了在程序剛開(kāi)始運(yùn)行的時(shí)候幫你自動(dòng)設(shè)置種子。
此外我們還得擔(dān)心一下種子的質(zhì)量。
“種子”的值需要每次獲取都不一樣，符合要求的常見(jiàn)種子來(lái)源有以下幾種：
- 使用系統(tǒng)時(shí)間。這個(gè)確實(shí)每次獲取都不一樣，獲取速度也很快，是很多開(kāi)發(fā)者和庫(kù)的默認(rèn)選項(xiàng)。但是系統(tǒng)時(shí)間是可以修改的，而且世界上還有閏秒這個(gè)麻煩東西，你意外得到相同的系統(tǒng)時(shí)間的概率其實(shí)不低。
- 使用隨機(jī)設(shè)備，這些是軟件模擬出來(lái)的隨機(jī)數(shù)生成器，以Linux為例，有
random和urandom兩種，其中random以操作系統(tǒng)及外部環(huán)境的噪音為數(shù)據(jù)源產(chǎn)生隨機(jī)值，要求不高時(shí)我們可以認(rèn)為這是“真隨機(jī)”，當(dāng)然它的生成速率是比較低的；另一個(gè)是urandom，它會(huì)用外部噪音生成一個(gè)初始狀態(tài)，然后基于這個(gè)狀態(tài)用偽隨機(jī)數(shù)算法快速產(chǎn)生隨機(jī)值，因此它的生成速率高但質(zhì)量低。一般使用urandom生成種子是夠用的。 - 使用產(chǎn)生真實(shí)隨機(jī)數(shù)的硬件，原理和軟件模擬的類似，和大多數(shù)軟件實(shí)現(xiàn)轉(zhuǎn)硬件實(shí)現(xiàn)后會(huì)性能提升不同，TRNG反而可能會(huì)有更低的性能，但相比軟件實(shí)現(xiàn)它可以更精細(xì)地收集環(huán)境里的雜音從而生成實(shí)驗(yàn)證明的不可預(yù)測(cè)的高質(zhì)量的隨機(jī)數(shù)。常見(jiàn)的TRNG生成速率從數(shù)百k/s到數(shù)兆/s的都有，但像
/dev/random通常速率可以有數(shù)兆到數(shù)十兆/s。除了性能上的不穩(wěn)定，不是所有設(shè)備都包含TRNG，這導(dǎo)致了適用面受限，所以直接用它的人不多。不過(guò)很多依賴高質(zhì)量隨機(jī)數(shù)的場(chǎng)景就不得不考慮TRNG了。 - 利用地址空間布局隨機(jī)化。現(xiàn)代操作系統(tǒng)在加載程序后都會(huì)給程序的內(nèi)存地址加點(diǎn)隨機(jī)的偏移量，所以程序每次運(yùn)行的時(shí)候獲取的變量地址基本都是不同的。這個(gè)是成本極低的獲取隨機(jī)值的方法，幾乎不花費(fèi)運(yùn)行時(shí)代價(jià)，谷歌的abseil庫(kù)里就有很多用這個(gè)方法獲取隨機(jī)數(shù)種子的代碼。然而，使用這個(gè)方法的前提是你的系統(tǒng)要支持地址空間布局隨機(jī)化，其次系統(tǒng)加的隨機(jī)偏移量質(zhì)量要尚可，這兩個(gè)我們都控制不了，我們只能相信常用操作系統(tǒng)都做到這幾點(diǎn)了。另外，高權(quán)限的程序和用戶始終能把一些代碼寫(xiě)進(jìn)有固定地址的地方，雖然這種操作正變得越來(lái)越難，但還不是完全不可能，所以需要高質(zhì)量種子的時(shí)候這個(gè)方案通常不會(huì)被考慮（另一個(gè)原因是有的系統(tǒng)可以配置關(guān)閉隨機(jī)化布局甚至根本不支持隨機(jī)化）。
- auxiliary vector。Linux特有的，可以通過(guò)
/proc/<pid>/auxv或者glibc的函數(shù)getauxval來(lái)獲取。這個(gè)數(shù)組包含一系列操作系統(tǒng)和當(dāng)前進(jìn)程的信息，全部是操作系統(tǒng)在程序加載時(shí)寫(xiě)入的，Windows有類似的東西。這些數(shù)據(jù)中有些是不變的比如硬件信息和平臺(tái)信息，有些則是完全隨機(jī)的，比如其中有程序的入口地址和vDSO的地址，這些因?yàn)锳SLR的緣故都是完全隨機(jī)的，另外auxv里還有專門(mén)的隨機(jī)值字段，這些信息加一起比單純依賴ASLR能帶來(lái)更強(qiáng)的不可預(yù)測(cè)。
原則就是盡量讓預(yù)測(cè)結(jié)果的難度增加，最好是能做到完全不可預(yù)測(cè)。
那作為開(kāi)發(fā)者我用啥呢？一般來(lái)說(shuō)系統(tǒng)時(shí)間是夠用了，自己寫(xiě)著完或者做些簡(jiǎn)單工具可以用這個(gè)，不過(guò)要記住系統(tǒng)時(shí)間是可修改的不可靠的。如果是庫(kù)或者對(duì)隨機(jī)性依賴比較重的比如游戲，/dev/urandom是個(gè)比較理想的選擇。追求極致性能并且對(duì)種子質(zhì)量要求沒(méi)那么高時(shí)，像谷歌那樣利用ASLR帶來(lái)的隨機(jī)值也是可以的。
實(shí)在有選擇困難癥的話，我們來(lái)看看別人是怎么做的。
golang和python3選擇了那些源作為種子
golang實(shí)際上是先利用auxv，如果系統(tǒng)不支持，就回退到從urandom之類的隨機(jī)設(shè)備讀取隨機(jī)值，這個(gè)也出問(wèn)題了就使用系統(tǒng)時(shí)間：
// runtime/rand.go
// OS-specific startup can set startupRand if the OS passes
// random data to the process at startup time.
// For example Linux passes 16 bytes in the auxv vector.
var startupRand []byte
func randinit() {
lock(&globalRand.lock)
if globalRand.init {
fatal("randinit twice")
}
seed := &globalRand.seed
// 查看是否有auxv信息被系統(tǒng)寫(xiě)入
if startupRand != nil {
for i, c := range startupRand {
seed[i%len(seed)] ^= c
}
clear(startupRand)
startupRand = nil
} else {
// 先從urandom讀取
if readRandom(seed[:]) != len(seed) {
// readRandom should never fail, but if it does we'd rather
// not make Go binaries completely unusable, so make up
// some random data based on the current time.
readRandomFailed = true
readTimeRandom(seed[:])
}
}
globalRand.state.Init(*seed)
clear(seed[:])
globalRand.init = true
unlock(&globalRand.lock)
}
這個(gè)是全局函數(shù)的設(shè)置，go還能自己創(chuàng)建rand.Source，這個(gè)的種子只能顯式傳進(jìn)去，這時(shí)候傳什么go就沒(méi)法管了，靈活的同時(shí)犧牲了一定的安全性。
Python3則是先讀取urandom，失敗后會(huì)結(jié)合系統(tǒng)時(shí)間加當(dāng)前進(jìn)程pid來(lái)生成種子，這樣比單使用系統(tǒng)時(shí)間要強(qiáng)：
// https://github.com/python/cpython/blob/main/Modules/_randommodule.c#L293
static int
random_seed(RandomObject *self, PyObject *arg)
{
int result = -1; /* guilty until proved innocent */
PyObject *n = NULL;
uint32_t *key = NULL;
size_t bits, keyused;
int res;
// 參數(shù)為空的時(shí)候
if (arg == NULL || arg == Py_None) {
if (random_seed_urandom(self) < 0) {
PyErr_Clear();
/* Reading system entropy failed, fall back on the worst entropy:
use the current time and process identifier. */
if (random_seed_time_pid(self) < 0) {
return -1;
}
}
return 0;
}
// 參數(shù)不為空的時(shí)候根據(jù)參數(shù)生成種子
Done:
Py_XDECREF(n);
PyMem_Free(key);
return result;
}
然后這個(gè)函數(shù)會(huì)被Random對(duì)象的__init__方法調(diào)用，如果初始化一個(gè)Random對(duì)象但不傳seed參數(shù)，那么就會(huì)進(jìn)行默認(rèn)設(shè)置。而random模塊里所有的方法其實(shí)都是由一個(gè)全局的Random()對(duì)象提供的，因?yàn)闆](méi)傳seed進(jìn)去，所以代碼里會(huì)自動(dòng)設(shè)置seed：
# https://github.com/python/cpython/blob/main/Lib/random.py#L924
_inst = Random()
seed = _inst.seed
random = _inst.random
uniform = _inst.uniform
triangular = _inst.triangular
randint = _inst.randint
choice = _inst.choice
randrange = _inst.randrange
sample = _inst.sample
shuffle = _inst.shuffle
choices = _inst.choices
normalvariate = _inst.normalvariate
lognormvariate = _inst.lognormvariate
expovariate = _inst.expovariate
vonmisesvariate = _inst.vonmisesvariate
gammavariate = _inst.gammavariate
gauss = _inst.gauss
betavariate = _inst.betavariate
binomialvariate = _inst.binomialvariate
paretovariate = _inst.paretovariate
weibullvariate = _inst.weibullvariate
getstate = _inst.getstate
setstate = _inst.setstate
getrandbits = _inst.getrandbits
randbytes = _inst.randbytes
這樣python就防止了用戶忘記設(shè)置seed的問(wèn)題。
總結(jié)
關(guān)于隨機(jī)數(shù)要講的暫時(shí)就這么多了，除了一丁點(diǎn)數(shù)值算法之外都是些比較淺顯易懂的東西。
概率和統(tǒng)計(jì)對(duì)程序設(shè)計(jì)的影響是很大的，所以我覺(jué)得與其花時(shí)間看最近比較火的微分方程，稍微抽出點(diǎn)時(shí)間看看概率統(tǒng)計(jì)對(duì)自己的幫助可能更大。
最后，其實(shí)標(biāo)準(zhǔn)庫(kù)還有各種第三方庫(kù)已經(jīng)貼心準(zhǔn)備了幾乎全套功能了，看懂文檔就能放心用，而且我也更推薦用這些庫(kù)，開(kāi)源的且久經(jīng)檢驗(yàn)的代碼始終是比自己閉門(mén)造車來(lái)的強(qiáng)。
參考
https://stackoverflow.com/questions/18394733/generating-a-random-number-between-1-7-by-rand5
浙公網(wǎng)安備 33010602011771號(hào)