Python 小技巧 052：使用记忆化优化递归函数
本帖最后由 zltzlt 于 2020-1-17 19:26 编辑使用记忆化优化递归函数
Memoization（记忆化）是一种利用缓存来加速函数调用的技术手段，将消耗较大的调用结果存储起来，当再次遇到相同调用时就从缓存读取结果，而无需重新计算。这种方法叫做 LRU（Least Recently Used）缓存算法。
例如，我们编写一个常规的计算第 n 项斐波那契数列的值的递归函数：
def fib(n):
if n == 1 or n == 2:
# 斐波那契数列的第 1 和第 2 项是 1
return 1
return fib(n - 1) + fib(n - 2)
这个函数看上去没毛病，而且代码很整洁。但是，它的效率如何呢？我们用 1 ~ 100 的数测试一下：
def fib(n):
if n == 1 or n == 2:
# 斐波那契数列的第 1 和第 2 项是 1
return 1
return fib(n - 1) + fib(n - 2)
for i in range(1, 101):
print(i, ":", fib(i))
执行效果：
太令人失望了，我们的函数好慢。但为什么会这么慢呢？
要搞懂这个，我们先从小的数据开始。让我们看看调用 fib(5) 会发生什么：
fib(5)
= fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)
= fib(2) + fib(1) + fib(2) + fib(2) + fib(1)
= 1 + 1 + 1 + 1 + 1
= 5
我们的递归函数写的很马虎，可怜的 Python 就会一直进行无必要的重复，从而浪费时间。要解决这种问题，我们就需要使用记忆化，Memoization。
记忆化背后的想法很简单。存储返回值，这样再调用就不会重复执行，而直接返回存储的值。
Python 中有几种方式实现记忆化。先来看一种：
cache = {} # 定义一个字典，用于存储返回值
def fib(n):
if n in cache:
return cache
# 我们需要将返回值存储起来
if n == 1 or n == 2:
# 斐波那契数列的第 1 和第 2 项是 1
value = 1
elif n > 2:
value = fib(n - 1) + fib(n - 2)
cache = value
return value
执行效果：
不错，速度比之前的快多了。
让我们再来看一种更简洁的解决方案，使用 functools 模块的 lru_cache() 装饰器：
from functools import lru_cache
# maxsize 是指定最大缓存多少个调用，默认为 128，如果设置为 None 则关闭缓存功能
# typed 是指定参数值相同但类型不同时是否单独缓存，默认值为 False
@lru_cache(maxsize=100, typed=False)
def fib(n):
if n == 1 or n == 2:
return 1
elif n > 2:
return fib(n - 1) + fib(n - 2)
for i in range(1, 101):
print(i, ":", fib(i))
执行效果：
速度也是相当快。 终于使递归成为了一种可行的代码编辑方式
页:
[1]