大运行差异：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?