源码解析python中randint函数的效率缺陷
作者:??bastgia???? 发布时间:2023-01-24 01:23:54
一、前言
前几天,在写一个与差分隐私相关的简单程序时,我发现了一些奇怪的东西:相对于其他的随机数生成函数,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
猜你喜欢
- 疑问在调用socket的时候,我们会使用到listen()函数,里面有个参数叫backlog, 例如:socket.listen(5). 那
- 1、$_SERVER$_SERVER超级全局变量包含由web服务器创建的信息,它提供了服务器和客户配置及当前请求环境的有关信息。根据服务器不
- 如何让我的网页自动适应客户端的屏幕分辨率?然后用下列办法进行自动推送:<% @language="vbscript
- js中用import导入模块和用require导入模块的区别JavaScript中,模块是一种可重用的代码块,它将一些代码打包成一个单独的单
- 信息架构的组件可以拆分成四类组织系统 如何组织信息,例如,依据主题或年代顺序。标签系统 如何表示信息,例如,科学术语(“Acer”)或通俗术
- 本文实例讲述了python中os操作文件及文件路径的方法。分享给大家供大家参考。具体分析如下:python获取文件上一级目录:取文件所在目录
- 微软现在已经进入了ASP.NET 2.0和Visual Web Developer 2005发布版最
- 嗯,你可以说我很无聊。最近疯狂加班,今天才得以有时间搞一个CSS的像素图来消遣休息下。先看效果:运行代码框<!DOCTYPE html
- Array(数组)内部机制在 Go 语言中数组是固定长度的数据类型,它包含相同类型的连续的元素,这些元素可以是内建类型,像数字和字符串,也可
- 前后端分离前后端分离的好处最大的好处就是前端JS可以做很大部分的数据处理工作,对服务器的压力减小到最小。后台错误不会直接反映到前台,错误接秒
- 在运维场景下,我们经常需要在服务器上用正则表达式来匹配IP地址。shell和其它编程语言一样,也可以使用正则分组捕获,不过不能使用 $1或\
- 以前做音乐项目的时候,最让我们头痛的就是满足用户的问题。在音乐的领域,不要试图去满足所有用户这个定律得到了最充分的验证。究其原因,无非是音乐
- asp学习入门经验介绍,本文初步介绍了初学asp的一些相关知识,如VBScript语法简介,循环控制语句的使用,asp数据库的简单操作查询,
- PHP现在推出5.3.0版本了,不过下载的时候有几个不同版本选择。那就是VC6 X86和VC9 X86。首先我来解答:VC6是什么?VC6就
- <? //以树型结构列出指定目录里的所有文件,如果你想知道自己某个目录里有哪些子目录和文件,可以调用这个类来查看,很方便的。 &nbs
- 目录单例模式反射hasattergetattrsetattr总结单例模式一般情况下,类可以生成任意个实例,而单例模式只生成一个实例我们先用单
- 前提:因为本文主要围绕着在thinkPHP5中使用redis的,所以关于redis的安装就不特意说明了,不过在这稍微提醒一下,安装完redi
- 如果网站只开了80端口,你会发现下面的方法是比较有用的,其中用的方法几乎都不是我发现的,文总包括一些注入时的个人经验和技巧方法可以说有4种(
- 在以前的日志中讲了怎么制作验证码,这篇就讲讲怎么给验证码加上起干扰效果的杂点。 其实很简单,首先做一个
- 本文实例讲述了javascript二维数组转置的方法。分享给大家供大家参考。具体实现方法如下:<script language=&qu