两个解决方案之间的运行时差异很大:Project Euler#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运行.现在,我试图从另一个解决方案在这里.

解:

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初学者,我不明白为什么这两种方法有这么大的差异,我怎么能修改我的代码,使其更有效.

第二个问题:

在解决项目欧拉问题时,应该记住任何时间限制,并且我的代码真的是无效的.

Answer 1

在第一个版本中,您可以多次计算某些链的长度,因为它们是其他链中的子链.

在第二个解决方案中,由于缓存,您只计算每个链的长度一次.这种优化技术称为memoization.

记忆化的一个更引人注目的例子是Fibonacci数的计算.这是简单的递归解决方案:

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)使用此算法计算或更高.

通过缓存fib(x)每个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

有关

• 什么是memoization以及如何在Python中使用它？