计算能力的速度（python）

Question

我很好奇，为什么在python中乘法要比取幂快得多（尽管从我所读到的内容来看，在许多其他语言中也是如此）。比如说，这样做要快得多

x*x

比

x**2

我认为**算子更一般，也可以处理分数次幂。但如果这就是为什么它要慢得多，为什么它不检查一个int指数然后做乘法呢？

编辑：下面是我尝试的一些示例代码。。。

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=1000000，那么pow1需要约2500ms，pow2需要约1700ms。
我承认对于n的大值，pow1比pow2快得多。但这并不奇怪。

Answer 1

在指数检验中这样做会减缓不是简单的二次幂的情况，所以不一定是胜利。然而，在指数预先已知的情况下（例如使用文字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”，但是要解决这个问题要困难得多。在我的例子中，这是不可能的，因为任何对象都可以传递给square函数。

Answer 2

增加支票也是一项开支。你总是想要那张支票吗？编译语言可以检查常量指数，看看它是否是一个相对较小的整数，因为它没有运行时开销，只是编译时开销。解释过的语言可能无法进行这种检查。

这取决于特定的实现，除非这种详细信息是由语言指定的。

Python不知道您将为它提供什么样的指数分布。如果是99%的非整数值，是否希望代码每次都检查一个整数，从而使运行时更慢？

Answer 3

基本上简单的乘法是O（n），常数因子很低。取功率为O（log n），常数因子较高（有特殊情况需要测试。。。分数指数、负指数等）。编辑：为了清楚起见，这是O（n），其中n是指数。

当然，对于小n来说，这种简单的方法会更快，因为你只实现了指数数学的一小部分，所以你的常数因子可以忽略不计。