计算幂的速度（在Python中）

Question

我很好奇为什么在Python中，乘法运算比取幂运算要快得多（据我所知，这在很多其他编程语言中也可能是这样）。比如说，进行以下乘法运算要比进行幂运算快很多：

x*x

而不是：

x**2

我想，**这个运算符更通用，可以处理分数幂。但如果这就是它慢的原因，为什么不先检查一下指数是不是整数，然后直接进行乘法呢？

补充：这是我尝试的一些示例代码……

def pow1(r, n):
  for i in range(r):
    p = i**n

def pow2(r, n):
  for i in range(r):
    p = 1
    for j in range(n):
      p *= i

现在，pow2只是一个快速示例，显然没有经过优化！
即便如此，我发现当n = 2，r = 1,000,000时，pow1大约需要2500毫秒，而pow2大约需要1700毫秒。
我承认，对于较大的n值，pow1确实比pow2快得多。但这也不算太意外。

Answer 1

在检查指数时，如果不是简单的2的幂，这样做会稍微减慢速度，所以不一定是个好主意。不过，如果事先知道指数（比如用字面量2），生成的字节码可以通过简单的“窥视优化”来提高效率。可能是因为这个情况比较特殊，所以没有人觉得值得去做。

这里有一个简单的概念验证，展示了这种优化（可以作为装饰器使用）。注意：你需要安装byteplay模块才能运行它。

import byteplay, timeit

def optimise(func):
    c = byteplay.Code.from_code(func.func_code)
    prev=None
    for i, (op, arg) in enumerate(c.code):
        if op == byteplay.BINARY_POWER:
            if c.code[i-1] == (byteplay.LOAD_CONST, 2):
                c.code[i-1] = (byteplay.DUP_TOP, None)
                c.code[i] = (byteplay.BINARY_MULTIPLY, None)
    func.func_code = c.to_code()
    return func

def square(x):
    return x**2

print "Unoptimised :", timeit.Timer('square(10)','from __main__ import square').timeit(10000000)
square = optimise(square)
print "Optimised   :", timeit.Timer('square(10)','from __main__ import square').timeit(10000000)

这段代码的执行时间是：

Unoptimised : 6.42024898529
Optimised   : 4.52667593956

[编辑] 其实再想想，这个优化不被实现是有很好的理由的。没有保证说不会有人创建一个用户自定义的类，重写了__mul__和__pow__方法，并且对每个方法做不同的处理。安全地实现这个优化的唯一方法是确保栈顶的对象在计算“x**2”和“x*x”时有相同的结果，但要做到这一点要复杂得多。例如，在我的例子中，这是不可能的，因为任何对象都可以传递给平方函数。

Answer 2

加一个检查是要花费资源的。你总是希望这个检查存在吗？在编译型语言中，可以在编译的时候检查一个常量的指数是否是一个相对较小的整数，因为这样只会在编译时消耗资源，而不会在运行时增加负担。而解释型语言可能就不会进行这样的检查。

这要看具体的实现，除非语言本身规定了这种细节。

Python并不知道你会输入什么样的指数。如果你输入的99%都是非整数值，你还希望代码每次都检查一下是否是整数吗？这样会让运行速度变得更慢。

Answer 3

简单来说，普通的乘法运算时间复杂度是O(n)，这个n就是你要乘的次数，常数因子很小。而求幂运算的时间复杂度是O(log n)，这里的n是指数，常数因子相对较大（还有一些特殊情况需要注意，比如分数指数、负指数等等）。编辑：为了更清楚，这里的O(n)是指n是指数的值。

当然，对于小的n，普通的方法会更快，因为你只是在做一些简单的指数运算，所以常数因子的影响可以忽略不计。