」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 使用 Javascript 實作 LRU 緩存

使用 Javascript 實作 LRU 緩存

發佈於2024-10-31
瀏覽:299

LRU Cache Implementation using Javascript

介紹

LRU 代表最近最少使用。 LRU 快取是一種緩存,當快取達到其容量時,最近最少使用的條目將被刪除。

  • 使用LRU快取的主要原因是為了提高存取資料的效能。從快取存取資料通常比從主記憶體或遠端伺服器檢索資料更快。
  • 透過將最近使用的資料儲存在快取中,增加了快取命中的機會,從而提高了資料檢索的速度。

供參考:

  • 映射資料結構用於模仿哈希表的行為。這允許高效的查找、插入和刪除操作。
  • 實現了雙鍊錶以實現元素之間的輕鬆移動。這提供了雙向遍歷(向前和向後)並執行恆定時間插入和刪除的能力。
  • 這兩種資料結構的結合可以實現高效率的操作,利用雜湊表和雙鍊錶的優點。

以下是如何在 JavaScript 中實作 LRU 快取的基本範例:

// Why we need this LRU
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

//Least Recently used
class LRU {
    constructor() {
     this.head = this.tail = null;
     this.map = new Map();
     this.size = 0; // Why I added size, because may be in future we can say if capacity reach to the size, we will remove the tail first and then insert.
    }

    get(key) {
        if (this.map.has(key)) {
            const node = this.map.get(key);

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        }

        return -1;
    }

    update(key, value) {
        if (this.map.has(key)) {
            let node = this.map.get(key);
            node.value = value;

            if (node !== this.head) {
                this.remove(node);
                this.insert(node);
            }

            return node.value;
        } else {
            console.log('Key not found'); 
            // Here we can check for capacity if available we can call insert
            // if capacity is not available we will remove the tail and then insert.
        }
    }

