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
  • 1.部署歷史 猿友們好,作為初來實習的我,已經遭受社會的“毒打”,所以請容許我在下麵環節適當吐槽,3Q! 傳統部署 ​ 回顧以往在伺服器部署webapi項目(非獨立發佈),dotnet環境、守護進程兩個逃都逃不掉,正常情況下還得來個nginx代理。不僅僅這仨,可能牽扯到yum或npm。node等都要 ...
  • 隨著技術的進步,跨平臺開發已經成為了標配,在此大背景下,ASP.NET Core也應運而生。本文主要基於ASP.NET Core+Element+Sql Server開發一個校園圖書管理系統為例,簡述基於MVC三層架構開發的常見知識點,前一篇文章,已經簡單介紹瞭如何搭建開發框架,和登錄功能實現,本篇... ...
  • 這道題只要會自定義cmp恰當地進行排序,其他部分沒有什麼大問題。 上代碼: 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,s,h1,h2,cnt; 4 struct apple{ 5 int height,ns;//height為蘋 ...
  • 這篇文章主要描述RPC的路由策略,包括為什麼需要請求隔離,為什麼不在註冊中心中實現請求隔離以及不同粒度的路由策略。 ...
  • 簡介: 中介者模式,屬於行為型的設計模式。用一個中介對象來封裝一系列的對象交互。中介者是各對象不需要顯式地相互引用,從而使其耦合鬆散,而且可以獨立地改變他們之間的交互。 適用場景: 如果平行對象間的依賴複雜,可以使用中介者解耦。 優點: 符合迪米特法則,減少成員間的依賴。 缺點: 不適用於系統出現對 ...
  • 【前置內容】Spring 學習筆記全系列傳送門: Spring學習筆記 - 第一章 - IoC(控制反轉)、IoC容器、Bean的實例化與生命周期、DI(依賴註入) Spring學習筆記 - 第二章 - 註解開發、配置管理第三方Bean、註解管理第三方Bean、Spring 整合 MyBatis 和 ...
  • 簡介: 享元模式,屬於結構型的設計模式。運用共用技術有效地支持大量細粒度的對象。 適用場景: 具有相同抽象但是細節不同的場景中。 優點: 把公共的部分分離為抽象,細節依賴於抽象,符合依賴倒轉原則。 缺點: 增加複雜性。 代碼: //用戶類 class User { private $name; fu ...
  • 這次設計一個通用的多位元組SPI介面模塊,特點如下: 可以設置為1-128位元組的SPI通信模塊 可以修改CPOL、CPHA來進行不同的通信模式 可以設置輸出的時鐘 狀態轉移圖和思路與多位元組串口發送模塊一樣,這裡就不給出了,具體可看該隨筆。 一、模塊代碼 1、需要的模塊 通用8位SPI介面模塊 `tim ...
  • AOP-03 7.AOP-切入表達式 7.1切入表達式的具體使用 1.切入表達式的作用: 通過表達式的方式定義一個或多個具體的連接點。 2.語法細節: (1)切入表達式的語法格式: execution([許可權修飾符] [返回值類型] [簡單類名/全類名] [方法名]([參數列表]) 若目標類、介面與 ...
  • 測試一、虛繼承與繼承的區別 1.1 單個繼承,不帶虛函數 1>class B size(8): 1> + 1> 0 | + (base class A) 1> 0 | | _ia //4B 1> | + 1> 4 | _ib //4B 有兩個int類型數據成員,占8B,基類邏輯存在前面 1.2、單個 ...