将 习题6.2 中的 Ackermann 函数备忘录化(memoize), 看看备忘录化(memoization)是否可以支持解决更大的参数。没有提示!
储存之前计算过的值以便今后使用，这个操作就称为备忘录化。
做这道题首先要理解书上关于斐波那契数列的例子。
计算斐波那契数列的代码：
1
2
3
4
5
6
7
| def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
|
备忘录化后的代码：
1
2
3
4
5
6
7
8
9
| known = {0:0, 1:1}
def fibonacci(n):
if n in known:
return known[n]
res = fibonacci(n-1) + fibonacci(n-2)
known[n] = res
return res
|
按照同样的思路，我们可以把计算的ack函数的值储存到字典里，后面再计算时先看之前是不是曾计算过，如果计算过，直接调用已有结果即可。
原ack函数代码：
1
2
3
4
5
6
7
8
| def ackermann(m,n): #来自6.2
if m == 0:
return n+1
if n == 0:
return ackermann(m-1,1)
return ackermann(m-1, ackermann(m,n-1))
print(ackermann(3,4))
|
备忘录化后的ack代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| known = {}
def ackermann(m,n):
if (m,n) in known:
return known[m,n]
if m == 0:
res = n+1
known[m,n] = res
return res
if n == 0:
res = ackermann(m-1,1)
known[m,n] = res
return res
res = ackermann(m-1, ackermann(m,n-1))
known[m,n] = res
return res
print(ackermann(3,4))
|
可以注意到我用了元组作为字典的键，元组是下一章学的，这里用是因为我觉得没有比元组更合适的了。
在 jupyter lab 里可以通过在代码第一行写%%time查看代码运行时间，经比较，可以发现备忘录化后的计算速度快了很多很多：
1
2
3
4
5
6
7
8
9
| %%time
def ackermann(m,n):
if m == 0:
return n+1
if n == 0:
return ackermann(m-1,1)
return ackermann(m-1, ackermann(m,n-1))
print(ackermann(3,6))
|
509
CPU times: user 55 ms, sys: 4.78 ms, total: 59.8 ms
Wall time: 66.4 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| %%time
known = {}
def ackermann(m,n):
if (m,n) in known:
return known[m,n]
if m == 0:
res = n+1
known[m,n] = res
return res
if n == 0:
res = ackermann(m-1,1)
known[m,n] = res
return res
res = ackermann(m-1, ackermann(m,n-1))
known[m,n] = res
return res
print(ackermann(3,6))
|
509
CPU times: user 3.09 ms, sys: 1.51 ms, total: 4.59 ms
Wall time: 5.48 ms
再大的数我就不试了。你感兴趣可以试试ackermann(4,3)/手动狗头。