原始碼解析python中randint函數的效率缺陷

2022-06-08 22:01:20

一、前言

前幾天，在寫一個與差分隱私相關的簡單程式時，我發現了一些奇怪的東西：相對於其他的亂數生成函數，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 內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

原始碼解析python中randint函數的效率缺陷

目錄

一、前言

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

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

random.random()

random.randint()

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

random.random()

直接使用 getrandbits()

使用 Numpy.random

熱門文章