Python random包可以用來(lái)生成隨機(jī)數(shù)。隨機(jī)數(shù)不僅可以用于數(shù)學(xué)用途，還經(jīng)常被嵌入到算法中巾表，用以提高算法效率，并提高程序的安全性略吨。如果想要更加高級(jí)的數(shù)學(xué)功能集币，可以考慮選擇標(biāo)準(zhǔn)庫(kù)之外的numpy和scipy項(xiàng)目，它們不但支持?jǐn)?shù)組和矩陣運(yùn)算翠忠，還有豐富的數(shù)學(xué)和物理方程可供使用鞠苟。
本章節(jié)主要介紹random.random()，它被用來(lái)生成一個(gè)0~1之間的隨機(jī)浮點(diǎn)數(shù)秽之，是randint(), shuffle(), choice()等其他函數(shù)的基礎(chǔ)当娱。
隨機(jī)數(shù)的意義
現(xiàn)實(shí)生活中，有很多場(chǎng)景需要用到“隨機(jī)數(shù)”：
- 彩票
- 棋牌游戲中的洗牌和擲骰子
- 游戲掉寶率
其中大部分是靠計(jì)算機(jī)軟件生成的的“偽隨機(jī)數(shù)”考榨。偽隨機(jī)數(shù)一般是由隨機(jī)種子和隨機(jī)算法計(jì)算生成的跨细，也就是說(shuō)，在隨機(jī)種子和隨機(jī)算法一定的情況下河质，偽隨機(jī)數(shù)是可重復(fù)冀惭、可預(yù)測(cè)的震叙。
簡(jiǎn)單來(lái)說(shuō)，偽隨機(jī)數(shù)具有循環(huán)長(zhǎng)度散休。什么叫循環(huán)長(zhǎng)度媒楼？就是如果第一次產(chǎn)生數(shù)字55，第二個(gè)產(chǎn)生數(shù)字107戚丸，那么循環(huán)多少次后划址，會(huì)繼續(xù)產(chǎn)生55，107……這樣的序列限府。大部分簡(jiǎn)單算法的循環(huán)長(zhǎng)度都是2^32左右夺颤。
這有什么影響嗎？如果你使用偽隨機(jī)數(shù)生成中獎(jiǎng)號(hào)碼谣殊，有心人可以根據(jù)歷史結(jié)果推斷出你的中獎(jiǎng)號(hào)碼規(guī)律。事實(shí)上牺弄，過(guò)去有些電話充值卡就是因此被破解的姻几。大家可以思考其中的門(mén)道。
偽隨機(jī)數(shù)的一個(gè)優(yōu)點(diǎn)是它們的計(jì)算不需要外部的特殊硬件的支持势告，因此在計(jì)算機(jī)科學(xué)中偽隨機(jī)數(shù)依然被使用蛇捌。真正的隨機(jī)數(shù)必須使用專(zhuān)門(mén)的設(shè)備，比如熱噪訊號(hào)咱台、量子力學(xué)的效應(yīng)络拌、放射性元素的衰退輻射，或使用無(wú)法預(yù)測(cè)的現(xiàn)象回溺，譬如用戶按鍵盤(pán)的位置與速度春贸、用戶運(yùn)動(dòng)鼠標(biāo)的路徑坐標(biāo)等來(lái)產(chǎn)生。 [wiki 偽隨機(jī)性]
好的隨機(jī)數(shù)算法
軟件無(wú)法產(chǎn)生真正意義上的隨機(jī)數(shù)遗遵，而只能產(chǎn)生偽隨機(jī)數(shù)萍恕。
好的隨機(jī)數(shù)算法應(yīng)具有如下性質(zhì)：
(1)相同序列的概率非常低
(2)符合統(tǒng)計(jì)學(xué)的平均性
好的偽隨機(jī)數(shù)算法和差的具有天壤之別，其中差別之大用肉眼就可以觀測(cè)到：
常用的隨機(jī)數(shù)算法
線性同余
線性同余隨機(jī)數(shù)生成器LCG（linear congruential generator）是最古老也最廣為人知的位隨機(jī)數(shù)生成器算法车要，它通過(guò)遞歸公式產(chǎn)生偽隨機(jī)數(shù)允粤。
公式：X(i) = [a * X(i-1) + c] Mod m產(chǎn)生一個(gè)[0, m-1]之間的隨機(jī)數(shù)序列，種子值X(0)是用戶提供的且是上式中唯一用作遞歸的隨機(jī)數(shù)翼岁。該序列通過(guò)浮點(diǎn)數(shù)操作（除法）可以轉(zhuǎn)化為在[0, 1]之間均勻分布的隨機(jī)數(shù)序列类垫。
LCG的循環(huán)長(zhǎng)度對(duì)a, c敏感，選擇合適的參數(shù)循環(huán)長(zhǎng)度可達(dá)到m琅坡。
通過(guò)以上公式悉患，我們很容易完成線性同余生成器的Python實(shí)現(xiàn)。
class Random(object):
'''Random 庫(kù)實(shí)現(xiàn)'''
def __init__(self, x=None):
if x is None:
import time
self.seed = long(time.time())
else:
self.seed = long(x)
self._seed = self.seed
def random_LCG(self):
'''
線性同余產(chǎn)生0~1之間的隨機(jī)數(shù)
X(k) = [a * X(k-1) + c] mod m
'''
# 以下參數(shù)值參照GCC編譯器
m = 2**32
a = 1103515245
c = 12345
self._seed = (a * self._seed + c) % m
return self._seed / float(m-1)
平方取中
平方取中法是由馮·諾依曼在1946年提出的榆俺，其基本思想為：將數(shù)列中的第X(i)項(xiàng)（假設(shè)其有m位）平方购撼，取得到的2m位數(shù)（若不足2m位跪削，在最高位前補(bǔ)0）中間部分的m位數(shù)字，作為X(i)的下一項(xiàng)X(i+1)迂求，由此產(chǎn)生一個(gè)偽隨機(jī)數(shù)數(shù)列碾盐。即：
x(i+1) = (10^(-m/2) * x(i) * x(i)) Mod (10^m)
平方取中法計(jì)算較快，但在實(shí)際應(yīng)用時(shí)會(huì)發(fā)現(xiàn)該方法容易產(chǎn)生周期性明顯的數(shù)列揩局，而且在某些情況下計(jì)算到一定步驟后始終產(chǎn)生相同的數(shù)甚至是零毫玖，或者產(chǎn)生的數(shù)字位數(shù)越來(lái)越小直至始終產(chǎn)生零。
在類(lèi) Random 中添加平方取中函數(shù)凌盯。
def random_MSM(self):
'''
平方取中法產(chǎn)生0~1之間的隨機(jī)數(shù)
X(i+1) = [10^(-m/2) * X(i)^2] mod (10^m)
'''
m = 8
self._seed = long((10**(-m/2) * self._seed * self._seed) % (10**m))
return self._seed / float(10**m -1)
Wichmann-Hill
Python Random標(biāo)準(zhǔn)庫(kù)中提供了基于Wichmann-Hill 算法實(shí)現(xiàn)的random()函數(shù)付枫。
Wichman-Hill算法通過(guò)線性合并不同短周期隨機(jī)數(shù)發(fā)生器的輸出來(lái)產(chǎn)生長(zhǎng)周期的隨機(jī)數(shù)序列。如果把周期N1和N2的波形加起來(lái)那么得到的波形周期為
N = lcm（N1,N2）
這樣驰怎，通過(guò)結(jié)合幾個(gè)隨機(jī)數(shù)發(fā)生器的輸出阐滩，可以產(chǎn)生一個(gè)更長(zhǎng)的序列。它結(jié)合3個(gè)隨機(jī)數(shù)發(fā)生器的輸出如下:
X(n) = 171 * X(n-1) Mod 30269
Y(n) = 172 * X(n-1) Mod 30307
Z(n )= 170 * X(n-1) Mod 30323
U(n) = {X(n)/30269 + Y(n)/30307 + Z(n)/30323}
源碼如下：
def random(self):
"""Get the next random number in the range [0.0, 1.0)."""
# Wichman-Hill random number generator.
#
# Wichmann, B. A. & Hill, I. D. (1982)
# Algorithm AS 183:
# An efficient and portable pseudo-random number generator
# Applied Statistics 31 (1982) 188-190
#
# see also:
# Correction to Algorithm AS 183
# Applied Statistics 33 (1984) 123
#
# McLeod, A. I. (1985)
# A remark on Algorithm AS 183
# Applied Statistics 34 (1985),198-200
# This part is thread-unsafe:
# BEGIN CRITICAL SECTION
x, y, z = self._seed
x = (171 * x) % 30269
y = (172 * y) % 30307
z = (170 * z) % 30323
self._seed = x, y, z
# END CRITICAL SECTION
# Note: on a platform using IEEE-754 double arithmetic, this can
# never return 0.0 (asserted by Tim; proof too long for a comment).
return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
Mersenne Twister
Mersenne Twister算法譯為馬特賽特旋轉(zhuǎn)演算法县忌，是偽隨機(jī)數(shù)發(fā)生器之一掂榔，其主要作用是生成偽隨機(jī)數(shù)。此算法是Makoto Matsumoto （松本）和Takuji Nishimura （西村）于1997年開(kāi)發(fā)的症杏，基于有限二進(jìn)制字段上的矩陣線性再生装获。可以快速產(chǎn)生高質(zhì)量的偽隨機(jī)數(shù)厉颤，修正了古老隨機(jī)數(shù)產(chǎn)生算法的很多缺陷穴豫。
Mersenne Twister有以下優(yōu)點(diǎn)：隨機(jī)性好，在計(jì)算機(jī)上容易實(shí)現(xiàn)逼友，占用內(nèi)存較少(mt19937的C程式碼執(zhí)行僅需624個(gè)字的工作區(qū)域)精肃，與其它已使用的偽隨機(jī)數(shù)發(fā)生器相比，產(chǎn)生隨機(jī)數(shù)的速度快帜乞、周期長(zhǎng)肋杖，可達(dá)到2^19937-1，且具有623維均勻分布的性質(zhì)挖函。
Mersenne Twister 目前被很多語(yǔ)言采用状植，作為隨機(jī)數(shù)產(chǎn)生算法。以下是Python Random庫(kù)中關(guān)于默認(rèn) Random.random() 函數(shù)的說(shuō)明怨喘。
General notes on the underlying Mersenne Twister core generator:
* The period is 2**19937-1.
* It is one of the most extensively tested generators in existence.
* Without a direct way to compute N steps forward, the semantics of
jumpahead(n) are weakened to simply jump to another distant state and rely
on the large period to avoid overlapping sequences.
* The random() method is implemented in C, executes in a single Python step,
and is, therefore, threadsafe.
性能比較
根據(jù)隨機(jī)數(shù)算法生成一組坐標(biāo)(x,y)津畸，使用pylab繪制其在二維坐標(biāo)系上的散點(diǎn)圖。
上圖的四個(gè)子圖分別由不同的算法生成的2000個(gè)點(diǎn)繪制必怜，散點(diǎn)圖的特點(diǎn)是相同點(diǎn)數(shù)不堆積只繪制一次肉拓，因此在坐標(biāo)軸上點(diǎn)數(shù)越多、分布越均勻代表算法性能越優(yōu)秀梳庆。
可發(fā)現(xiàn)：
- 平方取中算法較其他算法出現(xiàn)了明顯的稀疏分布暖途，即算法在2000個(gè)點(diǎn)時(shí)已命中循環(huán)長(zhǎng)度卑惜。
- 線性同余生成器算法在2000個(gè)點(diǎn)時(shí)與Python Random標(biāo)準(zhǔn)庫(kù)提供的Wichmann-Hill、Mersenne Twister算法性能差距不大驻售。
拓展閱讀
- Python 隨機(jī)數(shù)標(biāo)準(zhǔn)庫(kù)(2) -- shuffle()
- 偽隨機(jī)的上位和真隨機(jī)的逆襲
- Random.org: 通過(guò)大氣噪音 (Atmospheric Noise) 這種大自然的隨機(jī)現(xiàn)象來(lái)產(chǎn)生最優(yōu)質(zhì)最科學(xué)最隨機(jī)的隨機(jī)數(shù)生成及衍生服務(wù)露久。他們提供的免費(fèi)服務(wù)包括：隨機(jī)數(shù)、數(shù)組欺栗、字符毫痕、序列生成，隨機(jī)正態(tài)分布生成迟几，機(jī)選彩票消请，拋硬幣，擲色子类腮，洗牌器臊泰，隨機(jī)打亂順序，隨機(jī)生成時(shí)間蚜枢、日期缸逃、密碼、地理坐標(biāo)祟偷、DNA序列察滑、純凈白噪音等等打厘，從娛樂(lè)到學(xué)術(shù)都有修肠。當(dāng)然他們還有付費(fèi)服務(wù)：第三方認(rèn)證的抽簽，為非常重要的抽簽提供最高純度的隨機(jī)性户盯。
更多精彩內(nèi)容嵌施，請(qǐng)關(guān)注我的個(gè)人博客。
