计算幂的速度（用python）-IT科技

计算幂的速度（用python）

2025-03-17 09:09:00

admin

原创

摘要：问题描述：我很好奇为什么在 Python 中乘法比幂运算快得多（尽管从我读过的内容来看，这在许多其他语言中也可能是正确的）。例如，执行x*x 比x**2 我认为 ** 运算符更通用，也可以处理小数幂。但如果这就是它速度慢得多的原因，那么它为什么不检查 int 指数，然后只进行乘法呢？编辑：这是我尝试过的一些示...

问题描述：

我很好奇为什么在 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 = 1,000,000，那么 pow1 需要 ~ 2500ms，而 pow2 需要 ~ 1700ms。

我承认，对于较大的 n 值，pow1 确实比 pow2 快得多。但这并不奇怪。

解决方案 1：

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

当然，对于较小的 n，简单的方法会更快，因为您实际上只实现了指数数学的一小部分，因此您的常数因子可以忽略不计。

解决方案 2：

添加检查也是一项开销。您总是希望进行这项检查吗？编译型语言可以检查常数指数，以查看它是否是一个相对较小的整数，因为没有运行时成本，只有编译时成本。解释型语言可能不会进行这项检查。

这取决于具体的实现，除非语言指定了此类细节。

Python 不知道您要输入什么指数分布。如果 99% 都是非整数值，您是否希望代码每次都检查整数，从而使运行时间变得更慢？

解决方案 3：

在指数检查中这样做会稍微减慢它不是简单的 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”，但要做到这一点要困难得多。例如，在我的例子中，这是不可能的，因为任何对象都可以传递给 square 函数。

解决方案 4：

使用二进制指数实现 b^p

def power(b, p):
    """
    Calculates b^p
    Complexity O(log p)
    b -> double
    p -> integer
    res -> double
    """
    res = 1

    while p:
        if p & 0x1: res *= b
        b *= b
        p >>= 1

    return res