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

Question

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

但是当我提交我的代码时，它显然需要很长时间来执行，并且说时间已经过期。我不确定我的代码是低效的（我觉得不是这样），还是I/O有问题。有9秒的时间限制，可以解决最多10个输入，0<；=n<；=1 000 000 000。在

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

这是我的代码：输入1000000000似乎花费了太长的时间

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

我只是试着注意到一些事情。。。这不必被认为是答案。在

在我最近的机器上，用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。在

Answer 2

您可以通过将结果存储在某种类型的cache中来优化程序。因此，如果结果存在于cache中，则无需执行计算，否则计算并将值放入cache。这样可以避免计算已计算的值。E、 g

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

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

不过，好的一点是，大多数调用都是重复的：如果用40调用coinProfit，这将级联到：

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

您看到的是大量的工作被重复（在这个小例子中，coinProfit已经在10上调用了两次）。在

您可以使用动态编程来解决这个问题：存储以前的计算结果，防止您在这部分上再次分支。在

可以自己实现动态编程，但可以使用@memoize修饰符自动执行此操作。在

现在这个函数做了很多工作。在

^{pr2}$

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

正如@steveha指出的，python已经有一个内置的memoize函数，称为lru_cache，更多信息可以在here中找到。在

---

A final note is that @memoize or other Dynamic programming constructs, are not the solution to all efficiency problems. First of all @memoizecan have an impact on side-effects: say your function prints something on stdout, then with @memoize this will have an impact on the number of times something is printed. And secondly, there are problems like the SAT problem where @memoize simply doesn't work at all, because the context itself is exponential (this as far as we know). Such problems are called NP-hard.