Python中的@cache巧妙用法

Python中的@cache有什麼妙用？

緩存是一種空間換時間的策略，緩存的設置可以提高計算機系統的性能。具體到代碼中，緩存的作用就是提高代碼的運行速度，但會占用額外的內存空間。

在Python的內置模塊 functools 中，提供瞭高階函數 cache() 用於實現緩存，用裝飾器的方式使用： @cache。

@cache緩存功能介紹

在cache的源碼中，對cache的描述是：Simple lightweight unbounded cache. Sometimes called “memoize”. 翻譯成中文：簡單的輕量級無限制緩存。有時也被稱為“記憶化”。

def cache(user_function, /):
    'Simple lightweight unbounded cache.  Sometimes called "memoize".'
    return lru_cache(maxsize=None)(user_function)

cache() 的代碼隻有一行，調用瞭 lru_cache() 函數，傳入一個參數 maxsize=None。lru_cache() 也是 functools 模塊中的函數，查看 lru_cache() 的源碼，maxsize 的默認值是128，表示最大緩存128個數據，如果數據超過瞭128個，則按 LRU（最久未使用）算法刪除多的數據。cache()將maxsize設置成None，則 LRU 特性被禁用且緩存數量可以無限增長，所以稱為“unbounded cache”（無限制緩存）。

lru_cache() 使用瞭 LRU（Least Recently Used）最久未使用算法，這也是函數名中有 lru 三個字母的原因。最久未使用算法的機制是，假設一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小， LRU算法選擇將最近最少使用的數據淘汰，保留那些經常被使用的數據。

cache() 是在Python3.9版本新增的，lru_cache() 是在Python3.2版本新增的， cache() 在 lru_cache() 的基礎上取消瞭緩存數量的限制，其實跟技術進步、硬件性能的大幅提升有關，cache() 和 lru_cache() 隻是同一個功能的不同版本。

lru_cache() 本質上是一個為函數提供緩存功能的裝飾器，緩存 maxsize 組傳入參數，在下次以相同參數調用函數時直接返回上一次的結果，用以節約高開銷或高I/O函數的調用時間。

@cache的應用場景

緩存的應用場景很廣泛，如靜態 Web 內容的緩存，可以直接在用戶訪問靜態網頁的函數上加 @cache 裝飾器。

一些遞歸的代碼中，存在反復傳入同一個參數執行函數代碼的情況，使用緩存可以避免重復計算，降低代碼的時間復雜度。

接下來，我用斐波那契數列作為例子來說明 @cache 的作用，如果前面的內容你看完瞭還一知半解，相信看完例子你會茅塞頓開。

斐波那契數列是指這樣一個數列：1、1、2、3、5、8、13、21、34、… ，從第三個數開始，每個數都是前兩個數之和。斐波那契數列的代碼實現不難，大部分程序員入門時都做過，在Python中，實現的代碼非常簡潔。如下：

def feibo(n):
    # 第0個數和第1個數為1
    a, b = 1, 1
    for _ in range(n):
        # 將b賦值給a,將a+b賦值給b,循環n次
        a, b = b, a+b
    return a

當然，斐波那契數列的代碼實現方式有很多種（至少五六種），本文為瞭說明 @cache 的應用場景，用遞歸的方式來寫斐波那契數列的代碼。如下：

def feibo_recur(n):
    if n < 0:
        return "n小於0無意義"
    # n為0或1時返回1（前兩個數為1）
    if n == 0 or n == 1:
        return 1
    # 根據斐波那契數列的定義，其他情況遞歸返回前兩個數之和
    return feibo_recur(n-1) + feibo_recur(n-2)

遞歸代碼執行時會一直遞歸到feibo_recur(1)和feibo_recur(0)，如下圖所示（以求第6個數為例）。

求F(5)時要先求F(4)和F(3)，求F(4)時要先求F(3)和F(2)，… 以此類推，遞歸的過程與二叉樹深度優先遍歷的過程類似。已知高度為 k 的二叉樹最多可以有 2k-1 個節點，根據上面遞歸調用的圖示，二叉樹的高度是 n，節點最多為 2n-1， 也就是遞歸調用函數的次數最多為 2n-1 次，所以遞歸的時間復雜度為 O(2^n) 。

時間復雜度為O(2^n)時，執行時間隨 n 的增大變化非常誇張，下面實際測試一下。

