利用 functools.lru_cache 优化递归算法
利用 functools.lru_cache 优化递归算法
递归算法可以简洁地解决许多复杂的问题，如计算阶乘、斐波那契数列等。然而，递归算法也存在一个明显的缺点，即会产生大量的重复计算，从而导致性能问题。Python 的 functools.lru_cache 装饰器可以帮助我们解决这个问题，通过缓存函数的输入和输出，避免重复计算，从而显著提高递归算法的性能。
什么是 functools.lru_cache
functools.lru_cache 是 Python 标准库 functools 中的一个装饰器，它实现了最近最少使用（Least Recently Used, LRU）缓存策略。LRU 缓存策略会保留最近使用过的函数调用结果，当再次调用相同的函数且传入相同的参数时，直接从缓存中返回结果，而不需要重新执行函数体，从而避免了重复计算。
递归算法的性能问题
我们可以使用递归算法来实现斐波那契数列的计算：
def fibonacci(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci(n - 1) + fibonacci(n - 2)# 测试
print(fibonacci(10))
在这个递归实现中，会存在大量的重复计算。例如，在计算 fibonacci(5) 时，fibonacci(3) 会被多次计算，随着 n 的增大，重复计算的次数会呈指数级增长，导致性能急剧下降。
使用 functools.lru_cache 优化递归算法
我们可以使用 functools.lru_cache 装饰器来优化上述的斐波那契数列递归算法：
import functools@functools.lru_cache(maxsize=None)
def fibonacci(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci(n - 1) + fibonacci(n - 2)# 测试
print(fibonacci(10))
在这个优化后的代码中，我们在 fibonacci 函数定义前添加了 @functools.lru_cache(maxsize=None) 装饰器。maxsize 参数指定了缓存的最大条目数，当 maxsize 为 None 时，表示缓存没有大小限制，可以缓存所有的函数调用结果。
当第一次调用 fibonacci(n) 时，函数会正常执行并将结果缓存起来。当再次调用相同的 n 时，直接从缓存中获取结果，避免了重复计算。这样，我们可以显著提高递归算法的性能。
性能对比
为了更直观地看到 functools.lru_cache 的优化效果，我们可以使用 timeit 模块来比较优化前后的性能：
import functools
import timeit# 未优化的斐波那契数列函数
def fibonacci_without_cache(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci_without_cache(n - 1) + fibonacci_without_cache(n - 2)# 优化后的斐波那契数列函数
@functools.lru_cache(maxsize=None)
def fibonacci_with_cache(n):if n == 0:return 0elif n == 1:return 1else:return fibonacci_with_cache(n - 1) + fibonacci_with_cache(n - 2)# 测试性能
n = 30
time_without_cache = timeit.timeit(lambda: fibonacci_without_cache(n), number=1) * 1000
time_with_cache = timeit.timeit(lambda: fibonacci_with_cache(n), number=1) * 1000print(f"未优化的执行时间: {time_without_cache} ms")
print(f"优化后的执行时间: {time_with_cache} ms")
运行上述代码，你会发现优化后的代码执行时间远远小于未优化的代码，尤其是当 n 较大时，性能提升更为明显。
注意事项
- 参数必须可哈希：
functools.lru_cache要求函数的参数必须是可哈希的，因为它使用参数的哈希值作为缓存的键。如果参数是不可哈希的（如列表、字典等），则不能使用该装饰器。 - 缓存大小：虽然可以将
maxsize设置为None来禁用缓存大小限制，但在实际应用中，应该根据内存情况合理设置缓存大小，避免占用过多的内存。
总结
functools.lru_cache 是一个非常实用的装饰器，它可以帮助我们优化递归算法，避免重复计算，提高程序的性能。通过简单地在递归函数前添加该装饰器，我们可以轻松地实现缓存功能，让递归算法更加高效。在实际编程中，当遇到递归算法性能问题时，不妨考虑使用 functools.lru_cache 来进行优化。