演算法系列(1) LRU

8 min readJun 20, 2021

描述

LRU 的全名為 Least Recently Used，是一種緩存淘汰的策略，因為緩存的容量是有限的，所以當緩存的容量滿了，就必須將沒有用的資料清除, 留下有用的資料，那怎麼判定為有用的資料呢? 在這個演算法的策略裡認為最近使用過的資料是有用的，很久沒使用的資料是沒有用的，所以當要在緩存中加入新的資料時，發現緩存的容量滿了就必須刪除沒有用的資料，這樣才有空間可以加入新的資料。

設計

首先，這個演算法需要先接受一個參數 capacity 來定義緩存的容量大小，接著實作兩個功能，塞入資料以及拿取資料，並且這兩個功能的時間複雜度都要是 O(1)

Function:

塞入資料: put(key, value)
拿取資料: get(key)

接著分析上面描述的功能並決定要使用哪一種資料結構，先把這個資料結構稱為 cache

在 cache 中的資料必須要有順序性，因為要用來分別最近使用的資料或是很久沒使用的資料，當 cache 容量滿了需要刪除最久沒使用的資料來釋出空間。
要在 cache 中透過 key 確認資料是否存在並且得到資料。
每次透過 key 從 cache 拿取資料必須將此次拿取的資料變成最近使用的資料，所以 cache 需要支援能夠在任意位置做插入刪除資料的行為。

根據上面列出的三個項目，能夠知道這個資料結構必須要查詢速度快且插入刪除資料快，這時候就可以想到兩種資料結構

hash map: 查詢速度快，但是沒有順序性
linked list: 有順序性，插入刪除速度快，但是查詢速度慢

於是結合兩種資料結構的優勢，產生新的資料結構，稱為 LinkedHashMap，也是 LRU 的核心資料結構，這個資料結構長的如下圖:

透過 LinkedHashMap 結構，能夠符合分析的三個項目

每次都是從 Tail 端新增資料，越靠近 Tail 就是最近使用的資料，越靠近 Head 就是越久沒使用的資料
透過 Hash Map 使用 key 能快速定位資料，找到 Double Linked List 的節點，進一步取得 value
Double Linked List 進行插入刪除速度快，但是沒辦法直接查詢到所要的節點，所以透過 Hash Map 直接 Mapping 到特定的節點進行插入刪除。

程式碼

首先要先定義一下節點的資料結構，有 key, value 以及指向前後節點的兩個指標

class Node:
    def __init__(self, key: int, value: int, left=None, right=None):
        self.prev = left
        self.next = right
        self.key = key
        self.value = value

接著是定義 Double Linked List 的資料結構

class DoubleList:
    # 初始化此結構，產生head和tail兩個節點，並且鏈結起來
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    #從tail端加入新節點
    def addLast(self, x: Node):
        x.next = self.tail
        x.prev = self.tail.prev
        #要注意下面兩行的順序不可以對調，否則會無法把原本在tail前面的節點鏈結到新節點
        self.tail.prev.next = x
        self.tail.prev = x
        self.size += 1
    #移除特定的節點
    def remove(self, x: Node):
        x.next.prev = x.prev
        x.prev.next = x.next
        x.prev = None
        x.next = None
        self.size -= 1
    #移除最久之前的節點
    def removeFirst(self):
        if self.head.next == self.tail:
            return None
        first_node = self.head.next
        self.remove(first_node)
        return first_node
        
    def getSize(self):
        return self.size

最後就是實作 LRU 的部分，一共兩個功能，但由於 Hash Map 和 Linked List 的資料必須要一致，不然會有錯誤發生，所以我們提供抽象的API，避免put 和get這兩個功能直接操作 Hash Map 和 Linked List

class LRUCache:
    #初始化
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.lruCache = DoubleList()    def get(self, key: int) -> int:
        #接下來會實作
        return x.value    def put(self, key: int, value: int) -> None:
        #接下來會實作
        return
        
    #將節點變成最新使用過的資料
    def makeRecently(self, key: int):
        x = self.map.get(key)
        self.lruCache.remove(x)
        self.lruCache.addLast(x)
    #加入新節點並且是最新使用的資料
    def addRecently(self, key: int, value: int):
        x = Node(key, value)
        self.lruCache.addLast(x)
        self.map[key] = x
    #刪除節點
    def deleteKey(self, key: int):
        x = self.map.get(key)
        self.lruCache.remove(x)
        self.map.pop(key)
    #刪除最久沒使用的資料
    def removeLeastRecently(self):
        firstNode = self.lruCache.removeFirst()
        self.map.pop(firstNode.key)

get和put的實作

class LRUCache:
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.lruCache = DoubleList()    def get(self, key: int) -> int:
        x = self.map.get(key)
        if x == None:
            return -1
        self.makeRecently(key)
        return x.value    def put(self, key: int, value: int) -> None:
        x = self.map.get(key)
        if x != None:
            self.deleteKey(key)
            self.addRecently(key, value)
            return
        if self.capacity == self.lruCache.getSize():
            self.removeLeastRecently()
        self.addRecently(key, value)
        return

大功告成啦！

結論

終於一個段落了，呼，總結一下

需要 Double Linked List 的原因是因為要刪除節點的時候，除了找到要刪除的節點外，還需要知道該節點前後節點的位置，才能達到時間複雜度為 O(1)。
節點需要把key存起來的原因是因為刪除最久未使用的資料時，要先從 Double Linked List 做刪除的動作，因為 Double Linked List 才有順序性，當刪除完資料後，也需要刪除 Hash Map 的資料，所以需要透過節點的key去刪除 Hash Map 裡面的資料。
把 Hash Map 以及 Double Linked List 在抽象一層出來的原因是因為操作兩種資料結構時，可能會有操作失誤，可能刪除Double Linked List的節點，但是忘記將 Hash Map 的key刪除。
上面 Double Linked List 提供了四種功能
(1) 新增節點
(2) 刪除特定節點
(3) 刪除最久未使用的節點
(4) 節點數量: 未包含 Head 和 Tail
上面將操作Hash Map 以及 Double Linked List兩種資料結構的功能抽象一層，提供了四種功能
(1) 將節點變成最新使用的節點: get 使用
(2) 新增節點為最新使用的節點: put 使用
(3) 刪除特定的節點: put 使用
(4) 移除最久未使用的節點: put 使用

演算法系列(1) LRU

描述

設計

Function:

程式碼

結論

Written by Charles Chou

No responses yet