import time
for i in [10, 20, 30, 40]:
    start = time.time()
    print(f'第{i}個斐波那契數:', feibo_recur(i))
    end = time.time()
    print(f'n={i} Cost Time: ', end - start)

Output:

第10個斐波那契數: 89
n=10 Cost Time:  0.0
第20個斐波那契數: 10946
n=20 Cost Time:  0.0015988349914550781
第30個斐波那契數: 1346269
n=30 Cost Time:  0.17051291465759277
第40個斐波那契數: 165580141
n=40 Cost Time:  20.90010976791382

從運行時間可以看出，在 n 很小時，運行很快，隨著 n 的增大，運行時間極速上升，尤其 n 逐步增加到30和40時，運行時間變化得特別明顯。為瞭更清晰地看出時間變化規律，再進一步進行測試。

for i in [41, 42, 43]:
    start = time.time()
    print(f'第{i}個斐波那契數:', feibo_recur(i))
    end = time.time()
    print(f'n={i} Cost Time: ', end - start)

Output:

第41個斐波那契數: 267914296
n=41 Cost Time:  33.77224683761597
第42個斐波那契數: 433494437
n=42 Cost Time:  55.86398696899414
第43個斐波那契數: 701408733
n=43 Cost Time:  92.55108690261841

從上面的變化可以看到，時間是指數級增長的（大約按1.65的指數增長），這跟時間復雜度為 O(2^n) 相符。按照這個時間復雜度，假如要計算第50個斐波那契數列，差不多要等一個小時，非常不合理，也說明遞歸的實現方式運算量過大，存在明顯的不足。如何解決這種不足，降低運算量呢？接下來看如何進行優化。

根據前面的分析，遞歸代碼運算量大，是因為遞歸執行時會不斷的計算 feibo_recur(n-1) 和 feibo_recur(n-2)，如示例圖中，要得到 feibo_recur(5) ，feibo_recur(1) 調用瞭5次。隨著 n 的增大，調用次數呈指數增加，造成瞭海量不必要的重復，浪費瞭大量時間。

假如有一個地方將每個 n 的執行結果記錄下來，當作“備忘錄”，下次函數再接收到這個相同的參數時，直接從備忘錄中獲取結果，而不用去執行遞歸的過程，就可以避免這些重復調用。在 Python 中，可以創建一個字典或列表來當作“備忘錄”使用。

temp = {}  # 創建一個空字典，用來記錄第i個斐波那契數列的值
def feibo_recur_temp(n):
    if n < 0:
        return "n小於0無意義"
    # n為0或1時返回1（前兩個數為1）
    if n == 0 or n == 1:
        return 1
    if n in temp:  # 如果temp字典中有n,則直接返回值,不調用遞歸代碼
        return temp[n]
    else:
        # 如果字典中還沒有第n個斐波那契數，則遞歸計算並保存到字典中
        temp[n] = feibo_recur_temp(n-1) + feibo_recur_temp(n-2)
        return temp[n]

上面的代碼中，創建瞭一個空字典用於存放每個 n 的執行結果。每次調用函數，都先查看字典中是否有記錄，如果有記錄就直接返回，沒有記錄就遞歸執行並將結果記錄到字典中，再從字典中返回結果。這裡的遞歸其實都隻執行瞭一次計算，並沒有真正的遞歸，如第一次傳入 n 等於 5，執行 feibo_recur_temp(5)，會遞歸執行 n 等於 4, 3, 2, 1, 0 的情況，每個 n 計算過一次後 temp 中都有瞭記錄，後面都是直接到 temp 中取數相加。每個 n 都是從temp中取 n-1 和 n-2 的值來相加，執行一次計算，所以時間復雜度是 O(n) 。

下面看一下代碼的運行時間。

for i in [10, 20, 30, 40, 41, 42, 43]:
    start = time.time()
    print(f'第{i}個斐波那契數:', feibo_recur_temp(i))
    end = time.time()
    print(f'n={i} Cost Time: ', end - start)
print(temp)

Output:

