前言
一陣子沒有寫文章了,最近沒有什麼靈感,前陣子在看一些 System Design 的文章時,看到題目中有提到 LRU Cache 機制,覺得挺有意思的就想著要來用 Python 來實作一個簡單的 LRU Cache 機制。
因為要有效率地運用電腦有限的空間,不能把所有要記錄的東西都存在某個儲存空間上,所以必須要有個機制來汰換資料,而汰換資料的方法大略分為下列四種:
- FIFO (First In, First Out)
- NMRU (Not Most Recently Used)
- LFU (Least Frequently Used)
- LRU (Least Recently Used)
在 CPU 快取的角度來說,當 CPU 發出 RAM 存取請求時,會先查看 Cache 內是否有請求資料。如果存在(命中),則不透過存取 RAM 的過程而直接返回資料。如果不存在(失效),則要先把 RAM 中的資料先存到 Cache 內,再把資料丟給 CPU。
上述第三種和第四種其實規則非常相似,而 LRU 就是我們今天要講的主角,在一個有限的空間內,若是資料已經達到空間上限時,就要進行所謂的「汰換」,而根據 LRU 的定義,我們就需要淘汰最近最少使用的資料,這邊我們用 Python 來實作。
LRU 是什麼
用生活上的例子來說明 LRU Cache 機制是最簡單不過的了,之前有看到有人用衣服放在衣櫃裡的情境來形容,這邊借用一下圖片。
可以想想自己衣櫃平常是怎麼被使用的,常穿的衣服一定都是衣櫃靠近前面那幾件,要用的時候拿出來穿,穿完之後洗乾淨再掛回衣櫃的前面,一直沒有在穿的衣服就被堆到衣櫃的後方,直到哪一天突然想到一件很久沒穿的衣服,拿出來穿完洗乾淨之後再放回衣櫃的前面。
那衣櫃的空間不可能無限地成長啊!所以這時候媽媽(限制)說話了:「是時候把你衣櫃整理整理了!」這時候的你一定會苦惱要丟那些衣服,套用 LRU Cache 機制的話,這時候你就會選擇把衣櫃最後方最不常穿的衣服丟掉。
實作
要實作 LRU Cache 有好幾種方法,這邊簡單提一下:
- LinkedHashMap
- Hash Map + Double Linked List
在 Python 中,我們很間單就能夠使用第二個方法提到的兩個資料結構,分別是 Dictionary (Hash Map) 及 Deque (Double Linked List),在 Get 和 Set 的時間複雜度都會是 O(1),非常適合用來實作這個機制,在下面我們會將把衣服放回至衣櫃的最前面叫做 Refresh 。
Get(Key)
回傳 Cache 中 Key 的 Value 並將 Refresh 該 Key,若 Key 不存在則傳回 None。
Set(Key, Value)
分為兩種情況,用 Key 在不在 Cache 內來分:
- 若 Key 在 Cache 裡:代表空間一定是夠的,直接 Refresh 該 Key 就好
- 若 Key 不在 Cache 裡:如果空間已經滿了,就把最尾端的資料 Pop 掉,再把 Key 放進隊伍的頭;如果空間還沒滿,就直接把 Key 放進隊伍的頭。
構思了兩個簡單的 Function,接下來就來實作吧!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from collections import deque
class LRUCache:
def __init__(self, size):
self.size = size
self.hash_map = dict()
self.queue = deque()
def get(self, key):
if key in self.hash_map:
# 將 Key 從 Queue 中拿出並放到最前面
self.queue.remove(key)
self.queue.appendleft(key)
return self.hash_map[key] # 回傳該 Key 的值
def set(self, key, value):
if key not in self.hash_map:
if len(self.queue) == self.size:
deleted_key = self.queue.pop() # 將最後一個順位的 Key pop 掉
self.queue.appendleft(key)
self.hash_map[key] = value
del self.hash_map[deleted_key] # 清除 Dict 裡面不必要的 Key
else:
self.hash_map[key] = value
self.queue.appendleft(key)
else:
# 若 Key 已經在 HashMap 裡面就直接 Refresh 該 Key 即可
self.queue.remove(key)
self.queue.appendleft(key)
self.hash_map[key] = value
cache = LRUCache(3)
cache.set("A", 1) # cache.deque = ["A"]
cache.set("B", 2) # cache.deque = ["B", "A"]
cache.set("C", 3) # cache.deque = ["C", "B", "A"]
cache.get("A") # 1, cache.deque = ["A", "C", "B"], A is refreshed
cache.get("D") # None
cache.set("D", 4) # cache.deque = ["D", "A", "C"], B is poped
cache.set("C", 5) # cache.deque = ["C", "D", "A"], C is refreshed
總結
實作過一遍之後就會對概念更加清楚,強烈建議有興趣的讀者自己也實作一遍,理解衣服與衣櫃的概念之後,透過自己的方式去構思,試看看自己寫出 Get 和 Set 的 Function,之後對於一些 System Design 的題目要求也會有一些基本的概念!
參考
LRU & LFU 緩存機制的原理及實現
如何使用 Python 實現 LRU Cache 快取置換機制
記憶體延遲:因與果
快取文件置換機制