python中functools.lru_cache的具体使用_Python

1. 优化算法的思想

当算法的复杂度较高时，常见的优化策略包括：

减少重复计算：通过缓存结果避免相同输入的重复计算。这种方法常用在递归和动态规划问题中。
合理使用数据结构：根据具体问题，选择合适的数据结构（如哈希表、堆、树等），以提高操作效率。例如，用哈希表可以加快查找操作。
剪枝（pruning）：在搜索或递归算法中，及时放弃不可能产生最优解的分支，减少无效计算。
分治法（divide and conquer）：将大问题拆解为多个小问题，分别求解后再合并结果。经典例子是归并排序。
记忆化（memoization）：将已经计算过的结果保存下来，以便下次直接使用。这种策略在递归或递推中尤为重要。
动态规划（dynamic programming）：通过存储子问题的结果，避免重复计算子问题。

2. lru 算法与优化思想的关系

lru（least recently used，最近最少使用） 是一种基于 缓存优化 思想的算法，用于减少重复计算。这与上面的减少重复计算思想紧密相关。lru 通过缓存结果来加速访问，但同时通过淘汰最近最少使用的缓存项来保证缓存不会无限增长。

lru 算法的核心思想：

保留最近使用的结果，淘汰不常用的结果。
如果缓存容量达到上限，优先淘汰最久未被使用的项。

3. functools.lru_cache

python 提供了 functools.lru_cache，这是一个基于 lru 算法的缓存装饰器。它会缓存函数的返回值，当再次调用该函数时，如果参数相同，直接从缓存中返回结果，避免重复计算。lru_cache 自动处理 lru 淘汰策略，能够显著优化那些需要大量重复计算的场景。

lru_cache 的参数

maxsize：缓存的最大容量，超过这个容量时，最近最少使用的数据会被淘汰。maxsize=none 表示没有限制。
typed：若设置为 true，不同类型的相同值将被区别对待。例如 1 和 1.0 会被认为是不同的参数。

4. 原理详解：functools.lru_cache 是如何工作的？

缓存机制：当你第一次调用某个函数时，它的计算结果会被缓存起来，储存在一个类似字典的结构中。
缓存命中：当你再次调用该函数，且参数相同时，函数不会再次执行，而是直接返回缓存中的结果。
缓存淘汰：如果缓存的数量达到了 maxsize，并且有新的函数调用进入缓存，则最近最少被使用的缓存项会被淘汰。

5. 如何使用 functools.lru_cache 优化算法

接下来通过一些例子说明如何结合 functools.lru_cache 和 lru 算法来优化算法。

示例 1：优化递归算法（斐波那契数列）

未优化的版本（时间复杂度为 o(2^n)）

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(30))  # 计算非常慢，因为存在大量重复计算

优化后的版本（使用 functools.lru_cache）

from functools import lru_cache

@lru_cache(maxsize=128)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(30))  # 速度快得多，因为避免了重复计算

maxsize=128：表示最多缓存 128 个结果，超出部分将按 lru 策略淘汰。

示例 2：带不同参数类型的缓存

@lru_cache(maxsize=100, typed=true)
def double(x):
    return x * 2

print(double(1))   # 缓存 1 的结果
print(double(1.0)) # 缓存 1.0 的结果，区别对待

这里 typed=true 意味着 double(1) 和 double(1.0) 是不同的缓存条目，虽然它们的值相同，但类型不同。

示例 3：缓存大规模计算结果

假设我们有一个耗时的计算，比如对一个大数组的求和操作：

import time

@lru_cache(maxsize=32)
def expensive_sum(arr):
    time.sleep(2)  # 模拟耗时操作
    return sum(arr)

arr = tuple(range(1000000))

# 第一次调用
print(expensive_sum(arr))  # 需要等待 2 秒

# 第二次调用（相同的参数）
print(expensive_sum(arr))  # 立即返回结果，无需等待

由于 arr 是相同的参数，第二次调用时直接从缓存中获取结果。