日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

源碼解析python中randint函數的效率缺陷_python

作者：??bastgia???? ? 更新時間： 2022-08-02 編程語言

一、前言

前幾天，在寫一個與差分隱私相關的簡單程序時，我發現了一些奇怪的東西：相對于其他的隨機數生成函數，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； 如果只是一次生成一個，它可能沒有特別高效。

原文鏈接：https://juejin.cn/post/7097242084079304717

欄目分類
最近更新