LRUCache的實現理及利用python實現的方法

NO IMAGE

簡介

LRU(Least Recently Used)最近最少使用,最近有時間和空間最近的歧義,所以我更喜歡叫它近期最少使用演算法。它的核心思想是,如果一個資料被訪問過,我們有理由相信它在將來被訪問的概率就越高。於是當LRU快取達到設定的最大值時將快取中近期最少使用的物件移除。LRUCache內部使用LinkedHashMap來儲存key-value鍵值對,並將LinkedHashMap設定為訪問順序來體現LRU演算法。

無論是對某個key的get,還是set都算做是對該key的一次使用。當set一個不存在的key,並且LRU Cache中key的數量超過cache size的時候,需要將使用時間距離現在最長的那個key從LRU Cache中清除。

LRU Cache實現

在Java中,LRUCache是通過LinkedHashMap實現的。鄙人照貓畫虎,實現一個Python版的LRU Cache(可能和其他大神的實現有所區別)。

首先,需要說明的是:

LRU Cache物件內部會維護一個 雙端迴圈連結串列 的 頭節點

LRU Cache物件內部會維護一個dict

內部dict的value都是Entry物件,每個Entry物件包含:

key的hash_code(hash_code = hash(key),在本實現中,hash_code相同的不同key,會被當作一個key來處理。因此,對於自定義類,應該實現魔術方法:__hash__)
v – (key, value)對中的value
prev – 前一個物件
next – 後一個物件

具體實現是:

當從LRU Cache中get一個key的時候:

計算該key的hash_code
從內部dict中獲取到entry
將該entry移動到 雙端迴圈連結串列 的 第一個位置
返回entry.value

當向LRU Cache中set一個(key, value)對的時候:

計算該key的hash_code,

從LRU Cache的內部dict中,取出該hash_code對應的old_entry(可能不存在),然後根據(key, value)對生成一個new_entry,之後執行:

dict[hash_code] = new_entry
將new_entry提到 雙端迴圈連結串列 的第一個位置
如果old_entry存在,則從連結串列中刪除old_entry
如果是新增了一個(key, value)對,並且cache中key的數量超過了cache size,那麼將雙端連結串列的最後一個元素刪除(該元素就是那個最近最少被使用的元素),並且從內部dict中刪除該元素

HashMap的實現原理

(面試過程中也經常會被問到):陣列和連結串列組合成的連結串列雜湊結構,通過hash演算法,儘量將陣列中的資料分佈均勻,如果hashcode相同再比較equals方法,如果equals方法返回false,那麼就將資料以連結串列的形式儲存在陣列的對應位置,並將之前在該位置的資料往連結串列的後面移動,並記錄一個next屬性,來指示後移的那個資料。

注意:陣列中儲存的是entry(其中儲存的是鍵值)

Python實現


class Entry:
def __init__(self, hash_code, v, prev=None, next=None):
self.hash_code = hash_code
self.v = v
self.prev = prev
self.next = next
def __str__(self):
return "Entry{hash_code=%d, v=%s}" % (
self.hash_code, self.v)
__repr__ = __str__
class LRUCache:
def __init__(self, max_size):
self._max_size = max_size
self._dict = dict()
self._head = Entry(None, None)
self._head.prev = self._head
self._head.next = self._head
def __setitem__(self, k, v):
try:
hash_code = hash(k)
except TypeError:
raise
old_entry = self._dict.get(hash_code)
new_entry = Entry(hash_code, v)
self._dict[hash_code] = new_entry
if old_entry:
prev = old_entry.prev
next = old_entry.next
prev.next = next
next.prev = prev
head = self._head
head_prev = self._head.prev
head_next = self._head.next
head.next = new_entry
if head_prev is head:
head.prev = new_entry
head_next.prev = new_entry
new_entry.prev = head
new_entry.next = head_next
if not old_entry and len(self._dict) > self._max_size:
last_one = head.prev
last_one.prev.next = head
head.prev = last_one.prev
self._dict.pop(last_one.hash_code)
def __getitem__(self, k):
entry = self._dict[hash(k)]
head = self._head
head_next = head.next
prev = entry.prev
next = entry.next
if entry.prev is not head:
if head.prev is entry:
head.prev = prev
head.next = entry
head_next.prev = entry
entry.prev = head
entry.next = head_next
prev.next = next
next.prev = prev
return entry.v
def get_dict(self):
return self._dict
if __name__ == "__main__":
cache = LRUCache(2)
inner_dict = cache.get_dict()
cache[1] = 1
assert inner_dict.keys() == [1], "test 1"
cache[2] = 2
assert sorted(inner_dict.keys()) == [1, 2], "test 2"
cache[3] = 3
assert sorted(inner_dict.keys()) == [2, 3], "test 3"
cache[2]
assert sorted(inner_dict.keys()) == [2, 3], "test 4"
assert inner_dict[hash(2)].next.v == 3
cache[4] = 4
assert sorted(inner_dict.keys()) == [2, 4], "test 5"
assert inner_dict[hash(4)].v == 4, "test 6"

總結

以上就是這篇文章的全部內容了,希望本文的內容對大家的學習或者工作具有一定的參考學習價值,如果有疑問大家可以留言交流,謝謝大家對指令碼之家的支援。

您可能感興趣的文章:

C 開發在IOS環境下執行的LRUCache快取功能Android 載入大圖、多圖和LruCache快取詳細介紹Java資源快取 之 LruCache詳解Android的記憶體優化–LruCache