python randint函數(python中randint函數的效率缺陷實例分析)

一、前言

前幾天,在寫一個與差分隱私相關的簡單程序時,我發現了一些奇怪的東西:相對于其他的隨機數生成函數,Python的random.randint()函數感覺很慢。 由于randint()是 Python 中最為常用的生成隨機整數的API,因此我決定深入挖掘其實現機制以了解其運行效率較低的原因。

二、對randint()運行效率的測試

首先,我們可以先觀察一下random.randint()的運行效率:

$python3-mtimeit-s'importrandom''random.random()'10000000loops,bestof3:0.0523usecperloop$python3-mtimeit-s'importrandom''random.randint(0,128)'1000000loops,bestof3:1.09usecperloop

很明顯,在生成一個大小在[0, 128]中的隨機整數的成本,大約是在生成大小在[0, 1)之間的隨機浮點數的 20 倍。

三、從源碼分析randint()的缺陷

接下來,我們將從python的源碼,來解析randint()的實現機制。

random.random()

首先從random()開始說。該函數定義在Lib/random.py文件中,函數random.random()是Random類的random方法的別名,而Random.random()直接從_Random繼承了random方法。繼續向下追溯就會發現,random方法的真正定義是在Modules/_randommodule.c中實現的,其實現代碼如下:

staticPyObject*random_random(RandomObject*self,PyObject*Py_UNUSED(ignored)){uint32_ta=genrand_int32(self)>>5,b=genrand_int32(self)>>6;returnPyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));}

其中getrand_int32()函數是一個C語言實現的梅森旋轉算法,其能夠快速生成偽隨機數。

總結一下,當我們在Python中調用random.random()時,該函數直接調用了C函數,而該C函數唯一的功能就是:生成隨機數,并將genrand_int32()的結果轉換為浮點數,除此之外沒有做任何額外的步驟。

random.randint()

現在讓我們看看randint()的實現代碼:

defrandint(self,a,b):"""Returnrandomintegerinrange[a,b],includingbothendpoints."""returnself.randrange(a,b+1)

randint函數會調用randrange()函數,因此我們再觀察randrange()的源碼。

defrandrange(self,start,stop=None,step=1,_int=int):"""Choosearandomitemfromrange(start,stop[,step]).Thisfixestheproblemwithrandint()whichincludestheendpoint;inPythonthisisusuallynotwhatyouwant."""#Thiscodeisabitmessytomakeitfastforthe#commoncasewhilestilldoingadequateerrorchecking.istart=_int(start)ifistart!=start:raiseValueError("non-integerarg1forrandrange()")ifstopisNone:ifistart>0:returnself._randbelow(istart)raiseValueError("emptyrangeforrandrange()")#stopargumentsupplied.istop=_int(stop)ifistop!=stop:raiseValueError("non-integerstopforrandrange()")width=istop-istartifstep==1andwidth>0:returnistart+self._randbelow(width)ifstep==1:raiseValueError("emptyrangeforrandrange()(%d,%d,%d)"%(istart,istop,width))#Non-unitstepargumentsupplied.istep=_int(step)ifistep!=step:raiseValueError("non-integerstepforrandrange()")ifistep>0:n=(width+istep-1)//istepelifistep<0:n=(width+istep+1)//istepelse:raiseValueError("zerostepforrandrange()")ifn<=0:raiseValueError("emptyrangeforrandrange()")returnistart+istep*self._randbelow(n)

在調用下一層的函數之前,randrange()需要對于函數參數進行大量的檢查。不過,如果我們不是用stop參數,那么檢查速度就會快一些,經過一堆檢查之后,才可以調用_randbelow()方法。

默認情況下,_randbelow()被映射到_randbelow_with_getrandbits():

def_randbelow_with_getrandbits(self,n):"Returnarandomintintherange[0,n).RaisesValueErrorifn==0."getrandbits=self.getrandbitsk=n.bit_length()#don'tuse(n-1)herebecausencanbe1r=getrandbits(k)#0<=r<2**kwhiler>=n:r=getrandbits(k)returnr

