6

当我在 Project Euler中努力解决问题 14 时，我发现我可以使用一种叫做 memoization 的东西来加快我的进程（我让它运行了 15 分钟，但它仍然没有返回答案）。问题是，我该如何实现它？我试过了，但我得到一个键错误（返回的值无效）。这让我很烦恼，因为我很肯定我可以对此应用记忆并更快地获得它。

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))

谢谢。

4

3 回答 3

4

还有一种很好的递归方式可以做到这一点，它可能会比po​​orsod的解决方案慢，但它更类似于您的初始代码，因此您可能更容易理解。

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))
于 2013-03-18T23:48:14.267 回答
3

对于 Collat​​z 序列，记忆的重点是避免计算您已经完成的列表部分。序列的其余部分完全由当前值决定。因此，我们希望尽可能多地检查表格，并尽快退出其余的计算。

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.update已经存在的元素table，但这个版本的函数反而利用了我们对控制流的了解，节省了大量时间。

[collatz_sequence(x) for x in range(500001, 1000000)]现在在我的计算机上运行大约 2 秒，而 @welter 版本的类似表达式在 400 毫秒内运行。我认为这是因为这些函数实际上并不计算相同的东西——我的版本生成整个序列，而 @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 - 发现错误！

于 2013-03-18T23:37:56.130 回答
-1

这是我对 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
于 2015-03-05T13:33:05.707 回答