源码解析Python中randint函数的效率缺陷
本文深入剖析Python标准库中random.randint()函数运行缓慢的根本原因。通过对比random()与randint()的源码实现，揭示了参数校验、类型转换及位运算带来的额外开销。文章提供了三种更快的生成随机整数方法：利用random()缩放、直接调用getrandbits()以及使用Numpy批量生成，并附带具体性能测试数据，帮助开发者在大量随机数生成场景下做出最优选择。
一、前言
日前，在编写一个涉及差分隐私的简易程序时，我注意到一个异常现象：相较于其他随机数生成函数，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语言创建或操作的大型数组上。为了证明这一点，下边给出了生成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 内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
