一、前言

前幾天，在寫一個(gè)與差分隱私相關(guān)的簡單程序時(shí)，我發(fā)現(xiàn)了一些奇怪的東西：相對(duì)于其他的隨機(jī)數(shù)生成函數(shù)，Python的random.randint()函數(shù)感覺很慢。 由于?randint()?是 Python 中最為常用的生成隨機(jī)整數(shù)的API，因此我決定深入挖掘其實(shí)現(xiàn)機(jī)制以了解其運(yùn)行效率較低的原因。

本文深入探討了 random 模塊的實(shí)現(xiàn)，并討論了一些更為快速的生成偽隨機(jī)整數(shù)的替代方法。

二、對(duì)randint()運(yùn)行效率的測(cè)試

首先，我們可以先觀察一下random.randint()的運(yùn)行效率：

$ 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

很明顯，在生成一個(gè)大小在[0, 128]中的隨機(jī)整數(shù)的成本，大約是在生成大小在[0, 1)之間的隨機(jī)浮點(diǎn)數(shù)的 20 倍。

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

接下來，我們將從python的源碼，來解析randint()的實(shí)現(xiàn)機(jī)制。

random.random()

首先從random()開始說。該函數(shù)定義在Lib/random.py文件中，函數(shù)random.random()?是Random類的random方法的別名，而Random.random()直接從_Random繼承了random方法。繼續(xù)向下追溯就會(huì)發(fā)現(xiàn)，random方法的真正定義是在Modules/_randommodule.c中實(shí)現(xiàn)的，其實(shí)現(xiàn)代碼如下：

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()?函數(shù)是一個(gè)C語言實(shí)現(xiàn)的梅森旋轉(zhuǎn)算法，其能夠快速生成偽隨機(jī)數(shù)。

總結(jié)一下，當(dāng)我們?cè)赑ython中調(diào)用random.random()時(shí)，該函數(shù)直接調(diào)用了C函數(shù)，而該C函數(shù)唯一的功能就是：生成隨機(jī)數(shù)，并將genrand_int32()的結(jié)果轉(zhuǎn)換為浮點(diǎn)數(shù)，除此之外沒有做任何額外的步驟。

random.randint()

現(xiàn)在讓我們看看randint()的實(shí)現(xiàn)代碼：

def randint(self, a, b):
    """Return random integer in range [a, b], including both end points.
    """
    return self.randrange(a, b+1)

randint函數(shù)會(huì)調(diào)用randrange()函數(shù)，因此我們?cè)儆^察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)

在調(diào)用下一層的函數(shù)之前，randrange()需要對(duì)于函數(shù)參數(shù)進(jìn)行大量的檢查。不過，如果我們不是用stop參數(shù)，那么檢查速度就會(huì)快一些，經(jīng)過一堆檢查之后，才可以調(diào)用_randbelow()方法。

默認(rèn)情況下，_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

從該函數(shù)的源碼可以發(fā)現(xiàn)：該函數(shù)的邏輯是計(jì)算出n的位數(shù)，而后按照位數(shù)生成隨機(jī)比特，因此當(dāng)n的大小不為2的次冪時(shí)，該函數(shù)可能需要多次調(diào)用getrandbits()。getrandbits()是一個(gè)利用C語言定義的函數(shù)，該函數(shù)最終也會(huì)調(diào)用?getrand_int32()，但由于該函數(shù)相對(duì)于 random() 函數(shù)需要更多的處理過程，導(dǎo)致其運(yùn)行速度慢兩倍。

總而言之，通過python代碼或者C代碼都可以調(diào)用由C所定義的函數(shù)。由于 Python 是字節(jié)碼解釋的，因此，任何在調(diào)用C函數(shù)之前的，用python語言定義的處理過程，都會(huì)導(dǎo)致函數(shù)的運(yùn)行速度比直接調(diào)用 C 函數(shù)慢很多。

這里有幾個(gè)實(shí)驗(yàn)可以幫助我們檢驗(yàn)這個(gè)假設(shè)。首先，讓我們嘗試在?randrange?中通過調(diào)用沒有stop參數(shù)的?randrange?來減少中間的參數(shù)檢查過程，提高程序執(zhí)行的速度：

$ python3 -m timeit -s 'import random' 'random.randrange(1)'
1000000 loops, best of 3: 0.784 usec per loop

正如預(yù)期的那樣，由于中間運(yùn)行過程的減少，此時(shí)randrange()運(yùn)行時(shí)間比原始的?randint()?好一些。可以在 PyPy 中重新運(yùn)行比較運(yùn)行時(shí)間。

$ 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

正如預(yù)期的那樣，PyPy 中這些調(diào)用之間的差異很小。

四、更快的生成隨機(jī)整數(shù)的方法

所以 randint() 結(jié)果非常慢。當(dāng)只需要生成少量隨機(jī)數(shù)的時(shí)候，可以忽視該函數(shù)帶來的性能損失，當(dāng)需要生成大量的隨機(jī)數(shù)時(shí)，就需要尋找一個(gè)效率夠高的方法。

random.random()

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

$ python3 -m timeit -s 'import random' 'int(128 * random.random())'
10000000 loops, best of 3: 0.193 usec per loop

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

直接使用 getrandbits()

另一種生成偽隨機(jī)整數(shù)的快速方法是直接使用 getrandbits()：

$ python3 -m timeit -s 'import random' 'random.getrandbits(7)'
10000000 loops, best of 3: 0.102 usec per loop

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

使用 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

生成單個(gè)數(shù)據(jù)的速度很慢。那是因?yàn)?Numpy 不適合僅用于單個(gè)數(shù)據(jù)：numpy能夠?qū)⒊杀緮備N在用 C語言 創(chuàng)建or操作的大型數(shù)組上。為了證明這一點(diǎn)，下邊給出了生成 100 個(gè)隨機(jī)整數(shù)所需時(shí)間：

$ python3 -m timeit -s 'import numpy.random' 'numpy.random.randint(128, size=100)'
1000000 loops, best of 3: 1.91 usec per loop

僅比生成單個(gè)慢 60%！ 每個(gè)整數(shù) 0.019 微秒，這是目前最快的方法——比調(diào)用?random.random()?快 3 倍。 這種方法如此之快的原因是Numpy將調(diào)用開銷分?jǐn)偟剿猩傻恼麛?shù)上，并且在 Numpy 內(nèi)部運(yùn)行一個(gè)高效的 C 循環(huán)來生成它們?？傊?，如果要生成大量隨機(jī)整數(shù)，建議使用 Numpy； 如果只是一次生成一個(gè)，它可能沒有特別高效。