跳到主要內容區塊

ntuccepaper2019

專題報導

Python小技巧:函式結果自動快取
  • 卷期:v0062
  • 出版日期:2022-09-20

作者:周秉誼 / Tomofun 資深技術經理


記憶化是在記憶體使用和計算時間取得平衡的方式,將經常重複使用的計算結果存放在存取速度較快的記憶體中,加速取得結果。針對這種情況,Python標準函式庫中的functools函式庫有提供了lru_cache()函式,可以透過Decorator方便地使用記憶機制。

 

前言

Python是非常容易學習的程式語言,不只可以運用在日常工作的自動化,也可以作為網路服務的後端(Backend)程式,也有豐富的標準函式庫(Python Standard Library)和套件(Package),使得Python成為多種使用情境下都可以使用的程式語言。

函式(Function)及函式呼叫(Function call)是在使用Python時非常重要且常見的程式設計方式。使用函式可以把複雜的程式流程和邏輯從主程式中抽離,簡化主程式的流程,又可以讓程式碼更方便的重複使用(Reuse)。函式在使用上除了對資料或環境進行操作,另一個方式是使用函式的回傳值(Return Value),這類函式的程式碼會依照不同的輸入參數(Argument)計算出回傳值供呼叫者(Caller)使用。然而有些函式十分複雜,在計算時要花費非常久的時間,而相同輸入參數的結果又可能會被重複使用到,每次都重新計算將會花費許多額外的計算資源。在這種情境之下,記憶化(Memoization)的概念就可以派上用場。

 

函式快取機制

記憶化和快取(Cache)的概念很像,都是在記憶體使用和計算時間取得平衡的方式,將經常重複使用的計算結果存放在存取速度較快的記憶體中,加速取得結果的方式。對於較複雜、計算時間較長的函式,程式開發人員也可以在程式當中自行安排記憶方式,但相對來說程式流程就會變得較複雜。針對這種情況,Python標準函式庫中的functools函式庫有提供了lru_cache()函式,可以方便使用記憶機制。

 

lru_cache()函式設定

functools函式庫中的lru_cache()函式,讓程式開發人員可以透過Function Decorator的方式,只加一行就能依參數的不同將函式結果記憶化,達到函式快取(Function cache)的功能。因為在Python有一級函式(First-class Function)的性質,函式是一級物件(First-class object),可以跟其他資資一起當成參數傳進另一個函式,對輸入和輸出進行前後處理(pre/post processing)。Function Decorator就是這一種可以對另一個函式輸入輸出行為進行改變的函式。Python更進一步對於Function Decorator提供了語法糖衣(Syntax Sugar),讓程式開發人員用更簡化的語法使用Decorator的功能。只要在要加Decorator的函式前,加上@符號(commercial at)及Decorator的名稱,之後在呼叫原本的函式時,就會自動用Function Decorator的方式對該函式的輸入輸出進行前後處理。所以要使用lru_cache()函式進行函式快取,只要在要快取的函式前加上一行@lru_cache的Decorator語法,就會完成自動快取了。

lru_cache()函式在使用時,可以設定一個maxsize的參數,指定快取空間的數量,當快取使用超過這個數量時,就會把最久沒有使用到的快取刪除,保持快取空間的數量在設定之下。如果沒有設定maxsize參數,預設為128,也可以將maxsize設為None,就不會有快取空間的數量限制。程式開發人員可以依據不同情境,設定比較合理的maxsize大小。

 

以lru_cache()函式加速計算

費氏數列(Fibonacci number)的計算是一個可以簡單用lru_cache()函式和Decorator方式加速非常多的例子。以基本的遞迴(Recusion)方式計算費氏數列,當n成長到30以上,就會因為大量相同的輸入參數重複呼叫,使計算所花費的時間快速增加。如果使用了lru_cache()函式對已計算出來的結果進行快取,就可以節省非常多計算花費的時間。

更為複雜的多個參數的遞迴計算,如果適當地設計函式和參數的呼叫,也是可以用lru_cache()函式就能有十分顯著的加速。如Leetcode平台上題號329的Longest Increasing Path in a Matrix問題,要在一給定的二維陣列中找到最長的遞增路徑,也可以用深度搜尋(DFS)演算法,配合lru_cache()函式進行快取來解決。

 

20220920_006207_01

 

圖1.以lru_cache()函式快取加速費氏數列計算

 

 

無快取

有快取

n=10

0.043

0.042

n=40

12.674

0.042

n=80

N/A

0.054

圖2.有無lru_cache()函式快取計算費氏數列花費時間

 

20220920_006207_02

 

圖3.以lru_cache()函式和DFS進行最長的遞增路徑計算

 

結語

使用Python標準函式庫中functools函式庫提供的lru_cache()函式,配合Function Decorator語法,就可以方便使用記憶機制將函式的計算結果快取起來,大幅加速計算所需的時間。一些原本需要改寫為動態規劃(Dynamic Programming)的程式,也可以在原本遞迴計x算的函式簡單加上Decorator就能加速。因此函式快取是在進行Python程式開發時很重要的小技巧。