Python - Memoization和Collatz序列

Question

当我在努力做Problem 14 in Project Euler时，我发现我可以使用一种叫做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))

Answer 2

对于Collatz序列，记忆的要点是避免计算列表中已经完成的部分。序列的其余部分完全由当前值确定。因此，我们希望尽可能频繁地检查表，并尽快摆脱剩余的计算。

def collatz_sequence(start, table={}):  # cheeky trick: store the (mutable) table as a default argument
    """Returns the Collatz sequence for a given starting number"""
    l = []
    n = start

    while n not in l:  # break if we find ourself in a cycle
                       # (don't assume the Collatz conjecture!)
        if n in table:
            l += table[n]
            break
        elif n%2 == 0:
            l.append(n)
            n = n//2
        else:
            l.append(n)
            n = (3*n) + 1

    table.update({n: l[i:] for i, n in enumerate(l) if n not in table})

    return l

它起作用了吗？让我们对其进行监视，以确保正在使用已记录的元素：

class NoisyDict(dict):
    def __getitem__(self, item):
        print("getting", item)
        return dict.__getitem__(self, item)

def collatz_sequence(start, table=NoisyDict()):
    # etc



In [26]: collatz_sequence(5)
Out[26]: [5, 16, 8, 4, 2, 1]

In [27]: collatz_sequence(5)
getting 5
Out[27]: [5, 16, 8, 4, 2, 1]

In [28]: collatz_sequence(32)
getting 16
Out[28]: [32, 16, 8, 4, 2, 1]

In [29]: collatz_sequence.__defaults__[0]
Out[29]: 
{1: [1],
 2: [2, 1],
 4: [4, 2, 1],
 5: [5, 16, 8, 4, 2, 1],
 8: [8, 4, 2, 1],
 16: [16, 8, 4, 2, 1],
 32: [32, 16, 8, 4, 2, 1]}

编辑:我知道它是可以优化的！秘密是在函数中有两个地方(两个返回点)，我们知道l和table没有共享任何元素。虽然以前我通过测试已经在table中的元素来避免调用table.update，但是这个版本的函数利用了我们对控制流的了解，从而节省了大量时间。

[collatz_sequence(x) for x in range(500001, 1000000)]现在在我的电脑上运行大约2秒，而@welter版本的类似表达式只有400ms。我认为这是因为这两个函数实际上并不计算相同的东西-我的版本生成整个序列，而@welter的只是找到它的长度。所以我不认为我能让我的实现降到同样的速度。

def collatz_sequence(start, table={}):  # cheeky trick: store the (mutable) table as a default argument
    """Returns the Collatz sequence for a given starting number"""
    l = []
    n = start

    while n not in l:  # break if we find ourself in a cycle
                       # (don't assume the Collatz conjecture!)
        if n in table:
            table.update({x: l[i:] for i, x in enumerate(l)})
            return l + table[n]
        elif n%2 == 0:
            l.append(n)
            n = n//2
        else:
            l.append(n)
            n = (3*n) + 1

    table.update({x: l[i:] for i, x in enumerate(l)})
    return l

PS -找出bug！

Answer 3

这是我对PE14的解决方案：

memo = {1:1}
def get_collatz(n):

if n in memo : return memo[n]

if n % 2 == 0:
    terms = get_collatz(n/2) + 1
else:
    terms = get_collatz(3*n + 1) + 1

memo[n] = terms
return terms

compare = 0
for x in xrange(1, 999999):
if x not in memo:
    ctz = get_collatz(x)
    if ctz > compare:
     compare = ctz
     culprit = x

print culprit