大運行差異：Poject歐拉＃14

Question

我用下面的代碼解決Project Euler #14：

import time 
start_time = time.time() 
def collatz_problem(n): 
    count = 0 
    while n!=1: 
     if n%2==0: 
      n = n/2 
      count = count+1 
     elif n%2!=0: 
      n = 3*n+1 
      count = count +1 
    return count+1 


def longest_chain(): 
    max_len,num = 1,1 
    for i in xrange(13,1000000): 
     chain_length = collatz_problem(i) 
     if chain_length > max_len: 
      max_len = chain_length 
      num = i 

    return num 

print longest_chain() 
print time.time() - start_time, "seconds" 

上述解決方案花了大約~35 seconds運行。現在，我嘗試了here的另一個解決方案。

解決方案：

import time 
start_time = time.time() 
cache = { 1: 1 } 
def chain(cache, n): 
    if not cache.get(n,0): 
     if n % 2: cache[n] = 1 + chain(cache, 3*n + 1) 
     else: cache[n] = 1 + chain(cache, n/2) 
    return cache[n] 
m,n = 0,0 
for i in xrange(1, 1000000): 
    c = chain(cache, i) 
    if c > m: m,n = c,i 

print n 
print time.time() - start_time, "seconds" 

現在，這種解決方案只花了~3.5 seconds。

第一個問題：

現在，我是一個Python初學者我不明白爲什麼有那麼多在這兩種方法的差異以及如何修改我的代碼，使之更加effecient。

第二個問題：

在解決項目歐拉的問題是有沒有時間限制一個應該記住，是我的代碼真的那麼ineffecient。

Answer 1

在第一個版本中，您可能會多次計算某些鏈的長度，因爲它們是其他鏈中的子鏈。

在第二個解決方案中，您只計算每個鏈的長度，因爲緩存一次。這種優化技術被稱爲memoization。

---

一個更具戲劇性的例子是計算Fibonacci numbers。下面是簡單的遞歸解決方案：

def fib(n): 
    if n < 2: 
     return n 
    else: 
     return fib(n-1) + fib(n-2) 

這需要指數時間，因爲fib(n)評估fib(n-1)和fib(n-2)，但fib(n-1)還評估fib(n-2)，所以你最終再次做同樣的計算。嘗試使用此算法計算fib(35)或更高。

通過爲每個x緩存fib(x)的結果，您可以避免重新計算相同的結果，從而將性能提高到線性時間。

def fib2(n): 
    if n < 2: 
     return n 
    elif n in cache: 
     return cache[n] 
    else: 
     result = fib2(n-1) + fib2(n-2) 
     cache[n] = result 
     return result 

相關

• What is memoization and how can I use it in Python?