05-用结果缓存来救场

1.1.3　用结果缓存来救场

结果缓存（memoization）是一种缓存技术，即在每次计算任务完成后就把结果保存起来，这样在下次需要时即可直接检索出结果，而不需要一而再再而三地重复计算（如图1-4所示）^[1]。

下面创建一个新版的斐波那契函数，利用Python的字典对象作为结果缓存，如代码清单1-5所示。

代码清单1-5　fib3.py

from typing import Dict
memo: Dict[int, int] = {0: 0, 1: 1}  # our base cases
def fib3(n: int) -> int:
    if n not in memo: 
        memo[n] = fib3(n - 1) + fib3(n - 2)  # memoization
    return memo[n]

现在就可以放心地调用 fib3(50) 了，如代码清单1-6所示。

代码清单1-6　fib3.py（续）

if __name__ == "__main__":
    print(fib3(5))
    print(fib3(50))

现在一次调用 fib3(20) 只会产生39次 fib3() 调用，而不会像调用 fib2(20) 那样产生21891次 fib2() 调用。 memo 中预填了之前的基线条件0和1，并加了一条 if 语句大幅降低了 fib3() 的计算复杂度。