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

zltzlt

使用记忆化优化递归函数

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[n]
    # 我们需要将返回值存储起来
    if n == 1 or n == 2:
        # 斐波那契数列的第 1 和第 2 项是 1
        value = 1
    elif n > 2:
        value = fib(n - 1) + fib(n - 2)
    cache[n] = 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))

执行效果：



速度也是相当快。

_2_

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