TechBridge 技術共筆部落格

var topics = ['Web前後端', '行動網路', '機器人/物聯網', '數據分析', '產品設計', 'etc.']

如何使用 Python 實現 LRU Cache 快取置換機制


如何使用 Python 實現 LRU 快取

前言

由於電腦記憶體空間(memory)的限制,無法容納所有資料和文件,所以當有新的文件要被置換進入快取(cache)時,必須根據一定的規則來取代掉適合的文件,這就是所謂的快取文件置換機制。

一般來說常見的快取文件置換機制有:

  1. FIFO(First In, First Out)先進先出算法
  2. LFU(Least Frequently Used)最近最不常使用算法
  3. LRU(Least Recently Used)最近最少使用算法
  4. NMRU(Not Most Recently Used)非最近使用算法

通常我們評量快取機制的指標主要有兩種:延遲(latency)和命中率(hit rate),其中延遲指的是命中後回傳對應資料的所花的時間。而命中率則是需要的資料在快取中被找到的頻率。

本文則要介紹 LRU(Least Recently Used)這個常見經典算法(在 memcached 也有使用),並使用 Python 實現簡單的 LRU 算法。其核心思想主要就是如果資料最近有被使用過,則未來被使用的機率也比較高。實際上的實作基本概念就是快取一定的資料量,若是超過一定的資料量則把最近最少使用的資料淘汰掉。

LRU 基本原理

如何使用 Python 實現 LRU 快取

關於 LRU 算法用生活化一點說明就像是平常衣架管理衣服一樣。想像你的衣架是一個有限空間的衣架,越常穿的衣服靠外面。當我們有新衣服時會先從前面放入,要穿衣服時則會把想要的衣服拿出來使用,洗完後放到最前面(因為比較常穿)。當衣服太多超過衣架可容納空間時,最後面不常穿的衣服從衣架掉下去,消失不見:P

使用 Python 實現 LRU 快取方案

通常我們常會使用 hash map 搭配 Double Linked List 來實作(set/get 時間複雜度 O(1)),這樣可以避免單純使用陣列並存 counter/timestamp 的方式需要不停維護 counter 或是只使用 Linked List 實作,在 get 值時時間複雜度為 O(n),來的合適。

如何使用 Python 實現 LRU 快取

以下我們使用 Python Dict (hash map) 和 Queue (Double Linked List) 來實作簡單的 LRU 算法。

建立一個給定大小的 LRU cache 系統,並實作兩種操作方式,取值和設定值

  1. get(key):當 key 對應的值存在 cache 系統中時回傳該值,並把該值放到 cache 系統最前面,若沒有對應值則回傳 -1
  2. set(key, value):當 key 不存在 cache 系統中時,則將 key, value 放入 cache,若系統值滿則移除最不常使用的 key, value 並塞入插入新的 key, value
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
from collections import deque


class LRUCache:
def __init__(self, cache_size):
self.cache_size = cache_size
self.queue = deque()
self.hash_map = dict()

def is_queue_full(self):
return len(self.queue) == self.cache_size

def set(self, key, value):
if key not in self.hash_map:
if self.is_queue_full():
pop_key = self.queue.pop()
self.hash_map.pop(pop_key)
self.queue.appendleft(key)
self.hash_map[key] = value
else:
self.queue.appendleft(key)
self.hash_map[key] = value

def get(self, key):
if key not in self.hash_map:
return -1
else:
self.queue.remove(key)
self.queue.appendleft(key)
return self.hash_map[key]


if __name__ == '__main__':
# 設定 cache 大小為 3
lru_cache = LRUCache(3)

lru_cache.set('key1', 7)
lru_cache.set('key2', 2)
lru_cache.set('key3', 3)
lru_cache.set('key4', 4)
print(lru_cache.get('key2'))
# 超過 cache 大小,被丟棄,所以 key1 回傳值為 -1
print(lru_cache.get('key1'))
lru_cache.set('key1', 7)
# key1 已存在 cache 中,所以不做任何動作
lru_cache.set('key1', 2)
print(lru_cache.get('key1'))

總結

以上簡單介紹如何使用 Python 實現 LRU 快取方案,若是讀者有興趣的話可以自己嘗試 OrderedDict 實作或是針對 multi thread 進行 cache 讀寫操作設計,甚至可以模仿 redis 或 memcached 給儲存資料追加 expire time,實作一個(自幹輪子)更完整的 cache 系統解決方案!

參考文件

  1. 快取文件置換機制

(image via twimgtopjavatutorialHacker Noon

關於作者:
@kdchang 文藝型開發者,夢想是做出人們想用的產品和辦一所心目中理想的學校。A Starter & Maker. JavaScript, Python & Arduino/Android lover.:)

喜歡我們的文章嗎?歡迎分享按讚給予我們支持和鼓勵!





訂閱 TechBridge Weekly 技術週刊,每週發送最精華的技術開發、產品設計的資訊給您



TechBridge Weekly 技術週刊編輯團隊

TechBridge Weekly 技術週刊團隊是一群對用技術改變世界懷抱熱情的團隊。本技術共筆部落格初期專注於Web前後端、行動網路、機器人/物聯網、資料科學與產品設計等技術分享。This is TechBridge Weekly Team Tech Blog, which focus on web, mobile, robot, IoT, Data Science technology sharing.

關於我們 / 技術日報 / 技術週刊 / 粉絲專頁 / 訂閱RSS

留言討論