我的短递归函数执行时间太长，如何优化它

Question

我正在尝试在CodeChef上解决这个问题：http://www.codechef.com/problems/COINS

但是当我提交代码时，显然执行时间太长，并说时间已过。 我不确定我的代码是否效率低下（对我来说似乎不像），或者我是否遇到了 I/O 问题。 有 9 秒的时间限制，最多求解 10 个输入，0 <= n <= 1 000 000 000

。

在拜特兰，他们有一个非常奇怪的货币体系。

每枚字节兰金币上都写着一个整数。一枚硬币 n可以在银行兑换成三种硬币：n/2，n/3和n/4。但 这些数字都是四舍五入的（银行必须盈利）。

您也可以以美元出售字节兰硬币。交易所 比率为1：1。但是你不能买到字节兰硬币。

你有一枚金币。美元的最大金额是多少 你能得到它吗？

这是我的代码：输入 1 000 000

000 似乎花费的时间太长

def coinProfit(n):
    a = n/2
    b = n/3
    c = n/4
    if a+b+c > n:
        nextProfit = coinProfit(a)+coinProfit(b)+coinProfit(c)
        if nextProfit > a+b+c:
            return nextProfit
        else:
            return a+b+c
    return n
while True:
    try:
        n = input()
        print(coinProfit(n))
    except Exception:
        break

Answer 1

问题是您的代码将每个递归调用分支为三个新调用。这会导致指数行为。

然而，好消息是大多数调用都是重复的：如果您使用 40 调用coinProfit，这将级联到：

coinProfit(40)
 - coinProfit(20)
    - coinProfit(10)
    - coinProfit(6)
    - coinProfit(5)
 - coinProfit(13)
 - coinProfit(10)

你看到的是重复了很多努力（在这个小例子中，coinProfit已经在10上调用了两次）。

您可以使用动态规划来解决此问题：存储较早的计算结果，防止您再次在此部件上进行分支。

一个人可以自己实现动态编程，但可以使用@memoize装饰器自动执行此操作。

现在，该函数做了很多工作太多次。

import math;
def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper
@memoize
def coinProfit(n):
    a = math.floor(n/2)
    b = math.floor(n/3)
    c = math.floor(n/4)
    if a+b+c > n:
        nextProfit = coinProfit(a)+coinProfit(b)+coinProfit(c)
        if nextProfit > a+b+c:
            return nextProfit
        else:
            return a+b+c
    return n

@memoize转换函数，以便：对于函数，维护已计算输出的数组。如果对于给定的输入，输出已经计算完毕，则将其存储在数组中，并立即返回。否则，它将按照您的方法的定义进行计算，存储在数组中（供以后使用）并返回。

正如@steveha指出的那样，python已经有一个名为lru_cache的内置memoize函数，更多信息可以在这里找到。

<小时 />

最后需要注意的是，@memoize或其他动态规划结构并不是所有效率问题的解决方案。首先，@memoize会对副作用产生影响：假设您的函数在stdout上打印某些内容，然后@memoize这将对打印内容的次数产生影响。其次，存在像SAT问题这样的问题，@memoize根本不起作用，因为上下文本身是指数级的（据我们所知）。这样的问题被称为NP-hard。

Answer 2

您可以通过在某种cache中存储结果来优化程序。所以如果结果存在于cache那么就不需要执行计算，否则计算并将值放在cache中。通过这种方式，您可以避免计算已计算的值。例如

cache = {0: 0}

def coinProfit(num):
    if num in cache:
        return cache[num]
    else:
        a = num / 2
        b = num / 3
        c = num / 4
        tmp = coinProfit(c) + coinProfit(b) + coinProfit(a)
        cache[num] = max(num, tmp)
        return cache[num]

while True:
    try:
        print coinProfit(int(raw_input()))
    except:
        break

Answer 3

我刚刚尝试并注意到了一些事情......这不必被视为答案。

在我的（最近的）机器上，使用 n = 100 000 000 计算需要 30 秒。我想对于您刚刚编写的算法来说，这是很正常的，因为它一次又一次地计算相同的值（您没有按照其他答案中的建议使用缓存优化递归调用）。

此外，问题定义非常温和，因为它坚持：每个字节兰金币上都写着一个整数，但这些数字都是向下舍入的。知道了这一点，你应该将函数的前三行转换为：

import math
def coinProfit(n):
    a = math.floor(n/2)
    b = math.floor(n/3)
    c = math.floor(n/4)

这将防止a, b, c变成float数字（至少是Python3），这将使您的计算机疯狂地陷入一个大的递归混乱，即使使用最小的n值。