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
  • 在C#中使用SQL Server實現事務的ACID(原子性、一致性、隔離性、持久性)屬性和使用資料庫鎖(悲觀鎖和樂觀鎖)時,你可以通過ADO.NET的SqlConnection和SqlTransaction類來實現。下麵是一些示例和概念說明。 實現ACID事務 ACID屬性是事務處理的四個基本特征, ...
  • 我們在《SqlSugar開發框架》中,Winform界面開發部分往往也用到了自定義的用戶控制項,對應一些特殊的界面或者常用到的一些局部界面內容,我們可以使用自定義的用戶控制項來提高界面的統一性,同時也增強了使用的便利性。如我們Winform界面中用到的分頁控制項、附件顯示內容、以及一些公司、部門、菜單的下... ...
  • 在本篇教程中,我們學習瞭如何在 Taurus.MVC WebMVC 中進行數據綁定操作。我們還學習瞭如何使用 ${屬性名稱} CMS 語法來綁定頁面上的元素與 Model 中的屬性。通過這些步驟,我們成功實現了一個簡單的數據綁定示例。 ...
  • 是在MVVM中用來傳遞消息的一種方式。它是在MVVMLight框架中提供的一個實現了IMessenger介面的類,可以用來在ViewModel之間、ViewModel和View之間傳遞消息。 Send 接受一個泛型參數,表示要發送的消息內容。 Register 方法用於註冊某個對象接收消息。 pub ...
  • 概述:在WPF中,通過EventHandler可實現基礎和高級的UI更新方式。基礎用法涉及在類中定義事件,併在UI中訂閱以執行更新操作。高級用法藉助Dispatcher類,確保在非UI線程上執行操作後,通過UI線程更新界面。這兩種方法提供了靈活而可靠的UI更新機制。 在WPF(Windows Pre ...
  • 概述:本文介紹了在C#程式開發中如何利用自定義擴展方法測量代碼執行時間。通過使用簡單的Action委托,開發者可以輕鬆獲取代碼塊的執行時間,幫助優化性能、驗證演算法效率以及監控系統性能。這種通用方法提供了一種便捷而有效的方式,有助於提高開發效率和代碼質量。 在軟體開發中,瞭解代碼執行時間是優化程式性能 ...
  • 概述:Cron表達式是一種強大的定時任務調度工具,通過配置不同欄位實現靈活的時間規定。在.NET中,Quartz庫提供了簡便的方式配置Cron表達式,實現精準的定時任務調度。這種靈活性和可擴展性使得開發者能夠根據需求輕鬆地制定和管理定時任務,例如每天備份系統日誌或其他重要操作。 Cron表達式詳解 ...
  • 概述:.NET提供多種定時器,如System.Windows.Forms.Timer適用於UI,System.Web.UI.Timer用於Web,System.Diagnostics.Timer用於性能監控,System.Threading.Timer和System.Timers.Timer用於一般 ...
  • 問題背景 有同事聯繫我說,在生產環境上,訪問不了我負責的common服務,然後我去檢查common服務的health endpoint, 沒問題,然後我問了下異常,timeout導致的System.OperationCanceledException。那大概率是客戶端的問題,會不會是埠耗盡,用ne ...
  • 前言: 在本篇 Taurus.MVC WebMVC 入門開發教程的第四篇文章中, 我們將學習如何實現數據列表的綁定,通過使用 List<Model> 來展示多個數據項。 我們將繼續使用 Taurus.Mvc 命名空間,同時探討如何在視圖中綁定並顯示一個 Model 列表。 步驟1:創建 Model ...