python中functools.lru_cache的具體使用

更新時間：2024年09月23日 09:28:32 作者：pumpkin84514

本文主要介紹了python中functools.lru_cache的具體使用,通過functools.lru_cache,你可以輕松優(yōu)化具有重復計算的函數(shù),大大提高代碼的執(zhí)行效率

1. 優(yōu)化算法的思想

當算法的復雜度較高時，常見的優(yōu)化策略包括：

減少重復計算：通過緩存結果避免相同輸入的重復計算。這種方法常用在遞歸和動態(tài)規(guī)劃問題中。
合理使用數(shù)據(jù)結構：根據(jù)具體問題，選擇合適的數(shù)據(jù)結構（如哈希表、堆、樹等），以提高操作效率。例如，用哈希表可以加快查找操作。
剪枝（Pruning）：在搜索或遞歸算法中，及時放棄不可能產(chǎn)生最優(yōu)解的分支，減少無效計算。
分治法（Divide and Conquer）：將大問題拆解為多個小問題，分別求解后再合并結果。經(jīng)典例子是歸并排序。
記憶化（Memoization）：將已經(jīng)計算過的結果保存下來，以便下次直接使用。這種策略在遞歸或遞推中尤為重要。
動態(tài)規(guī)劃（Dynamic Programming）：通過存儲子問題的結果，避免重復計算子問題。

2. LRU 算法與優(yōu)化思想的關系

LRU（Least Recently Used，最近最少使用） 是一種基于 緩存優(yōu)化 思想的算法，用于減少重復計算。這與上面的減少重復計算思想緊密相關。LRU 通過緩存結果來加速訪問，但同時通過淘汰最近最少使用的緩存項來保證緩存不會無限增長。

LRU 算法的核心思想：

保留最近使用的結果，淘汰不常用的結果。
如果緩存容量達到上限，優(yōu)先淘汰最久未被使用的項。

3. functools.lru_cache

Python 提供了 functools.lru_cache，這是一個基于 LRU 算法的緩存裝飾器。它會緩存函數(shù)的返回值，當再次調(diào)用該函數(shù)時，如果參數(shù)相同，直接從緩存中返回結果，避免重復計算。lru_cache 自動處理 LRU 淘汰策略，能夠顯著優(yōu)化那些需要大量重復計算的場景。

lru_cache 的參數(shù)

maxsize：緩存的最大容量，超過這個容量時，最近最少使用的數(shù)據(jù)會被淘汰。maxsize=None 表示沒有限制。
typed：若設置為 True，不同類型的相同值將被區(qū)別對待。例如 1 和 1.0 會被認為是不同的參數(shù)。

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

緩存機制：當你第一次調(diào)用某個函數(shù)時，它的計算結果會被緩存起來，儲存在一個類似字典的結構中。
緩存命中：當你再次調(diào)用該函數(shù)，且參數(shù)相同時，函數(shù)不會再次執(zhí)行，而是直接返回緩存中的結果。
緩存淘汰：如果緩存的數(shù)量達到了 maxsize，并且有新的函數(shù)調(diào)用進入緩存，則最近最少被使用的緩存項會被淘汰。

5. 如何使用 functools.lru_cache 優(yōu)化算法

接下來通過一些例子說明如何結合 functools.lru_cache 和 LRU 算法來優(yōu)化算法。

示例 1：優(yōu)化遞歸算法（斐波那契數(shù)列）

未優(yōu)化的版本（時間復雜度為 O(2^n)）

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

print(fibonacci(30))  # 計算非常慢，因為存在大量重復計算

優(yōu)化后的版本（使用 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：帶不同參數(shù)類型的緩存

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

print(double(1))   # 緩存 1 的結果
print(double(1.0)) # 緩存 1.0 的結果，區(qū)別對待

這里 typed=True 意味著 double(1) 和 double(1.0) 是不同的緩存條目，雖然它們的值相同，但類型不同。

示例 3：緩存大規(guī)模計算結果

假設我們有一個耗時的計算，比如對一個大數(shù)組的求和操作：

import time

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

arr = tuple(range(1000000))

# 第一次調(diào)用
print(expensive_sum(arr))  # 需要等待 2 秒

# 第二次調(diào)用（相同的參數(shù)）
print(expensive_sum(arr))  # 立即返回結果，無需等待

由于 arr 是相同的參數(shù)，第二次調(diào)用時直接從緩存中獲取結果。