python - 为什么在 python 中使用指数取模更快？

Question

我试图优化我正在修补的程序，当我注意到执行 value = i % 65536 似乎比执行 value = i % (2* *16)。

为了对此进行测试，我运行了以下程序:

import cProfile
import pstats

AMOUNT = 100000000

def test1():
    for i in xrange(AMOUNT):
        value = i % 65536
    return

def test2():
    for i in xrange(AMOUNT):
        value = i % (256**2)
    return

def test3():
    for i in xrange(AMOUNT):
        value = i % (16**4)
    return

def test4():
    for i in xrange(AMOUNT):
        value = i % (4**8)
    return

def test5():
    for i in xrange(AMOUNT):
        value = i % (2**16)
    return

def run_tests():
    test1()
    test2()
    test3()
    test4()
    test5()
    return

if __name__ == '__main__':
    cProfile.run('run_tests()', 'results')
    stats = pstats.Stats('results')
    stats.sort_stats('calls', 'nfl')
    stats.print_stats()

...产生了以下输出:

Fri May 11 15:11:59 2012    results

         8 function calls in 40.473 seconds

   Ordered by: call count, name/file/line

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000   40.473   40.473 <string>:1(<module>)
        1    0.000    0.000   40.473   40.473 test.py:31(run_tests)
        1   10.466   10.466   10.466   10.466 test.py:6(test1)
        1    7.475    7.475    7.475    7.475 test.py:11(test2)
        1    7.485    7.485    7.485    7.485 test.py:16(test3)
        1    7.539    7.539    7.539    7.539 test.py:21(test4)
        1    7.508    7.508    7.508    7.508 test.py:26(test5)

使用 65536 最慢，为 10.466 秒，而使用 256**2 最快，为 7.475 秒(其他可能的指数值介于两者之间)。诚然，这种速度差异只有在大量重复的情况下才会明显，但我仍然很好奇为什么会出现这种情况。

为什么用 65536 取模比用指数取模慢？他们应该评估为相同的数字，我原以为 python 解释器在采用 mod 之前完全评估指数会花费更长的时间。

推而广之，在 python 表达式中使用 2 的幂通常比完全输入数字更有效吗？这种模式是否适用于模数以外的运算或 2 以外的其他数字？

(顺便说一句，我使用的是 Python 2.7.2(32 位)，并且我在 64 位 Windows 7 笔记本电脑上运行了上面的代码)。

编辑:
所以我尝试颠倒我调用的函数的顺序，现在正好相反。看起来无论 run_tests 中的第一个函数是什么，在使用 cProfile 时总是会运行得慢一些，这很很奇怪。所以，吸取教训，我猜 -- 分析器很奇怪 :D

Answer 1

生成的字节码没有区别，因为编译器完成了它的工作并优化了常量算术表达式。这意味着您的测试结果只是巧合(尝试以不同的顺序对函数计时!)。

>>> import dis
>>> dis.dis(test1)
  2           0 SETUP_LOOP              30 (to 33)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_GLOBAL              1 (AMOUNT)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               0 (i)

  3          19 LOAD_FAST                0 (i)
             22 LOAD_CONST               1 (65536)
             25 BINARY_MODULO       
             26 STORE_FAST               1 (value)
             29 JUMP_ABSOLUTE           13
        >>   32 POP_BLOCK           

  4     >>   33 LOAD_CONST               0 (None)
             36 RETURN_VALUE        
>>> dis.dis(test5)
  2           0 SETUP_LOOP              30 (to 33)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_GLOBAL              1 (AMOUNT)
              9 CALL_FUNCTION            1
             12 GET_ITER            
        >>   13 FOR_ITER                16 (to 32)
             16 STORE_FAST               0 (i)

  3          19 LOAD_FAST                0 (i)
             22 LOAD_CONST               3 (65536)
             25 BINARY_MODULO       
             26 STORE_FAST               1 (value)
             29 JUMP_ABSOLUTE           13
        >>   32 POP_BLOCK           

  4     >>   33 LOAD_CONST               0 (None)
             36 RETURN_VALUE        

(实际上是有区别的:数字存储在常量表中的不同偏移量处。不过，我无法想象这会造成任何差异)。

为了完整性，这里有一个使用 timeit 模块的正确测试:

import timeit

setup = "i = 1337"

best1 = best2 = float("inf")
for _ in range(5000):
  best1 = min(best1, timeit.timeit("i % 65536", setup=setup, number=10000))
for _ in range(5000):
  best2 = min(best2, timeit.timeit("i % (2**16)", setup=setup, number=10000))
print best1
print best2

请注意，我测量的是所需的最小 时间，而不是平均时间。如果由于某种原因需要更长的时间，这仅意味着它被更频繁地中断(因为代码除了 CPU 的能力外不依赖于任何东西)。