我的短遞歸函數花費太長時間執行，如何優化它

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。