Think Python Exercise 11.3 阿克曼函数

将 习题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)/手动狗头。