时间戳

首页 > 解决方案 > 如何改善分而治之的运行时间？

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

问题描述

当分而治之的递归函数不能产生足够低的运行时间时，还可以进行哪些其他改进？

比如说，这个power函数取自这里：

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

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

标签： pythonrecursiondivide-and-conquer

解决方案

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

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. 最后，在ifandwhile语句中，不需要在布尔子句周围加上括号，因为我们以分号结束子句（而在类似 C 的语法中，可以有一个 1 行if语句，因此我们需要括号） .

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

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 位的数字，对于普通的 64 位双精度浮点算术版本来说太大而log不够精确。这可能是最佳方法，但您必须进行更多研究。

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

推荐阅读