Javascript 手寫 LRU 演算法

2022 年 9 月 29 日
筆記
javascript, LRU, WEB

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

一、基本要求

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

二、數據結構

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

2.1 Map

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

2.2 Doubly Linked List

我們也可通過雙向鏈表（Doubly Linked List）維護快取條目，通過對鏈表的增、刪、改實現數據管理。為確保能夠從鏈表中快速讀取某個節點的數據，我們可以通過 Map 來存儲對鏈表中節點的引用。

三、Map 實現

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

配置存儲限制，當大於此限制，快取條目將按照最近讀取情況被驅逐。
創建一個用於存儲快取數據的 Map 。

在 添加數據 時：

判斷當前存儲數據中是否包含新進數據，如果存在，則刪除當前數據
判斷當前存儲空間是否被用盡，如果已用盡則刪除 Map 頭部的數據。
map.delete(map.keys().next().value)
插入新數據到 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)

如果 map 中存在當前 key，則修改當前節點的值，然後從鏈表中把當前節點移動到鏈表頭部；
否則：
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
        }       
    }
}

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

Tags: javascript LRU WEB