Python中的@cache有什么妙用？

緩存是一種空間換時間的策略，緩存的設(shè)置可以提高計(jì)算機(jī)系統(tǒng)的性能。具體到代碼中，緩存的作用就是提高代碼的運(yùn)行速度，但會占用額外的內(nèi)存空間。

在Python的內(nèi)置模塊 functools 中，提供了高階函數(shù) cache() 用于實(shí)現(xiàn)緩存，用裝飾器的方式使用： @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() 的代碼只有一行，調(diào)用了 lru_cache() 函數(shù)，傳入一個參數(shù) maxsize=None。lru_cache() 也是 functools 模塊中的函數(shù)，查看 lru_cache() 的源碼，maxsize 的默認(rèn)值是128，表示最大緩存128個數(shù)據(jù)，如果數(shù)據(jù)超過了128個，則按 LRU（最久未使用）算法刪除多的數(shù)據(jù)。cache()將maxsize設(shè)置成None，則 LRU 特性被禁用且緩存數(shù)量可以無限增長，所以稱為“unbounded cache”（無限制緩存）。

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

cache() 是在Python3.9版本新增的，lru_cache() 是在Python3.2版本新增的， cache() 在 lru_cache() 的基礎(chǔ)上取消了緩存數(shù)量的限制，其實(shí)跟技術(shù)進(jìn)步、硬件性能的大幅提升有關(guān)，cache() 和 lru_cache() 只是同一個功能的不同版本。

lru_cache() 本質(zhì)上是一個為函數(shù)提供緩存功能的裝飾器，緩存 maxsize 組傳入?yún)?shù)，在下次以相同參數(shù)調(diào)用函數(shù)時直接返回上一次的結(jié)果，用以節(jié)約高開銷或高I/O函數(shù)的調(diào)用時間。

@cache的應(yīng)用場景

緩存的應(yīng)用場景很廣泛，如靜態(tài) Web 內(nèi)容的緩存，可以直接在用戶訪問靜態(tài)網(wǎng)頁的函數(shù)上加 @cache 裝飾器。

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

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

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

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

當(dāng)然，斐波那契數(shù)列的代碼實(shí)現(xiàn)方式有很多種（至少五六種），本文為了說明 @cache 的應(yīng)用場景，用遞歸的方式來寫斐波那契數(shù)列的代碼。如下：

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

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

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

時間復(fù)雜度為O(2^n)時，執(zhí)行時間隨 n 的增大變化非?？鋸?，下面實(shí)際測試一下。

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

Output:

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

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

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

Output:

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

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

根據(jù)前面的分析，遞歸代碼運(yùn)算量大，是因?yàn)檫f歸執(zhí)行時會不斷的計(jì)算 feibo_recur(n-1) 和 feibo_recur(n-2)，如示例圖中，要得到 feibo_recur(5) ，feibo_recur(1) 調(diào)用了5次。隨著 n 的增大，調(diào)用次數(shù)呈指數(shù)增加，造成了海量不必要的重復(fù)，浪費(fèi)了大量時間。

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

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

上面的代碼中，創(chuàng)建了一個空字典用于存放每個 n 的執(zhí)行結(jié)果。每次調(diào)用函數(shù)，都先查看字典中是否有記錄，如果有記錄就直接返回，沒有記錄就遞歸執(zhí)行并將結(jié)果記錄到字典中，再從字典中返回結(jié)果。這里的遞歸其實(shí)都只執(zhí)行了一次計(jì)算，并沒有真正的遞歸，如第一次傳入 n 等于 5，執(zhí)行 feibo_recur_temp(5)，會遞歸執(zhí)行 n 等于 4, 3, 2, 1, 0 的情況，每個 n 計(jì)算過一次后 temp 中都有了記錄，后面都是直接到 temp 中取數(shù)相加。每個 n 都是從temp中取 n-1 和 n-2 的值來相加，執(zhí)行一次計(jì)算，所以時間復(fù)雜度是 O(n) 。

下面看一下代碼的運(yùn)行時間。

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

Output:

第10個斐波那契數(shù): 89
n=10 Cost Time:  0.0
第20個斐波那契數(shù): 10946
n=20 Cost Time:  0.0
第30個斐波那契數(shù): 1346269
n=30 Cost Time:  0.0
第40個斐波那契數(shù): 165580141
n=40 Cost Time:  0.0
第41個斐波那契數(shù): 267914296
n=41 Cost Time:  0.0
第42個斐波那契數(shù): 433494437
n=42 Cost Time:  0.0
第43個斐波那契數(shù): 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}

可以看到，代碼運(yùn)行時間全都降到小數(shù)點(diǎn)后很多位了(時間太小，只顯示了 0.0 )。不過，temp 字典里記錄了每個數(shù)對應(yīng)的斐波那契數(shù)，這需要占用額外的內(nèi)存空間，用空間換時間。

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

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:
        # 第一次執(zhí)行時，將結(jié)果保存到列表中，后續(xù)直接從列表中取
        temp.append(feibo_recur_temp(n-1) + feibo_recur_temp(n-2))
        return temp[n]

現(xiàn)在，已經(jīng)剖析了遞歸代碼重復(fù)執(zhí)行帶來的時間復(fù)雜度問題，也給出了優(yōu)化時間復(fù)雜度的方法，讓我們將注意力轉(zhuǎn)回到本文介紹的 @cache 裝飾器。@cache 裝飾器的作用是將函數(shù)的執(zhí)行結(jié)果緩存，在下次以相同參數(shù)調(diào)用函數(shù)時直接返回上一次的結(jié)果，與上面的優(yōu)化方式完全一致。

所以，只需要在遞歸函數(shù)上加 @cache 裝飾器，遞歸的重復(fù)執(zhí)行就可以解決，時間復(fù)雜度就能從 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)

代碼比自己實(shí)現(xiàn)更加簡潔優(yōu)雅，并且每次使用時直接加上 @cache 裝飾器就行，專注處理業(yè)務(wù)邏輯。下面看一下實(shí)際的運(yùn)行時間。

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

Output:

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

運(yùn)行時間全都降到小數(shù)點(diǎn)后很多位了(只顯示了 0.0 )，完美解決問題，非常精妙。以后遇到相似的情況，可以直接使用 @cache ，實(shí)現(xiàn)“記憶化”的緩存功能。

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

補(bǔ)充：Python @cache裝飾器

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

例：

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

可以用來做某些遞歸、動態(tài)規(guī)劃。比如斐波那契數(shù)列的各項(xiàng)值從小到大輸出。其實(shí)類似用數(shù)組保存前項(xiàng)的結(jié)果，都需要額外的空間。不過用裝飾器可以省略額外空間代碼，減少了出錯的風(fēng)險。

到此這篇關(guān)于Python中的@cache巧妙用法的文章就介紹到這了,更多相關(guān)Python中的@cache內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論