Python：为什么如此快？

Question

在模块random中使用的Mersenne Twister的周期（据我所知）是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 shell瞬间生成大约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 可能会强制转换。

- telliott99

---

请参见 http://stackoverflow.com/questions/867393/how-do-languages-such-as-python-overcome-cs-integral-data-limits。 - wich

你从未测试过Python将整数转换为10进制所需的时间。你需要执行：timeit 'str(2**19937)'。而你的第二个计时测试实际上是计算Python添加大数字的能力，也没有进行任何转换。 - Andrew Dalke

很明显，str()强制进行了转换。与简单的加法步骤相比，这会导致70倍的减速因素。 - Andrew Dalke

Answer 1

抱歉打击你的热情，但它之所以如此快，是因为Python实际上没有实现数学模块。Python支持加载导出Python API但在其他语言中实现的共享库。math.so提供了您从“import math”获取的模块（_random.so也是如此）。

- clee

---

自己找出来吧！http://svn.python.org/view/python/trunk/Modules/_math.c?view=markup :) - clee

哟！这就像是阅读原版的希腊语一样。但我会尝试一下，谢谢。 - telliott99

@telliott99 继续问我们字典为什么这么快吧。 :D - wisty

@wisty 我刚刚订了一本《编写优美代码》，所以我相信我会找到答案的。第18章由安德鲁·库克林撰写，专门讨论这个话题 ;) - telliott99

Answer 2

编译为字节码时，像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

- mthurlin

Answer 3

Python可以非常快地将其转换为十进制数。但是，不需要这样做。2^19937只需要进行二进制移位（“<<”）即可，因此速度非常快。仅当您以十进制打印时，实际转换才是必要的，而这会慢得多。指数运算可以与移位相同（=移动点），如果数字基数与指数基数相同。你看到，10的指数n次方只是将数字移位。现在，计算机大多使用内部基数2（位），因此计算2^19937是在位置19937（从零开始计算位位置）设置一个位。作为附加信息：十进制转换通常通过征服和分治算法实现，该算法依次将数字除以10的幂。正如您所见，实际转换速度慢了五十万倍。第二个例子更有趣：由于正在计算具有大整数m，n的m^n，因此最快的方法是连续乘以它并存储临时结果。因此，您只需要长时间乘法，它们可以相当有效地计算。精确的乘法实现取决于：除了正常的学校乘法Karatsuba，Tom-Cooke和Schoenhagen-Strasse（FFT）乘法也被使用。

- Thorsten S.

---

@Thorsten S.，显然我已经超出了我的能力范围，但我不确定你是正确的。乘法只是一个简单的二进制移位，一旦你弄清楚要移动多少位，但是指数运算怎么可能相同呢？这是通过第二步乘法来得到位数的，对吧？ - telliott99

Answer 4

我对Python中这个实际的实现知之甚少，但考虑到这基本上是原始乘法和对数，我并不感到惊讶，即使在相当大的数字上也能保持相当快的速度。

有一些任意精度数学库，例如GMP，它们以汇编优化的方式非常有效地实现了各种操作，专门用于此目的。

- Jakob Borg