python - 如何改善分而治之的运行时间？

Question

当分而治之的递归函数不能产生足够低的运行时间时，还可以进行哪些其他改进？
比如说，这个 power函数取自 here :

def power(x, y):
    if (y == 0): return 1
    elif (int(y % 2) == 0):
        return (power(x, int(y / 2)) * power(x, int(y / 2)))
    else:
        return (x * power(x, int(y / 2)) * power(x, int(y / 2)))

由于它是递归的， memoizing and tail recursion (不确定它是否可以与分而治之一起应用)可以提供很大帮助，但我不知道有任何其他调整。对于我的基准，我正在使用:

base = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
exponent = 1000000

以 301.140625s完成，我仍然需要它能够处理更大的基数和指数......也许将问题分成两个以上的子问题？
正在使用的内存器可以找到 here

Answer 1

您应该在这里使用的主要优化是公共(public)子表达式消除。考虑您的第一段代码:

def power(x, y):
    if y == 0: 
        return 1
    elif y % 2 == 0:
        return (power(x, y // 2) * power(x, y // 2)
    else:
        return (x * power(x, y // 2) * power(x, y // 2)

我稍微清理了一下 - 因为 y是 int , y % 2也将是 int因此无需转换类型。以及规范的书写方式 int(y / 2)是 y // 2 .最后，在 if和 while语句，不需要在 bool 子句周围加上括号，因为我们用分号结束子句(而在类似 C 的语法中，可能有 1 行 if 语句，因此我们需要括号)。
这里的问题是您正在计算 power(x, y // 2)两次 elif和 else案例。相反，您应该尝试只计算一次该值。

def power(x, y):
    if (y == 0): 
        return 1
    else:
        smaller_power = power(x, y // 2)
        if y % 2 == 1:
            return x * smaller_power * smaller_power
        else:
            return smaller_power * smaller_power

这会立即显着提高算法的效率。而不是 O(y)及时，改进的版本是 O(log y)及时(假设我们将单个 * 计为 1 次操作)。
稍微聪明点，我们可以想出一个稍微不同的算法:

def power(x, y):
    if y == 0:
        return 1
    else:
        smaller_power = power(x * x, y // 2)
        return x * smaller_power if y % 2 == 1 else smaller_power

可以转换为以下尾递归版本:

def power_tail_helper(x, y, acc):
    """
    returns acc * power(x, y)
    """
    if y == 0:
        return acc
    else:
        new_acc = acc * x if y % 2 == 1 else acc
        return power_tail_helper(x * x, y // 2, new_acc)

def power_tail(x, y):
    return power_tail_helper(x, y, 1)

这又可以变成以下迭代算法:

def power_iter(x, y):
    acc = 1
    while y != 0:
        (x, y, acc) = (x * x, y // 2, acc * x if y % 2 == 1 else acc)
    return acc

请注意，在惯用的 Python 中，我们会将其写为

def power_iter(x, y):
    acc = 1
    while y:
        x, y, acc = (x * x, y // 2, acc * x if y % 2 else acc)
    return acc

使用数字在适当的上下文中自动转换为 bool 值的事实，其中 0 为 False和所有其他数字是 True .
您可以使用的最后一种方法是更数学的方法。您可以使用对数计算指数。这需要高精度的对数库才能得到准确的答案，因为 base是一个 320 位的数字，对于 log 的普通 64 位 double 浮点算术版本来说太大了。足够精确。这可能是最佳方法，但您必须进行更多研究。
无论哪种方式，请记住，输出的大小将是一个需要超过 1 亿字节来存储的数字。因此，无论您使用哪种算法，都需要一段时间，因为即使是将答案存储在内存中并读出它的“算法”也需要一段时间。