Javascript 手寫 LRU 演算法

来源:https://www.cnblogs.com/kelsen/archive/2022/09/29/16743231.html
-Advertisement-
Play Games

LRU 是 Least Recently Used 的縮寫,即最近最少使用。作為一種經典的緩存策略,它的基本思想是長期不被使用的數據,在未來被用到的幾率也不大,所以當新的數據進來時我們可以優先把這些數據替換掉。 一、基本要求 固定大小:限制記憶體使用。 快速訪問:緩存插入和查找操作應該很快,最好是 O ...


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 定義節點類

包含 prevnextdata 三個屬性,分別用以存儲指向前後節點的引用,以及當前節點要存儲的數據。

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

4.2 定義鏈表類

包含 headtail 屬性,分別指向鏈表的 頭節點尾節點

當從鏈表中讀取數據時,需要將當前讀取的數據移動到鏈表頭部;添加數據時,將新節點插入到頭部;當鏈表節點數量大於限定的閥值,需要從鏈表尾部刪除節點。

{
    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/

識微見遠 格物致知
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 前文回顧 實現一個簡單的Database1(譯文) 實現一個簡單的Database2(譯文) 實現一個簡單的Database3(譯文) 譯註:cstsck在github維護了一個簡單的、類似sqlite的資料庫實現,通過這個簡單的項目,可以很好的理解資料庫是如何運行的。本文是第三篇,主要是實現資料庫 ...
  • SELECT定義: SQL的SELECT語句可以實現對錶的選擇、投影及連接操作。即SELECT語句可以從一個或多個表中根據用戶的需要從資料庫中選出匹配的行和列,結果通常是生成一個臨時表。 SELECT語句功能強大,有很多子句,所有被使用的子句必須按語法說明的順序嚴格地排序。 查詢數據表,區分單列查詢 ...
  • 可能就會有人在問:安裝MySQL為什麼還要圖形化軟體? 實際上MySQL有兩種方式來執行請求,一是通過手打命令的方式,二是通過圖形化界面來進行操作,後者本質上也是通過輸入命令來執行請求,但是它可以使操作更簡單,避免一些重覆性的輸入。 這裡我將提供兩種流行的圖形化軟體:Navicat和DataGrip ...
  • Android許可權詢問 AndroidMaifest.xml中聲明許可權 <!-- 聲明所有需要的許可權(包括普通許可權和危險許可權) --> <uses-permission android:name="android.permission.READ_EXTERNAL_STORAGE" /> <uses- ...
  • vue組件中最常見的數據傳遞就是父子組件之間的傳遞,父組件可以通過 props 向下傳數據給子組件,子組件可以通過 $emit 事件攜帶數據給父組件。然而當兩個頁面沒有任關係,該如何通信?這就引出了 EventBus ( 事件匯流排 ) 這個概念 初始化 方法一:新建文件 首先需要初始化一個 Even ...
  • #背景 什麼是tapable、hook,平時做vue開發時的webpack 配置一直都沒弄懂,你也有這種情況嗎? 還是看源碼,閑來無聊又看一下webpack的源碼,看看能否找到一些寶藏 tapable和webpack沒有特定關係,可以先看下這篇文章,瞭解下這個小型庫 https://webpack. ...
  • JavaScript排序 — sort()方法 ——解決null、undefined、0之間的排序(混亂)問題 一、普通的數組排序 ​ JavaScript中用方法sort()為數組排序。sort()方法有一個可選參數,是用來確定元素順序的函數。如果這個參數被省略,那麼數組中的元素將按照ASCII字 ...
  • ##vue路由守衛用於登錄驗證許可權攔截 ###vue路由守衛 - 全局(router.beforeEach((to, from, next) =>來判斷登錄和路由跳轉狀態) ###主要方法: to:進入到哪個路由去 from:從哪個路由離開 next:路由的控制參數,常用的有next(true)和n ...
一周排行
    -Advertisement-
    Play Games
  • public static void GetRegistData() { string name = "huishuangzhu"; //搜索到註冊表根目錄 RegistryKey hkml = Registry.ClassesRoot; //搜索到註冊表根目錄下的XXX文件夾。 RegistryK ...
  • 用acme.sh自動部署功能變數名稱證書 安裝ACME 目前使用量最大的免費SSL證書就是Let’s Encrypt,自2018-03開始,Let’s Encrypt官方發佈上線了免費的SSL泛功能變數名稱證書,目前通過DNS方式獲取比較快,國內可以通過鵝雲的DNSPod功能變數名稱API或者貓雲功能變數名稱API自動簽發Let’ ...
  • 經常看到有群友調侃“為什麼搞Java的總在學習JVM調優?那是因為Java爛!我們.NET就不需要搞這些!”真的是這樣嗎?今天我就用一個案例來分析一下。 昨天,一位學生問了我一個問題:他建了一個預設的ASP.NET Core Web API的項目,也就是那個WeatherForecast的預設項目模 ...
  • 1、環境搭建 1.1 依賴 <!-- nacos註冊中心 註解 @EnableDiscoveryClient --> <dependency> <groupId>com.alibaba.cloud</groupId> <artifactId>spring-cloud-starter-alibaba- ...
  • ULID:Universally Unique Lexicographically Sortable Identifier(通用唯一詞典分類標識符) UUID:Universally Unique Identifier(通用唯一標識符) 為什麼不選擇UUID UUID 目前有 5 個版本: 版本1: ...
  • 虛基類/抽象類 抽象類:有純虛函數的類 虛繼承 通過修飾繼承方式, 如代碼2是虛繼承,被虛繼承的類稱為虛基類 虛繼承派生類的記憶體佈局方式 先是vbptr => 派生類的數據 =>基類的數據 , 對比代碼1和代碼2,發現原本基類數據在前面,派生類數據在後面,但是在虛繼承的時候 基類數據方式放到了後面, ...
  • 下麵給出 Kafka 一些重要概念,讓大家對 Kafka 有個整體的認識和感知,後面還會詳細的解析每一個概念的作用以及更深入的原理 • Producer:消息生產者,向 Kafka Broker 發消息的客戶端。 • Consumer:消息消費者,從 Kafka Broker 取消息的客戶端。 • ...
  • 前面介紹了對稱加密演算法,本文將介紹密碼學中另一類重要應用:消息摘要(Digest),什麼是消息摘要?簡單的定義是:對一份數據,進行一個單向的Hash函數,生成一個固定長度的Hash值,這個值就是這份數據的摘要,也稱為指紋。 ...
  • 弟弟最近要考試,臨時抱佛腳在網上找了一堆學習資料複習,這不剛就來找我了,說PDF上有水印,影響閱讀效果,到時候考不好就怪資料不行,氣的我差點當場想把他揍一頓! 算了,弟弟長大了,看在打不過他的份上,就不打他了~ 稍加思索,我想起了Python不是可以去水印?說搞就搞! 去除水印原理 去除方法: 用 ...
  • 作者:陳昌浩 1 導讀 if…else…在代碼中經常使用,聽說可以通過Java 8的Function介面來消滅if…else…!Function介面是什麼?如果通過Function介面介面消滅if…else…呢?讓我們一起來探索一下吧。 2 Function介面 Function介面就是一個有且僅有 ...