一、前言

前几天,在写一个与差分隐私相关的简单程序时,我发现了一些奇怪的东西:相对于其他的随机数生成函数,Python的random.randint()函数感觉很慢。 由于randint()是 Python 中最为常用的生成随机整数的API,因此我决定深入挖掘其实现机制以了解其运行效率较低的原因。

二、对randint()运行效率的测试

首先,我们可以先观察一下random.randint()的运行效率:

$python3-mtimeit-s'importrandom''random.random()'10000000loops,bestof3:0.0523usecperloop$python3-mtimeit-s'importrandom''random.randint(0,128)'1000000loops,bestof3:1.09usecperloop

很明显,在生成一个大小在[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中实现的,其实现代码如下:

staticPyObject*random_random(RandomObject*self,PyObject*Py_UNUSED(ignored)){uint32_ta=genrand_int32(self)>>5,b=genrand_int32(self)>>6;returnPyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));}

其中getrand_int32()函数是一个C语言实现的梅森旋转算法,其能够快速生成伪随机数。

总结一下,当我们在Python中调用random.random()时,该函数直接调用了C函数,而该C函数唯一的功能就是:生成随机数,并将genrand_int32()的结果转换为浮点数,除此之外没有做任何额外的步骤。

random.randint()

现在让我们看看randint()的实现代码:

defrandint(self,a,b):"""Returnrandomintegerinrange[a,b],includingbothendpoints."""returnself.randrange(a,b+1)

randint函数会调用randrange()函数,因此我们再观察randrange()的源码。

defrandrange(self,start,stop=None,step=1,_int=int):"""Choosearandomitemfromrange(start,stop[,step]).Thisfixestheproblemwithrandint()whichincludestheendpoint;inPythonthisisusuallynotwhatyouwant."""#Thiscodeisabitmessytomakeitfastforthe#commoncasewhilestilldoingadequateerrorchecking.istart=_int(start)ifistart!=start:raiseValueError("non-integerarg1forrandrange()")ifstopisNone:ifistart>0:returnself._randbelow(istart)raiseValueError("emptyrangeforrandrange()")#stopargumentsupplied.istop=_int(stop)ifistop!=stop:raiseValueError("non-integerstopforrandrange()")width=istop-istartifstep==1andwidth>0:returnistart+self._randbelow(width)ifstep==1:raiseValueError("emptyrangeforrandrange()(%d,%d,%d)"%(istart,istop,width))#Non-unitstepargumentsupplied.istep=_int(step)ifistep!=step:raiseValueError("non-integerstepforrandrange()")ifistep>0:n=(width+istep-1)//istepelifistep<0:n=(width+istep+1)//istepelse:raiseValueError("zerostepforrandrange()")ifn<=0:raiseValueError("emptyrangeforrandrange()")returnistart+istep*self._randbelow(n)

在调用下一层的函数之前,randrange()需要对于函数参数进行大量的检查。不过,如果我们不是用stop参数,那么检查速度就会快一些,经过一堆检查之后,才可以调用_randbelow()方法。

默认情况下,_randbelow()被映射到_randbelow_with_getrandbits():

def_randbelow_with_getrandbits(self,n):"Returnarandomintintherange[0,n).RaisesValueErrorifn==0."getrandbits=self.getrandbitsk=n.bit_length()#don'tuse(n-1)herebecausencanbe1r=getrandbits(k)#0<=r<2**kwhiler>=n:r=getrandbits(k)returnr

从该函数的源码可以发现:该函数的逻辑是计算出n的位数,而后按照位数生成随机比特,因此当n的大小不为2的次幂时,该函数可能需要多次调用getrandbits()。getrandbits()是一个利用C语言定义的函数,该函数最终也会调用getrand_int32(),但由于该函数相对于 random() 函数需要更多的处理过程,导致其运行速度慢两倍。

总而言之,通过python代码或者C代码都可以调用由C所定义的函数。由于 Python 是字节码解释的,因此,任何在调用C函数之前的,用python语言定义的处理过程,都会导致函数的运行速度比直接调用 C 函数慢很多。

这里有几个实验可以帮助我们检验这个假设。首先,让我们尝试在randrange中通过调用没有stop参数的randrange来减少中间的参数检查过程,提高程序执行的速度:

$python3-mtimeit-s'importrandom''random.randrange(1)'1000000loops,bestof3:0.784usecperloop

正如预期的那样,由于中间运行过程的减少,此时randrange()运行时间比原始的randint()好一些。可以在 PyPy 中重新运行比较运行时间。

$pypy-mtimeit-s'importrandom''random.random()'100000000loops,bestof3:0.0139usecperloop$pypy-mtimeit-s'importrandom''random.randint(0,128)'100000000loops,bestof3:0.0168usecperloop

正如预期的那样,PyPy 中这些调用之间的差异很小。

四、更快的生成随机整数的方法

所以 randint() 结果非常慢。当只需要生成少量随机数的时候,可以忽视该函数带来的性能损失,当需要生成大量的随机数时,就需要寻找一个效率够高的方法。

random.random()

一个技巧就是使用random.random()代替,乘以我们的整数限制从而得到整数,由于random()可以生成均匀的[0,1)分布,因此扩展之后也可以得到整数上的均匀分布:

$python3-mtimeit-s'importrandom''int(128*random.random())'10000000loops,bestof3:0.193usecperloop

这为我们提供了 [0, 128)范围内的伪随机整数,速度更快。需要注意的是:Python 以双精度表示其浮点数,精度为 53 位。当限制超过 53 位时,我们将使用此方法获得的数字不是完全随机的,多的位将丢失。如果不需要这么大的整数,就可以忽视这个问题。

直接使用 getrandbits()

另一种生成伪随机整数的快速方法是直接使用 getrandbits():

$python3-mtimeit-s'importrandom''random.getrandbits(7)'10000000loops,bestof3:0.102usecperloop

此方法快速,但是生成数据范围有限:它支持的范围为[0,2^n]。如果我们想限制范围,取模的方法无法做到范围的限制——这会扭曲分布;因此,我们必须使用类似于上面示例中的_randbelow_with_getrandbits()中的循环。但是会减慢速度。

使用 Numpy.random

最后,我们可以完全放弃 random 模块,而使用 Numpy:

$python3-mtimeit-s'importnumpy.random''numpy.random.randint(128)'1000000loops,bestof3:1.21usecperloop

生成单个数据的速度很慢。那是因为 Numpy 不适合仅用于单个数据:numpy能够将成本摊销在用 C语言 创建or操作的大型数组上。为了证明这一点,下边给出了生成 100 个随机整数所需时间:

$python3-mtimeit-s'importnumpy.random''numpy.random.randint(128,size=100)'1000000loops,bestof3:1.91usecperloop

仅比生成单个慢 60%! 每个整数 0.019 微秒,这是目前最快的方法——比调用random.random()快 3 倍。 这种方法如此之快的原因是Numpy将调用开销分摊到所有生成的整数上,并且在 Numpy 内部运行一个高效的 C 循环来生成它们。总之,如果要生成大量随机整数,建议使用 Numpy; 如果只是一次生成一个,它可能没有特别高效。

“python中randint函数的效率缺陷实例分析”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注本站网站,小编将为大家输出更多高质量的实用文章!