divmod()比使用%和//运算符更快吗？

Question

我从汇编中记得整数除法指令同时产生商和余数.因此,在python中,内置的divmod()函数比使用%和//运算符更好地表现性能(假设当然需要商和余数)？

q, r = divmod(n, d)
q, r = (n // d, n % d)

Answer 1

测量是要知道(Macbook Pro 2.8Ghz i7上的所有时间):

>>> import sys, timeit
>>> sys.version_info
sys.version_info(major=2, minor=7, micro=12, releaselevel='final', serial=0)
>>> timeit.timeit('divmod(n, d)', 'n, d = 42, 7')
0.1473848819732666
>>> timeit.timeit('n // d, n % d', 'n, d = 42, 7')
0.10324406623840332

这个divmod()功能处于劣势,因为您每次都需要查找全局.将它绑定到本地(计时器中的所有变量timeit都是本地的)可以稍微提高性能:

>>> timeit.timeit('dm(n, d)', 'n, d = 42, 7; dm = divmod')
0.13460898399353027

但是运算符仍然会赢,因为它们在divmod()执行函数调用时不必保留当前帧:

>>> import dis
>>> dis.dis(compile('divmod(n, d)', '', 'exec'))
  1           0 LOAD_NAME                0 (divmod)
              3 LOAD_NAME                1 (n)
              6 LOAD_NAME                2 (d)
              9 CALL_FUNCTION            2
             12 POP_TOP             
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE        
>>> dis.dis(compile('(n // d, n % d)', '', 'exec'))
  1           0 LOAD_NAME                0 (n)
              3 LOAD_NAME                1 (d)
              6 BINARY_FLOOR_DIVIDE 
              7 LOAD_NAME                0 (n)
             10 LOAD_NAME                1 (d)
             13 BINARY_MODULO       
             14 BUILD_TUPLE              2
             17 POP_TOP             
             18 LOAD_CONST               0 (None)
             21 RETURN_VALUE        

在//和%变种使用更多的操作码,但CALL_FUNCTION字节码是熊,性能明智的.

在PyPy中,对于小整数而言,并没有太大的区别; 在C整数运算的绝对速度下,操作码融化的小速度优势:

>>>> import platform, sys, timeit
>>>> platform.python_implementation(), sys.version_info
('PyPy', (major=2, minor=7, micro=10, releaselevel='final', serial=42))
>>>> timeit.timeit('divmod(n, d)', 'n, d = 42, 7', number=10**9)
0.5659301280975342
>>>> timeit.timeit('n // d, n % d', 'n, d = 42, 7', number=10**9)
0.5471200942993164

(我不得不将重复次数增加到10亿,以显示实际差异有多小,PyPy在这里速度非常快).

但是,当数字变大时,divmod() 赢得一个国家英里:

>>>> timeit.timeit('divmod(n, d)', 'n, d = 2**74207281 - 1, 26', number=100)
17.620037078857422
>>>> timeit.timeit('n // d, n % d', 'n, d = 2**74207281 - 1, 26', number=100)
34.44323515892029

(与hobbs的数字相比,我现在不得不将重复次数调低 10倍,只是为了在合理的时间内得到结果).

这是因为PyPy不再可以将这些整数解包为C整数; 你可以看到使用sys.maxint和时间之间的显着差异sys.maxint + 1:

>>>> timeit.timeit('divmod(n, d)', 'import sys; n, d = sys.maxint, 26', number=10**7)
0.008622884750366211
>>>> timeit.timeit('n // d, n % d', 'import sys; n, d = sys.maxint, 26', number=10**7)
0.007693052291870117
>>>> timeit.timeit('divmod(n, d)', 'import sys; n, d = sys.maxint + 1, 26', number=10**7)
0.8396248817443848
>>>> timeit.timeit('n // d, n % d', 'import sys; n, d = sys.maxint + 1, 26', number=10**7)
1.0117690563201904

Answer 2

如果您使用"小"本机整数,Martijn的答案是正确的,其中算术运算与函数调用相比非常快.然而,对于bigints,这是一个完全不同的故事:

>>> import timeit
>>> timeit.timeit('divmod(n, d)', 'n, d = 2**74207281 - 1, 26', number=1000)
24.22666597366333
>>> timeit.timeit('n // d, n % d', 'n, d = 2**74207281 - 1, 26', number=1000)
49.517399072647095

当划分一个2200万位的数字时,divmod的速度几乎是分区和模数的两倍,正如您所预期的那样.

在我的机器上,交叉发生在2 ^ 63左右的某个地方,但是不接受我的话.正如Martijn所说,衡量!当表现真的很重要时,不要认为在一个地方保持真实的东西在另一个地方仍然是真的.