当我在尝试解决欧拉计划中的问题14时，我发现可以使用一种叫做记忆化的东西来加速我的过程（我让它运行了好15分钟，但仍未返回答案）。问题是，如何实现它？我已经尝试过了，但是遇到了keyerror错误（返回的值无效）。这让我感到困扰，因为我确信可以应用记忆化来使它更快。
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))
谢谢。
还有一种不错的递归方法来完成这个任务，虽然可能比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))
lookup = {}，改为在函数之后（并且在函数外部）定义countTerms.lookup = {}。这个变量的状态在调用之间保持不变，并且你可以在函数内部通过countTerms.lookup（或者如果你在函数内部第一行添加了lookup = countTerms.lookup，则可以直接使用lookup）访问它。 - Jaimedef countTerms(n, lookup={})，就像poorsod所做的一样。 - welter对于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.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 - 发现错误点！
collatz_sequence 函数返回一个列表 l，其中包含该序列中的所有数字。返回列表的第0个元素将是原始数字（即你作为参数传递给 collatz_sequence 的数）。因此，对于所有整数 n，都有 collatz_sequence(n)[0] == n。 - Benjamin Hodgsonmemo = {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
keyerror。 - Jason Sperske