    remove(node) {
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    insert(key, value) {
        const newNode = new Node(key, value);
        this.map.set(key, newNode);
        if (this.head === null) {
            this.head = this.tail = newNode;
            this.size = 1;
            return;
        }
        // We need to insert at the Begining
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head= newNode;
        this.size  ;
        return;
    }
}

const test = new LRU();
test.insert('A', 20);
test.insert('B', 10);
test.insert('C', 5);
test.insert('D', 7);

console.log(test);
console.log('------------------');
console.log('C ---> ', test.get('C'));
console.log('D ---> ', test.get('D'));

console.log('D ---> ', test.update('B', 100));

/*
LRU {
  tail:  Node {
    key: 'A',
    value: 20,
    next: null,
    prev: Node { key: 'B', value: 10, next: [Circular *1], prev: [Node] }
  },
  head:  Node {
    key: 'D',
    value: 7,
    next: Node { key: 'C', value: 5, next: [Node], prev: [Circular *2] },
    prev: null
  },
  map: Map(4) {
    'A' =>  Node {
      key: 'A',
      value: 20,
      next: null,
      prev: [Node]
    },
    'B' => Node { key: 'B', value: 10, next: [Node], prev: [Node] },
    'C' => Node { key: 'C', value: 5, next: [Node], prev: [Node] },
    'D' =>  Node {
      key: 'D',
      value: 7,
      next: [Node],
      prev: null
    }
  },
  size: 4
}
------------------
C --->  5
D --->  7
D --->  100
B --->  100
*/

如果您有任何疑問,請隨時與我聯繫。

版本聲明 本文轉載於:https://dev.to/ashutoshsarangi/lru-cache-implementation-using-javascript-48no?1如有侵犯,請聯絡[email protected]刪除
最新教學 更多>
  • 哪種方法更有效地用於點 - 填點檢測:射線跟踪或matplotlib \的路徑contains_points?
    哪種方法更有效地用於點 - 填點檢測:射線跟踪或matplotlib \的路徑contains_points?
    在Python Matplotlib's path.contains_points FunctionMatplotlib's path.contains_points function employs a path object to represent the polygon.它...
    程式設計 發佈於2025-04-06
  • 如何從PHP中的Unicode字符串中有效地產生對URL友好的sl。
    如何從PHP中的Unicode字符串中有效地產生對URL友好的sl。
    為有效的slug生成首先,該函數用指定的分隔符替換所有非字母或數字字符。此步驟可確保slug遵守URL慣例。隨後,它採用ICONV函數將文本簡化為us-ascii兼容格式,從而允許更廣泛的字符集合兼容性。 接下來,該函數使用正則表達式刪除了不需要的字符,例如特殊字符和空格。此步驟可確保slug僅包...
    程式設計 發佈於2025-04-06
  • 如何使用不同數量列的聯合數據庫表?
    如何使用不同數量列的聯合數據庫表?
    合併列數不同的表 當嘗試合併列數不同的數據庫表時,可能會遇到挑戰。一種直接的方法是在列數較少的表中,為缺失的列追加空值。 例如,考慮兩個表,表 A 和表 B,其中表 A 的列數多於表 B。為了合併這些表,同時處理表 B 中缺失的列,請按照以下步驟操作: 確定表 B 中缺失的列,並將它們添加到表的...
    程式設計 發佈於2025-04-06
  • 如何克服PHP的功能重新定義限制?
    如何克服PHP的功能重新定義限制?
    克服PHP的函數重新定義限制在PHP中,多次定義一個相同名稱的函數是一個no-no。嘗試這樣做,如提供的代碼段所示,將導致可怕的“不能重新列出”錯誤。 但是,PHP工具腰帶中有一個隱藏的寶石:runkit擴展。它使您能夠靈活地重新定義函數。 runkit_function_renction_...
    程式設計 發佈於2025-04-06
  • 為什麼使用固定定位時,為什麼具有100%網格板柱的網格超越身體?
    為什麼使用固定定位時,為什麼具有100%網格板柱的網格超越身體?
    網格超過身體,用100%grid-template-columns 為什麼在grid-template-colms中具有100%的顯示器,當位置設置為設置的位置時,grid-template-colly修復了? 問題: 考慮以下CSS和html: class =“ snippet-code”> ...
    程式設計 發佈於2025-04-06
  • 在細胞編輯後,如何維護自定義的JTable細胞渲染?
    在細胞編輯後,如何維護自定義的JTable細胞渲染?
    在JTable中維護jtable單元格渲染後,在JTable中,在JTable中實現自定義單元格渲染和編輯功能可以增強用戶體驗。但是,至關重要的是要確保即使在編輯操作後也保留所需的格式。 在設置用於格式化“價格”列的“價格”列,用戶遇到的數字格式丟失的“價格”列的“價格”之後,問題在設置自定義單元...
    程式設計 發佈於2025-04-06
  • 如何簡化PHP中的JSON解析以獲取多維陣列?
    如何簡化PHP中的JSON解析以獲取多維陣列?
    php 試圖在PHP中解析JSON數據的JSON可能具有挑戰性,尤其是在處理多維數組時。 To simplify the process, it's recommended to parse the JSON as an array rather than an object.To do...
    程式設計 發佈於2025-04-06
  • 如何在Java中正確顯示“ DD/MM/YYYY HH:MM:SS.SS”格式的當前日期和時間?
    如何在Java中正確顯示“ DD/MM/YYYY HH:MM:SS.SS”格式的當前日期和時間?
    如何在“ dd/mm/yyyy hh:mm:mm:ss.ss”格式“ gormat 解決方案: args)拋出異常{ 日曆cal = calendar.getInstance(); SimpleDateFormat SDF =新的SimpleDateFormat(“...
    程式設計 發佈於2025-04-06
  • 如何從PHP中的數組中提取隨機元素?
    如何從PHP中的數組中提取隨機元素?
    從陣列中的隨機選擇,可以輕鬆從數組中獲取隨機項目。考慮以下數組:; 從此數組中檢索一個隨機項目,利用array_rand( array_rand()函數從數組返回一個隨機鍵。通過將$項目數組索引使用此鍵,我們可以從數組中訪問一個隨機元素。這種方法為選擇隨機項目提供了一種直接且可靠的方法。
    程式設計 發佈於2025-04-06
  • 如何使用PHP將斑點(圖像)正確插入MySQL?
    如何使用PHP將斑點(圖像)正確插入MySQL?
    essue VALUES('$this->image_id','file_get_contents($tmp_image)')";This code builds a string in PHP, but the function call fil...
    程式設計 發佈於2025-04-06
  • HTML格式標籤
    HTML格式標籤
    HTML 格式化元素 **HTML Formatting is a process of formatting text for better look and feel. HTML provides us ability to format text without us...
    程式設計 發佈於2025-04-06
  • 為什麼我會收到MySQL錯誤#1089:錯誤的前綴密鑰?
    為什麼我會收到MySQL錯誤#1089:錯誤的前綴密鑰?
    mySQL錯誤#1089:錯誤的前綴鍵錯誤descript [#1089-不正確的前綴鍵在嘗試在表中創建一個prefix鍵時會出現。前綴鍵旨在索引字符串列的特定前綴長度長度,以便更快地搜索這些前綴。 理解prefix keys `這將在整個Movie_ID列上創建標準主鍵。主密鑰對於唯一識...
    程式設計 發佈於2025-04-06
  • 如何有效地選擇熊貓數據框中的列?
    如何有效地選擇熊貓數據框中的列?
    在處理數據操作任務時,在Pandas DataFrames 中選擇列時,選擇特定列的必要條件是必要的。在Pandas中,選擇列的各種選項。 選項1:使用列名 如果已知列索引,請使用ILOC函數選擇它們。請注意,python索引基於零。 df1 = df.iloc [:,0:2]#使用索引0和1 ...
    程式設計 發佈於2025-04-06
  • 如何限制動態大小的父元素中元素的滾動範圍?
    如何限制動態大小的父元素中元素的滾動範圍?
    在交互式接口中實現垂直滾動元素的CSS高度限制問題:考慮一個佈局,其中我們具有與用戶垂直滾動一起移動的可滾動地圖div,同時與固定的固定sidebar保持一致。但是,地圖的滾動無限期擴展,超過了視口的高度,阻止用戶訪問頁面頁腳。 映射{} 因此。我們不使用jQuery的“ .aimimate...
    程式設計 發佈於2025-04-06
  • 如何使用PHP從XML文件中有效地檢索屬性值?
    如何使用PHP從XML文件中有效地檢索屬性值?
    從php PHP陷入困境。 使用simplexmlelement :: attributes()函數提供了簡單的解決方案。此函數可訪問對XML元素作為關聯數組的屬性: - > attributes()為$ attributeName => $ attributeValue){ echo...
    程式設計 發佈於2025-04-06

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3