如何改进分而治之的运行时间？

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 完成，我仍然需要它能够处理更大的基数和指数...也许将问题分成 2 个以上的子问题？

可以找到正在使用的记忆器here

Answer 1

您应该在此处使用的主要优化是公共子表达式消除。考虑您的第一段代码：

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 语句中，不需要在布尔子句两边加上括号，因为我们用分号结束子句（而在类 C 语法中，可以有一个1 行 if 语句，因此我们需要括号）。

这里的问题是您在 elif 和 else 两种情况下计算了两次 power(x, y // 2)。您应该尝试只计算一次该值。

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

利用数字在适当的上下文中自动转换为布尔值这一事实，其中 0 为 False，所有其他数字为 True。

您可以使用的最后一种方法是更数学化的方法。您可以使用对数计算指数。这将需要一个高精度的对数库来获得准确的答案，因为 base 是一个 320 位数字，对于 log 的普通 64 位双精度浮点算术版本来说太大了足够精确。这可能是最佳方法，但您必须进行更多研究。

无论哪种方式，请记住输出的大小将是一个需要超过 1 亿字节来存储的数字。所以无论你使用什么算法，都需要一段时间，因为即使是将答案存储在内存中并读出的“算法”也需要一段时间。

如何改进分而治之的运行时间？

How to improve divide-and-conquer runtimes?

python

recursion

divide-and-conquer