Python：为什么这么快？

Question

在Python的random模块中，梅森旋转算法的周期是2的19937次方减去1。简单来说，这个数字在二进制表示中有19937个连续的'1'（如果我没记错的话）。Python把这个数字转换成十进制的速度非常快：

$ python -m timeit '2**19937'
10000000 loops, best of 3: 0.0271 usec per loop

$ python -m timeit -s 'result = 0' 'result += 2**19937'
100000 loops, best of 3: 2.09 usec per loop

我猜第二种写法是需要转换的吧？

而且这不仅仅是二进制的转换。这个转换也很快。（我没有直接展示数字，而是展示转换成字符串后的长度）：

>>> import math
>>> N = 1000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
10787
>>> N = 5000
>>> s = str((int(N*math.e))**(int(N*math.pi)))
>>> len(s)
64921

计时：

python -m timeit -s 'import math' -s 'N=1000' 's = str((int(N*math.e))**(int(N*math.pi)))'
10 loops, best of 3: 51.2 msec per loop

问题是：这到底是怎么做到的呢？

我是不是太天真了，觉得这个过程很惊人？我觉得在Python命令行中瞬间生成一个大约5000位的数字，真是太神奇了。

编辑：

根据@dalke和@truppo的建议，增加了一些计时结果。

$ python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 230 usec per loop
$ python -m timeit 'x=2' 'int(x**19937)'
1000 loops, best of 3: 232 usec per loop
$ python -m timeit 'x=2' 'str(x**19937)'
100 loops, best of 3: 16.6 msec per loop

$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937'
1000 loops, best of 3: 237 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'int(result)'
1000 loops, best of 3: 238 usec per loop
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'str(result)'
100 loops, best of 3: 16.6 msec per loop

所以我觉得result = 0; result += 2**19937可能确实会强制进行转换。

Answer 1

在编译成字节码的时候，像 2**19937 这样的常量表达式会被优化成一个单一的常量：

>>> def foo(): return 2**10
... 
>>> import dis
>>> dis.dis(foo)
  1           0 LOAD_CONST               3 (1024)
              3 RETURN_VALUE        
>>> 

再考虑一下：

[~] python -m timeit 'x=2' 'x**19937'
1000 loops, best of 3: 210 usec per loop

Answer 2

不好意思打扰你，但其实它之所以这么快，是因为数学模块并不是用Python写的。

Python可以加载一些共享库，这些库提供了Python的接口，但它们是用其他语言实现的。比如，import math

Answer 3

Python把它转换成十进制的速度非常快。

我不太懂Python，但其实不需要这样做。2的19937次方不需要复杂的计算，它只是一个二进制的位移操作（用“<<”表示），位移19937位，所以速度非常快。只有在你要把它打印成十进制的时候，才需要真正的转换，而这个过程就慢多了。

补充说明：如果数字的底数和指数的底数相同，指数运算可以看作是位移（也就是移动小数点）。

比如：
10^-1 = 0.1
10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
10^n = 1（后面跟n个零）

你可以看到，10的n次方实际上就是把数字移动了小数点。现在计算机大多使用的是内部的二进制（比特），所以计算2的19937次方就是在第19937位上设置一个比特（从零开始计数）。
另外，转换成十进制通常是通过一种分而治之的算法来实现的，这个算法会不断地把数字除以十的幂。正如你所看到的，实际的转换速度慢了大约五十万倍。

第二个例子更有意思：当你用大整数m和n计算m^n时，最快的方法是连续相乘并存储临时结果。

举个例子：10^345

a = 10^2
b = a，a = 10^4
c = b，b = 10^16
d = c*c = 10^256

结果 = d*c*c*c*c*c*c*b*b*10

（可以进一步优化：参见Knuth的《半数算法》）

所以你只需要进行长乘法，而这个过程可以很有效地计算出来。

补充说明：乘法的具体实现方式有所不同：除了普通的学校乘法外，还使用Karatsuba、Tom-Cooke和Schoenhagen-Strasse（FFT）乘法。