Python - Memoization和Collat​​z序列

Question

当我在Project Euler中努力做问题14时,我发现我可以使用一个叫做memoization的东西来加速我的进程(我让它运行了15分钟,它仍然没有回复).问题是,我该如何实现它？我试过,但是我得到了一个keyerror(返回的值无效).这让我很烦,因为我很肯定我可以对此应用memoization并加快速度.

lookup = {}

def countTerms(n):
   arg = n
   count = 1
   while n is not 1:
      count += 1
      if not n%2:
         n /= 2
      else:
         n = (n*3 + 1)
      if n not in lookup:
         lookup[n] = count

   return lookup[n], arg

print max(countTerms(i) for i in range(500001, 1000000, 2)) 

谢谢.

Answer 1

还有一种很好的递归方法可以做到这一点，它可能会比 Poorsod 的解决方案慢，但它与您的初始代码更相似，因此可能更容易理解。

lookup = {}

def countTerms(n):
   if n not in lookup:
      if n == 1:
         lookup[n] = 1
      elif not n % 2:
         lookup[n] = countTerms(n / 2)[0] + 1
      else:
         lookup[n] = countTerms(n*3 + 1)[0] + 1

   return lookup[n], n

print max(countTerms(i) for i in range(500001, 1000000, 2))