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

Question

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

但是，当我提出我的代码，它显然需要很长时间来执行，并说时间已过。我不确定我的代码效率低下（看起来对我而言不是这样）还是I/O遇到问题。有一个9秒的时间限制，来解决最大值10级的输入，0 < = N < = 1个000 000 000

在Byteland它们具有非常奇怪的货币系统。

每个Bytelandian金币都写有一个整数。硬币 n可以在银行兑换成三个硬币：n/2,n/3和n/4。但是这些数字全部下调（银行必须盈利）。

您还可以出售美元的Bytelandian硬币。交易所 汇率为1：1。但你不能购买Bytelandian硬币。

你有一枚金币。您可以获得的最高金额是多少美元 ？

这里是我的代码：这似乎花费太长的时间为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

问题的输入是你的代码分支每次递归调用分为三个新的。这导致指数行为。

的好处却是，大多数电话是重复值：如果调用coinProfit与40，这将级联到：

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已经有一个内置的memoize函数叫做lru_cache，更多信息可以在here找到。

---

最后需要说明的是，@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秒的时间来计算。我想你刚刚编写的算法是非常正常的，因为它会再次计算相同的值（你没有按照其他答案中的建议来优化缓存的递归调用）。

而且，问题的定义是相当温和的，因为它坚持：每个Bytelandian金币有写上一个整数，但这些数字都四舍五入。认识到这一点，你应该把你的函数的三个第一线为：

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。