源碼解析python中randint函數的效率缺陷
一、前言
前幾天，在寫一個與差分隱私相關的簡單程序時，我發現瞭一些奇怪的東西：相對於其他的隨機數生成函數，Python的random.randint()函數感覺很慢。 由於 randint() 是 Python 中最為常用的生成隨機整數的API，因此我決定深入挖掘其實現機制以瞭解其運行效率較低的原因。
本文深入探討瞭 random 模塊的實現，並討論瞭一些更為快速的生成偽隨機整數的替代方法。
二、對randint()運行效率的測試
首先，我們可以先觀察一下random.randint()的運行效率：
$ python3 -m timeit -s 'import random' 'random.random()' 10000000 loops, best of 3: 0.0523 usec per loop $ python3 -m timeit -s 'import random' 'random.randint(0, 128)' 1000000 loops, best of 3: 1.09 usec per loop
很明顯，在生成一個大小在[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中實現的，其實現代碼如下：
static PyObject *
random_random(RandomObject *self, PyObject *Py_UNUSED(ignored))
{
uint32_t a=genrand_int32(self)>>5, b=genrand_int32(self)>>6;
return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}
其中 getrand_int32() 函數是一個C語言實現的梅森旋轉算法，其能夠快速生成偽隨機數。
總結一下，當我們在Python中調用random.random()時，該函數直接調用瞭C函數，而該C函數唯一的功能就是：生成隨機數，並將genrand_int32()的結果轉換為浮點數，除此之外沒有做任何額外的步驟。
random.randint()
現在讓我們看看randint()的實現代碼：
def randint(self, a, b):
"""Return random integer in range [a, b], including both end points.
"""
return self.randrange(a, b+1)
randint函數會調用randrange()函數，因此我們再觀察randrange()的源碼。
def randrange(self, start, stop=None, step=1, _int=int):
"""Choose a random item from range(start, stop[, step]).
This fixes the problem with randint() which includes the
endpoint; in Python this is usually not what you want.
"""
# This code is a bit messy to make it fast for the
# common case while still doing adequate error checking.
istart = _int(start)
if istart != start:
raise ValueError("non-integer arg 1 for randrange()")
if stop is None:
if istart > 0:
return self._randbelow(istart)
raise ValueError("empty range for randrange()")
# stop argument supplied.
istop = _int(stop)
if istop != stop:
raise ValueError("non-integer stop for randrange()")
width = istop - istart
if step == 1 and width > 0:
return istart + self._randbelow(width)
if step == 1:
raise ValueError("empty range for randrange() (%d,%d, %d)" % (istart, istop, width))
# Non-unit step argument supplied.
istep = _int(step)
if istep != step:
raise ValueError("non-integer step for randrange()")
if istep > 0:
n = (width + istep - 1) // istep
elif istep < 0:
n = (width + istep + 1) // istep
else:
raise ValueError("zero step for randrange()")
if n <= 0:
raise ValueError("empty range for randrange()")
return istart + istep*self._randbelow(n)
在調用下一層的函數之前，randrange()需要對於函數參數進行大量的檢查。不過，如果我們不是用stop參數，那麼檢查速度就會快一些，經過一堆檢查之後，才可以調用_randbelow()方法。
默認情況下，_randbelow() 被映射到 _randbelow_with_getrandbits()：
def _randbelow_with_getrandbits(self, n):
"Return a random int in the range [0,n). Raises ValueError if n==0."
getrandbits = self.getrandbits
k = n.bit_length() # don't use (n-1) here because n can be 1
r = getrandbits(k) # 0 <= r < 2**k
while r >= n:
r = getrandbits(k)
return r
從該函數的源碼可以發現：該函數的邏輯是計算出n的位數，而後按照位數生成隨機比特，因此當n的大小不為2的次冪時，該函數可能需要多次調用getrandbits()。getrandbits()是一個利用C語言定義的函數，該函數最終也會調用 getrand_int32()，但由於該函數相對於 random() 函數需要更多的處理過程，導致其運行速度慢兩倍。
總而言之，通過python代碼或者C代碼都可以調用由C所定義的函數。由於 Python 是字節碼解釋的，因此，任何在調用C函數之前的，用python語言定義的處理過程，都會導致函數的運行速度比直接調用 C 函數慢很多。
這裡有幾個實驗可以幫助我們檢驗這個假設。首先，讓我們嘗試在 randrange 中通過調用沒有stop參數的 randrange 來減少中間的參數檢查過程，提高程序執行的速度：
$ python3 -m timeit -s 'import random' 'random.randrange(1)' 1000000 loops, best of 3: 0.784 usec per loop
正如預期的那樣，由於中間運行過程的減少，此時randrange()運行時間比原始的 randint() 好一些。可以在 PyPy 中重新運行比較運行時間。
$ pypy -m timeit -s 'import random' 'random.random()' 100000000 loops, best of 3: 0.0139 usec per loop $ pypy -m timeit -s 'import random' 'random.randint(0, 128)' 100000000 loops, best of 3: 0.0168 usec per loop
正如預期的那樣，PyPy 中這些調用之間的差異很小。
四、更快的生成隨機整數的方法
所以 randint() 結果非常慢。當隻需要生成少量隨機數的時候，可以忽視該函數帶來的性能損失，當需要生成大量的隨機數時，就需要尋找一個效率夠高的方法。
random.random()
一個技巧就是使用random.random()代替，乘以我們的整數限制從而得到整數，由於random()可以生成均勻的[0,1)分佈，因此擴展之後也可以得到整數上的均勻分佈：
$ python3 -m timeit -s 'import random' 'int(128 * random.random())' 10000000 loops, best of 3: 0.193 usec per loop
這為我們提供瞭 [0, 128)范圍內的偽隨機整數，速度更快。需要註意的是：Python 以雙精度表示其浮點數，精度為 53 位。當限制超過 53 位時，我們將使用此方法獲得的數字不是完全隨機的，多的位將丟失。如果不需要這麼大的整數，就可以忽視這個問題。
直接使用 getrandbits()
另一種生成偽隨機整數的快速方法是直接使用 getrandbits()：
$ python3 -m timeit -s 'import random' 'random.getrandbits(7)' 10000000 loops, best of 3: 0.102 usec per loop
此方法快速，但是生成數據范圍有限：它支持的范圍為[0,2^n]。如果我們想限制范圍，取模的方法無法做到范圍的限制——這會扭曲分佈；因此，我們必須使用類似於上面示例中的 _randbelow_with_getrandbits()中的循環。但是會減慢速度。
使用 Numpy.random
最後，我們可以完全放棄 random 模塊，而使用 Numpy：
$ python3 -m timeit -s 'import numpy.random' 'numpy.random.randint(128)' 1000000 loops, best of 3: 1.21 usec per loop
生成單個數據的速度很慢。那是因為 Numpy 不適合僅用於單個數據：numpy能夠將成本攤銷在用 C語言 創建or操作的大型數組上。為瞭證明這一點，下邊給出瞭生成 100 個隨機整數所需時間：
$ python3 -m timeit -s 'import numpy.random' 'numpy.random.randint(128, size=100)' 1000000 loops, best of 3: 1.91 usec per loop
僅比生成單個慢 60%！ 每個整數 0.019 微秒，這是目前最快的方法——比調用 random.random() 快 3 倍。 這種方法如此之快的原因是Numpy將調用開銷分攤到所有生成的整數上，並且在 Numpy 內部運行一個高效的 C 循環來生成它們。總之，如果要生成大量隨機整數，建議使用 Numpy； 如果隻是一次生成一個，它可能沒有特別高效。
到此這篇關於源碼解析python中randint函數的效率缺陷的文章就介紹到這瞭,更多相關 python randint 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- python中列表(list)和元組(tuple)的深入講解
- Python生成隨機數詳解流程
- 如何在向量化NumPy數組上進行移動窗口
- Python如何生成隨機數及random隨機數模塊應用
- Python 中random 庫的詳細使用