Python 小技巧 052：使用记忆化优化递归函数

zltzlt

使用记忆化优化递归函数

Memoization（记忆化）是一种利用缓存来加速函数调用的技术手段，将消耗较大的调用结果存储起来，当再次遇到相同调用时就从缓存读取结果，而无需重新计算。这种方法叫做 LRU（Least Recently Used）缓存算法。

例如，我们编写一个常规的计算第 n 项斐波那契数列的值的递归函数：

1. def fib(n):
   
2.     if n == 1 or n == 2:
   
3.         # 斐波那契数列的第 1 和第 2 项是 1
   
4.         return 1
   
5.     return fib(n - 1) + fib(n - 2)

复制代码

这个函数看上去没毛病，而且代码很整洁。但是，它的效率如何呢？我们用 1 ~ 100 的数测试一下：

1. def fib(n):
   
2.     if n == 1 or n == 2:
   
3.         # 斐波那契数列的第 1 和第 2 项是 1
   
4.         return 1
   
5.     return fib(n - 1) + fib(n - 2)
   
6. 
   
7. 
   
8. for i in range(1, 101):
   
9.     print(i, ":", fib(i))

复制代码

执行效果：



太令人失望了，我们的函数好慢。但为什么会这么慢呢？

要搞懂这个，我们先从小的数据开始。让我们看看调用 fib(5) 会发生什么：

1.   fib(5)
   
2. = fib(4) + fib(3)
   
3. = fib(3) + fib(2) + fib(2) + fib(1)
   
4. = fib(2) + fib(1) + fib(2) + fib(2) + fib(1)
   
5. = 1 + 1 + 1 + 1 + 1
   
6. = 5

复制代码

我们的递归函数写的很马虎，可怜的 Python 就会一直进行无必要的重复，从而浪费时间。要解决这种问题，我们就需要使用记忆化，Memoization。

记忆化背后的想法很简单。存储返回值，这样再调用就不会重复执行，而直接返回存储的值。

Python 中有几种方式实现记忆化。先来看一种：

1. cache = {}    # 定义一个字典，用于存储返回值
   
2. 
   
3. 
   
4. def fib(n):
   
5.     if n in cache:
   
6.         return cache[n]
   
7.     # 我们需要将返回值存储起来
   
8.     if n == 1 or n == 2:
   
9.         # 斐波那契数列的第 1 和第 2 项是 1
   
10.         value = 1
    
11.     elif n > 2:
    
12.         value = fib(n - 1) + fib(n - 2)
    
13.     cache[n] = value
    
14.     return value

复制代码

执行效果：



不错，速度比之前的快多了。

让我们再来看一种更简洁的解决方案，使用 functools 模块的 lru_cache() 装饰器：

1. from functools import lru_cache
   
2. 
   
3. 
   
4. # maxsize 是指定最大缓存多少个调用，默认为 128，如果设置为 None 则关闭缓存功能
   
5. # typed 是指定参数值相同但类型不同时是否单独缓存，默认值为 False
   
6. @lru_cache(maxsize=100, typed=False)
   
7. def fib(n):
   
8.     if n == 1 or n == 2:
   
9.         return 1
   
10.     elif n > 2:
    
11.         return fib(n - 1) + fib(n - 2)
    
12. 
    
13. 
    
14. for i in range(1, 101):
    
15.     print(i, ":", fib(i))

复制代码

执行效果：



速度也是相当快。

_2_

终于使递归成为了一种可行的代码编辑方式