第10個斐波那契數: 89
n=10 Cost Time:  0.0
第20個斐波那契數: 10946
n=20 Cost Time:  0.0
第30個斐波那契數: 1346269
n=30 Cost Time:  0.0
第40個斐波那契數: 165580141
n=40 Cost Time:  0.0
第41個斐波那契數: 267914296
n=41 Cost Time:  0.0
第42個斐波那契數: 433494437
n=42 Cost Time:  0.0
第43個斐波那契數: 701408733
n=43 Cost Time:  0.0
{2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21, 8: 34, 9: 55, 10: 89, 11: 144, 12: 233, 13: 377, 14: 610, 15: 987, 16: 1597, 17: 2584, 18: 4181, 19: 6765, 20: 10946, 21: 17711, 22: 28657, 23: 46368, 24: 75025, 25: 121393, 26: 196418, 27: 317811, 28: 514229, 29: 832040, 30: 1346269, 31: 2178309, 32: 3524578, 33: 5702887, 34: 9227465, 35: 14930352, 36: 24157817, 37: 39088169, 38: 63245986, 39: 102334155, 40: 165580141, 41: 267914296, 42: 433494437, 43: 701408733}

可以看到，代碼運行時間全都降到小數點後很多位瞭(時間太小，隻顯示瞭 0.0 )。不過，temp 字典裡記錄瞭每個數對應的斐波那契數，這需要占用額外的內存空間，用空間換時間。

上面的代碼也可以用列表來當“備忘錄”，代碼如下。

temp = [1, 1]
def feibo_recur_temp(n):
    if n < 0:
        return "n小於0無意義"
    if n == 0 or n == 1:
        return 1
    if n < len(temp):
        return temp[n]
    else:
        # 第一次執行時，將結果保存到列表中，後續直接從列表中取
        temp.append(feibo_recur_temp(n-1) + feibo_recur_temp(n-2))
        return temp[n]

現在，已經剖析瞭遞歸代碼重復執行帶來的時間復雜度問題，也給出瞭優化時間復雜度的方法，讓我們將註意力轉回到本文介紹的 @cache 裝飾器。@cache 裝飾器的作用是將函數的執行結果緩存，在下次以相同參數調用函數時直接返回上一次的結果，與上面的優化方式完全一致。

所以，隻需要在遞歸函數上加 @cache 裝飾器，遞歸的重復執行就可以解決，時間復雜度就能從 O(2^n) 降為 O(n) 。代碼如下：

from functools import cache
@cache
def feibo_recur(n):
    if n < 0:
        return "n小於0無意義"
    if n == 0 or n == 1:
        return 1
    return feibo_recur(n-1) + feibo_recur(n-2)

代碼比自己實現更加簡潔優雅，並且每次使用時直接加上 @cache 裝飾器就行，專註處理業務邏輯。下面看一下實際的運行時間。

for i in [10, 20, 30, 40, 41, 42, 43]:
    start = time.time()
    print(f'第{i}個斐波那契數:', feibo_recur(i))
    end = time.time()
    print(f'n={i} Cost Time: ', end - start)

Output:

第10個斐波那契數: 89
n=10 Cost Time:  0.0
第20個斐波那契數: 10946
n=20 Cost Time:  0.0
第30個斐波那契數: 1346269
n=30 Cost Time:  0.0
第40個斐波那契數: 165580141
n=40 Cost Time:  0.0
第41個斐波那契數: 267914296
n=41 Cost Time:  0.0
第42個斐波那契數: 433494437
n=42 Cost Time:  0.0
第43個斐波那契數: 701408733
n=43 Cost Time:  0.0

運行時間全都降到小數點後很多位瞭(隻顯示瞭 0.0 )，完美解決問題，非常精妙。以後遇到相似的情況，可以直接使用 @cache ，實現“記憶化”的緩存功能。

參考文檔：
[1] Python文檔標準庫functools：https://docs.python.org/zh-cn/3.11/library/functools.html#functools.cache

補充：Python @cache裝飾器

@cache和@lru_cache(maxsize=None)可以用來寄存函數對已處理參數的結果，以便遇到相同參數可以直接給出答案。前者不限制存儲的數量，後者通過maxsize限制存儲的最大數量。

例：

@lru_cache(maxsize=None) # 等價於@cache
def test(a,b):
    print('開始計算a+b的值...')
    return a + b

可以用來做某些遞歸、動態規劃。比如斐波那契數列的各項值從小到大輸出。其實類似用數組保存前項的結果，都需要額外的空間。不過用裝飾器可以省略額外空間代碼，減少瞭出錯的風險。

到此這篇關於Python中的@cache巧妙用法的文章就介紹到這瞭,更多相關Python中的@cache內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

• python自帶緩存lru_cache用法及擴展的使用
• Python的functools模塊使用及說明
• Python 中的函數裝飾器和閉包詳解
• 詳解pandas apply 並行處理的幾種方法
• python反反爬蟲技術限制連續請求時間處理