從該函數的源碼可以發現:該函數的邏輯是計算出n的位數,而后按照位數生成隨機比特,因此當n的大小不為2的次冪時,該函數可能需要多次調用getrandbits()。getrandbits()是一個利用C語言定義的函數,該函數最終也會調用getrand_int32(),但由于該函數相對于 random() 函數需要更多的處理過程,導致其運行速度慢兩倍。

總而言之,通過python代碼或者C代碼都可以調用由C所定義的函數。由于 Python 是字節碼解釋的,因此,任何在調用C函數之前的,用python語言定義的處理過程,都會導致函數的運行速度比直接調用 C 函數慢很多。

這里有幾個實驗可以幫助我們檢驗這個假設。首先,讓我們嘗試在randrange中通過調用沒有stop參數的randrange來減少中間的參數檢查過程,提高程序執行的速度:

$python3-mtimeit-s'importrandom''random.randrange(1)'1000000loops,bestof3:0.784usecperloop

正如預期的那樣,由于中間運行過程的減少,此時randrange()運行時間比原始的randint()好一些?？梢栽?PyPy 中重新運行比較運行時間。

$pypy-mtimeit-s'importrandom''random.random()'100000000loops,bestof3:0.0139usecperloop$pypy-mtimeit-s'importrandom''random.randint(0,128)'100000000loops,bestof3:0.0168usecperloop

正如預期的那樣,PyPy 中這些調用之間的差異很小。

四、更快的生成隨機整數的方法

所以 randint() 結果非常慢。當只需要生成少量隨機數的時候,可以忽視該函數帶來的性能損失,當需要生成大量的隨機數時,就需要尋找一個效率夠高的方法。

random.random()

一個技巧就是使用random.random()代替,乘以我們的整數限制從而得到整數,由于random()可以生成均勻的[0,1)分布,因此擴展之后也可以得到整數上的均勻分布:

$python3-mtimeit-s'importrandom''int(128*random.random())'10000000loops,bestof3:0.193usecperloop

這為我們提供了 [0, 128)范圍內的偽隨機整數,速度更快。需要注意的是:Python 以雙精度表示其浮點數,精度為 53 位。當限制超過 53 位時,我們將使用此方法獲得的數字不是完全隨機的,多的位將丟失。如果不需要這么大的整數,就可以忽視這個問題。

直接使用 getrandbits()

另一種生成偽隨機整數的快速方法是直接使用 getrandbits():

$python3-mtimeit-s'importrandom''random.getrandbits(7)'10000000loops,bestof3:0.102usecperloop

此方法快速,但是生成數據范圍有限:它支持的范圍為[0,2^n]。如果我們想限制范圍,取模的方法無法做到范圍的限制——這會扭曲分布;因此,我們必須使用類似于上面示例中的_randbelow_with_getrandbits()中的循環。但是會減慢速度。

使用 Numpy.random

最后,我們可以完全放棄 random 模塊,而使用 Numpy:

$python3-mtimeit-s'importnumpy.random''numpy.random.randint(128)'1000000loops,bestof3:1.21usecperloop

生成單個數據的速度很慢。那是因為 Numpy 不適合僅用于單個數據:numpy能夠將成本攤銷在用 C語言 創建or操作的大型數組上。為了證明這一點,下邊給出了生成 100 個隨機整數所需時間:

$python3-mtimeit-s'importnumpy.random''numpy.random.randint(128,size=100)'1000000loops,bestof3:1.91usecperloop

僅比生成單個慢 60%! 每個整數 0.019 微秒,這是目前最快的方法——比調用random.random()快 3 倍。 這種方法如此之快的原因是Numpy將調用開銷分攤到所有生成的整數上,并且在 Numpy 內部運行一個高效的 C 循環來生成它們?？傊?如果要生成大量隨機整數,建議使用 Numpy; 如果只是一次生成一個,它可能沒有特別高效。

“python中randint函數的效率缺陷實例分析”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業相關的知識可以關注本站網站,小編將為大家輸出更多高質量的實用文章!