lru_cache
LRU算法原理
LRU (Least Recently Used，最近最少使用) 算法是一種緩存淘汰策略。其根據(jù)數(shù)據(jù)的歷史訪問(wèn)記錄來(lái)進(jìn)行淘汰拦惋，核心思想是，“如果數(shù)據(jù)最近被訪問(wèn)過(guò)安寺，那么將來(lái)被訪問(wèn)的幾率也更高”厕妖。該算法最初為操作系統(tǒng)中一種內(nèi)存管理的頁(yè)面置換算法，主要用于找出內(nèi)存中較久時(shí)間沒(méi)有使用的內(nèi)存塊挑庶，將其移出內(nèi)存從而為新數(shù)據(jù)提供空間言秸。
python中的LRU
Python 的 3.2 版本中，引入了一個(gè)非常優(yōu)雅的緩存機(jī)制迎捺，即 functool 模塊中的 lru_cache 裝飾器举畸，可以直接將函數(shù)或類方法的結(jié)果緩存住，后續(xù)調(diào)用則直接返回緩存的結(jié)果破加。lru_cache 原型如下：
@functools.lru_cache(maxsize=None, typed=False)
使用 functools 模塊的 lur_cache 裝飾器俱恶，可以緩存最多 maxsize 個(gè)此函數(shù)的調(diào)用結(jié)果，從而提高程序執(zhí)行的效率，特別適合于耗時(shí)的函數(shù)合是。參數(shù) maxsize 為最多緩存的次數(shù)了罪，如果為 None，則無(wú)限制聪全，設(shè)置為 2 的冪 時(shí)泊藕，性能最佳；如果 typed=True（注意难礼，在 functools32 中沒(méi)有此參數(shù)）娃圆，則不同參數(shù)類型的調(diào)用將分別緩存，例如 f(3) 和 f(3.0)蛾茉。
python lru_cache示例
from functools import lru_cache
@lru_cache(None)
def add(x, y):
print("calculating: %s + %s" % (x, y))
return x + y
print(add(1, 2))
print(add(1, 2))
print(add(2, 3))
輸出結(jié)果：
calculating: 1 + 2
3
3
calculating: 2 + 3
5
從結(jié)果可以看出讼呢，當(dāng)?shù)诙握{(diào)用 add(1, 2) 時(shí)，并沒(méi)有真正執(zhí)行函數(shù)體谦炬，而是直接返回緩存的結(jié)果悦屏。
注意事項(xiàng)
- 緩存是按照參數(shù)作為鍵
- 所有參數(shù)必須可哈希hash
