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
  • 經常看到有群友調侃“為什麼搞Java的總在學習JVM調優?那是因為Java爛!我們.NET就不需要搞這些!”真的是這樣嗎?今天我就用一個案例來分析一下。 昨天,一位學生問了我一個問題:他建了一個預設的ASP.NET Core Web API的項目,也就是那個WeatherForecast的預設項目模 ...
  • 很多軟體工程師都認為MD5是一種加密演算法,然而這種觀點是不對的。作為一個 1992 年第一次被公開的演算法,到今天為止已經被髮現了一些致命的漏洞。本文討論MD5在密碼保存方面的一些問題。 ...
  • Maven可以使我們在構建項目時需要用到很多第三方類jar包,如下一些常用jar包 而maven的出現可以讓我們避免手動導入jar包出現的某些問題,它可以自動下載那須所需要的jar包 我們只需要在創建的maven項目自動生成的pom.xml中輸入如下代碼 <dependencies> <!--ser ...
  • 來源:https://developer.aliyun.com/article/694020 非同步調用幾乎是處理高併發Web應用性能問題的萬金油,那麼什麼是“非同步調用”? “非同步調用”對應的是“同步調用”,同步調用指程式按照定義順序依次執行,每一行程式都必須等待上一行程式執行完成之後才能執行;非同步調 ...
  • 1.面向對象 面向對象編程是在面向過程編程的基礎上發展來的,它比面向過程編程具有更強的靈活性和擴展性,所以可以先瞭解下什麼是面向過程編程: 面向過程編程的核心是過程,就是分析出實現需求所需要的步驟,通過函數一步一步實現這些步驟,接著依次調用即可,再簡單理解就是程式 從上到下一步步執行,從頭到尾的解決 ...
  • 10瓶毒藥其中只有一瓶有毒至少需要幾隻老鼠可以找到有毒的那瓶 身似浮雲,心如飛絮,氣若游絲。 用二分查找和二進位位運算的思想都可以把死亡的老鼠降到最低。 其中,二進位位運算就是每一隻老鼠代表一個二進位0或1,0就代表老鼠存活,1代表老鼠死亡;根據數學運算 23 = 8、24 = 16,那麼至少需要四 ...
  • 一、Kafka存在哪些方面的優勢 1. 多生產者 可以無縫地支持多個生產者,不管客戶端在使用單個主題還是多個主題。 2. 多消費者 支持多個消費者從一個單獨的消息流上讀取數據,而且消費者之間互不影響。 3. 基於磁碟的數據存儲 支持消費者非實時地讀取消息,由於消息被提交到磁碟,根據設置的規則進行保存 ...
  • 大家好,我是陶朱公Boy。 前言 上一篇文章《關於狀態機的技術選型,最後一個真心好》我跟大家聊了一下關於”狀態機“的話題。從眾多技術選型中我也推薦了一款阿裡開源的狀態機—“cola-statemachine”。 於是就有小伙伴私信我,自己項目也考慮引入這款狀態機,但網上資料實在太少,能不能系統的介紹 ...
  • 使用腳本自動跑實驗(Ubuntu),將實驗結果記錄在文件中,併在實驗結束之後將結果通過郵件發送到郵箱,最後在windows端自動解析成excel表格。 ...
  • 話說在前面,我不是小黑子~ 我是超級大黑子😏 表弟大周末的跑來我家,沒事幹天天騷擾我,搞得我都不能跟小姐姐好好聊天了,於是為了打發表弟,我決定用Python做一個小游戲來消耗一下他的精力,我思來想去,決定把他變成小黑子,於是做了一個坤坤打籃球的游戲,沒想到他還挺愛玩的~ 終於解放了,於是我把游戲寫 ...