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
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...