技術文章 » Javascript 手寫 LRU 演演算法

Javascript 手寫 LRU 演演算法

2022-09-30 06:01:54

LRU 是 Least Recently Used 的縮寫，即最近最少使用。作為一種經典的快取策略，它的基本思想是長期不被使用的資料，在未來被用到的機率也不大，所以當新的資料進來時我們可以優先把這些資料替換掉。

一、基本要求

  1. 固定大小：限制記憶體使用。
  2. 快速存取：快取插入和查詢操作應該很快，最好是 O(1) 時間。
  3. 在達到記憶體限制的情況下替換條目：快取應該具有有效的演演算法來在記憶體已滿時驅逐條目。

二、資料結構

下面提供兩種實現方式，並完成相關程式碼。

2.1 Map

在 Javascript 中，Map 的 key 是有序的，當迭代的時候，他們以插入的順序返回鍵值。結合這個特性，我們也通過 Map 實現 LRU 演演算法。

2.2 Doubly Linked List

我們也可通過雙向連結串列（Doubly Linked List）維護快取條目，通過對連結串列的增、刪、改實現資料管理。為確保能夠從連結串列中快速讀取某個節點的資料，我們可以通過 Map 來儲存對連結串列中節點的參照。

三、Map 實現

在 初始化時 完成兩件事情：

  1. 設定儲存限制，當大於此限制，快取條目將按照最近讀取情況被驅逐。
  2. 建立一個用於儲存快取資料的 Map 。

在 新增資料 時：

  1. 判斷當前儲存資料中是否包含新進資料，如果存在，則刪除當前資料
  2. 判斷當前儲存空間是否被用盡，如果已用盡則刪除 Map 頭部的資料。
    map.delete(map.keys().next().value)
  3. 插入新資料到 Map 的尾部

基於 Javascript Map 實現 LRU，程式碼如下：

class LRUCache {
    size = 5
    constructor(size) {
        this.cache = new Map()
        this.size = size || this.size
    }

    get(key) {
        if (this.cache.has(key)) {
            // 存在即更新
            let temp = this.cache.get(key)
            this.cache.delete(key)
            this.cache.set(key, temp)
            return temp
        }
        return null
    }

    set(key, value) {

        if (this.cache.has(key)) {
            this.cache.delete(key)
        }

        if (this.cache.size >= this.size) {
            this.cache.delete(this.cache.keys().next().value)
        }

        this.cache.set(key, value)
    }
}

四、雙向連結串列實現

4.1 定義節點類

包含 prev，next，data 三個屬性，分別用以儲存指向前後節點的參照，以及當前節點要儲存的資料。

{
    prev: Node
    next: Node
    data: { key: string, data: any}
}

4.2 定義連結串列類

包含 head、tail 屬性，分別指向連結串列的 頭節點 和 尾節點。

當從連結串列中讀取資料時，需要將當前讀取的資料移動到連結串列頭部；新增資料時，將新節點插入到頭部；當連結串列節點數量大於限定的閥值，需要從連結串列尾部刪除節點。

{
    head: Node
    next: Node
    moveNodeToHead(node)
    insertNodeToHead(node)
    deleteLastNode()
}

4.3 定義 LRU 類

為 LRU 定義屬性：linkLine 用以儲存指向連結串列的參照；size 用以設定儲存空間大小限制；
為簡化從連結串列中查詢節點，再定義 map 屬性，用以儲存不同鍵指向連結串列節點的參照。

定義成員方法，set(key,value) 用以新增資料，get(key) 讀取一條資料。

4.4 set(key,value)

  1. 如果 map 中存在當前 key，則修改當前節點的值，然後從連結串列中把當前節點移動到連結串列頭部；
  2. 否則：
    1. 判斷當前連結串列節點數量是否達到了儲存上線，如果是，則刪除連結串列尾部的節點。同時從 map 中移除相應的節點參照；
    2. 建立新節點，然後插入到連結串列頭部，並新增 map 參照。

4.5 get(key)

如果 map 中存在當前 key，從連結串列中讀取節點，將其移動到連結串列頭部，並返回結果，否則返回空。

{
    linkLine: LinkLine
    map: Map
    size: Number
    set(key, value)
    get(key)
}

4.6 程式碼實現

class LinkNode {
    prev = null
    next = null
    constructor(key, value) {
        this.data = { key, value }
    }
}

class LinkLine {

    head = null
    tail = null

    constructor() {
        const headNode = new LinkNode('head', 'head')
        const tailNode = new LinkNode('tail', 'tail')

        headNode.next = tailNode
        tailNode.prev = headNode

        this.head = headNode
        this.tail = tailNode
    }

    moveNodeToFirst(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
        this.insertNodeToFirst(node)
    }

    insertNodeToFirst(node) {
        const second = this.head.next
        this.head.next = node
        node.prev = this.head
        node.next = second
        second.prev = node
    }

    delete(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
    }

    deleteLastNode() {
        const last = this.tail.prev
        this.tail.prev = last.prev
        last.prev.next = this.tail
        return last
    }
}

class LRUCache {
    linkLine = null
    map = {}
    size = 5

    constructor(size) {
        this.size = size || this.size
        this.linkLine = new LinkLine
    }

    get(key) {
        let value
        if (this.map[key]) {
            const node = this.map[key]
            value = node.value
            this.linkLine.moveNodeToFirst(node)
        }
        return value
    }

    set(key, value) {
        if (this.map[key]) {
            const node = this.map[key]
            node.value = value
            this.linkLine.moveNodeToFirst(node)
        } else {
            // 刪除最後一個元素
            if (Object.keys(this.map).length >= this.size) {
                const lastNode = this.linkLine.deleteLastNode()
                delete this.map[lastNode.data.key]
            }

            const newNode = new LinkNode(key, value)
            this.linkLine.insertNodeToFirst(newNode)
            this.map[key] = newNode
        }       
    }
}

https://gauliang.github.io/blogs/2022/lru-algorithm/