一、前言

前几天，在写一个与差分隐私相关的简单程序时，我发现了一些奇怪的东西：相对于其他的随机数生成函数，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； 如果只是一次生成一个，它可能没有特别高效。

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：mmqy2019@163.com进行举报，并提供相关证据，查实之后，将立刻删除涉嫌侵权内容。

猜你喜欢

• Playwright如何安装和使用，有哪些优势和局限

  Playwright是由微软公司2020年初发布的新一代自动化测试工具，相较于目前最常用的Selenium，本文就详细的介绍一下快速上手指南，对新手有一定的帮助，感兴趣的可以了解一下

• Python中的list.sort()方法应用于做什么，用法是怎样

  list.sort()方法是Python的列表方法，用于对原列表进行排序。本文详细的介绍了list.sort的具体使用，具有一定的参考价值，感兴趣的可以了解一下

• Python中怎么实现结巴分词且去掉除号

  这篇文章主要介绍了python文本处理的方案(结巴分词并去除符号)，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教

• Python中怎么用Django实现文件下载服务器

  这篇文章主要介绍了Python Django搭建文件下载服务器的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧

• Python中pluggy框架如何应用，详细的实例是怎样的

  这篇文章主要介绍了Python pluggy框架基础用法总结,本文通过三个例子结合代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下