为什么对于整数，2 * x * x比Python 3.x中的2 *(x * x)快? [英] Why is 2 * x * x faster than 2 * ( x * x ) in Python 3.x, for integers?

问题描述

以下Python 3.x整数乘法平均需要1.66s至1.77s:

import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
    # num += 2 * (x * x)
    num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))

如果我将2 * x * x替换为2 *(x * x)，则花费在2.04和2.25之间.怎么会来?

另一方面，在Java中则相反:2 * (x * x)在Java中更快. Java测试链接:为什么是2 *(i * i )比Java中的2 * i * i快?

我对该程序的每个版本运行了10次，结果如下.

   2 * x * x        |   2 * (x * x)
---------------------------------------
1.7717654705047607  | 2.0789272785186768
1.735931396484375   | 2.1166207790374756
1.7093875408172607  | 2.024367570877075
1.7004504203796387  | 2.047525405883789
1.6676218509674072  | 2.254328966140747
1.699510097503662   | 2.0949244499206543
1.6889283657073975  | 2.0841963291168213
1.7243537902832031  | 2.1290600299835205
1.712965488433838   | 2.1942825317382812
1.7622807025909424  | 2.1200053691864014

解决方案

首先，请注意，在Python 2.x中我们看不到相同的东西:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115

因此，这使我们相信这是由于Python 3中整数的变化所致，特别是Python 3在各处都使用了long(任意大整数).

对于足够小的整数(包括我们在此处考虑的整数)，CPython实际上仅使用O(MN)小学数字逐位乘法算法(对于较大的整数，它切换为 Karatsuba算法).您可以在源中自己看到.. >

x*x中的位数大约是2*x或x的两倍(因为log(x ² )= 2 log(x)).注意，在这种情况下，数字"不是以10为基数的数字，而是30位的值(在CPython的实现中被视为单数位).因此，对于循环的所有迭代，2是一个单一的数字值，而x和2*x是一个单一的数字值，而对于x >= 2**15，x*x是两个数字.因此，对于x >= 2**15，2*x*x仅需要单数一位乘法，而2*(x*x)要求单数一位和两位数乘法(因为x*x具有2 30-位数字).

这是查看此内容的直接方法(Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615

再次将其与Python 2进行比较，Python 2并非在各处都使用任意长度的整数:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973

(一个有趣的注释:如果您查看源代码，您会发现该算法实际上有一个特殊的数字平方(我们在这里做)，但是仍然不足以克服这一事实. 2*(x*x)只需要处理更多数字.)

The following Python 3.x integer multiplication takes on average between 1.66s and 1.77s:

import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
    # num += 2 * (x * x)
    num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))

if I replace 2 * x * x with 2 *(x * x), it takes between 2.04 and 2.25. How come?

On the other hand it is the opposite in Java: 2 * (x * x) is faster in Java. Java test link: Why is 2 * (i * i) faster than 2 * i * i in Java?

I ran each version of the program 10 times, here are the results.

   2 * x * x        |   2 * (x * x)
---------------------------------------
1.7717654705047607  | 2.0789272785186768
1.735931396484375   | 2.1166207790374756
1.7093875408172607  | 2.024367570877075
1.7004504203796387  | 2.047525405883789
1.6676218509674072  | 2.254328966140747
1.699510097503662   | 2.0949244499206543
1.6889283657073975  | 2.0841963291168213
1.7243537902832031  | 2.1290600299835205
1.712965488433838   | 2.1942825317382812
1.7622807025909424  | 2.1200053691864014

解决方案

First of all, note that we don't see the same thing in Python 2.x:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115

So this leads us to believe that this is due to how integers changed in Python 3: specifically, Python 3 uses long (arbitrarily large integers) everywhere.

For small enough integers (including the ones we're considering here), CPython actually just uses the O(MN) grade-school digit by digit multiplication algorithm (for larger integers it switches to the Karatsuba algorithm). You can see this yourself in the source.

The number of digits in x*x is roughly twice that of 2*x or x (since log(x²) = 2 log(x)). Note that a "digit" in this context is not a base-10 digit, but a 30-bit value (which are treated as single digits in CPython's implementation). Hence, 2 is a single-digit value, and x and 2*x are single-digit values for all iterations of the loop, but x*x is two-digit for x >= 2**15. Hence, for x >= 2**15, 2*x*x only requires single-by-single-digit multiplications whereas 2*(x*x) requires a single-by-single and a single-by-double-digit multiplication (since x*x has 2 30-bit digits).

Here's a direct way to see this (Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615

Again, compare this to Python 2, which doesn't use arbitrary-length integers everywhere:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973

(One interesting note: If you look at the source, you'll see that the algorithm actually has a special case for squaring numbers (which we're doing here), but even still this is not enough to overcome the fact that 2*(x*x) just requires processing more digits.)

这篇关于为什么对于整数，2 * x * x比Python 3.x中的2 *(x * x)快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！