JavaScript手寫LRU算法的示例代碼
LRU 是 Least Recently Used 的縮寫,即最近最少使用。作為一種經典的緩存策略,它的基本思想是長期不被使用的數(shù)據(jù),在未來被用到的幾率也不大,所以當新的數(shù)據(jù)進來時我們可以優(yōu)先把這些數(shù)據(jù)替換掉。
一、基本要求
- 固定大?。合拗苾却媸褂?。
- 快速訪問:緩存插入和查找操作應該很快,最好是 O(1) 時間。
- 在達到內存限制的情況下替換條目:緩存應該具有有效的算法來在內存已滿時驅逐條目。
二、數(shù)據(jù)結構
下面提供兩種實現(xiàn)方式,并完成相關代碼。
2.1 Map
在 Javascript 中,Map 的 key 是有序的,當?shù)臅r候,他們以插入的順序返回鍵值。結合這個特性,我們也通過 Map 實現(xiàn) LRU 算法。
2.2 Doubly Linked List
我們也可通過雙向鏈表(Doubly Linked List)維護緩存條目,通過對鏈表的增、刪、改實現(xiàn)數(shù)據(jù)管理。為確保能夠從鏈表中快速讀取某個節(jié)點的數(shù)據(jù),我們可以通過 Map 來存儲對鏈表中節(jié)點的引用。
三、Map 實現(xiàn)
在 初始化時 完成兩件事情:
1.配置存儲限制,當大于此限制,緩存條目將按照最近讀取情況被驅逐。
2.創(chuàng)建一個用于存儲緩存數(shù)據(jù)的 Map 。
在 添加數(shù)據(jù) 時:
1.判斷當前存儲數(shù)據(jù)中是否包含新進數(shù)據(jù),如果存在,則刪除當前數(shù)據(jù)
2.判斷當前存儲空間是否被用盡,如果已用盡則刪除 Map 頭部的數(shù)據(jù)。
map.delete(map.keys().next().value)
3.插入新數(shù)據(jù)到 Map 的尾部
基于 Javascript Map 實現(xiàn) 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) } }
四、雙向鏈表實現(xiàn)
4.1 定義節(jié)點類
包含 prev
,next
,data
三個屬性,分別用以存儲指向前后節(jié)點的引用,以及當前節(jié)點要存儲的數(shù)據(jù)。
{ prev: Node next: Node data: { key: string, data: any} }
4.2 定義鏈表類
包含 head
、tail
屬性,分別指向鏈表的 頭節(jié)點 和 尾節(jié)點。
當從鏈表中讀取數(shù)據(jù)時,需要將當前讀取的數(shù)據(jù)移動到鏈表頭部;添加數(shù)據(jù)時,將新節(jié)點插入到頭部;當鏈表節(jié)點數(shù)量大于限定的閥值,需要從鏈表尾部刪除節(jié)點。
{ head: Node next: Node moveNodeToHead(node) insertNodeToHead(node) deleteLastNode() }
4.3 定義 LRU 類
為 LRU 定義屬性:linkLine
用以存儲指向鏈表的引用;size
用以配置存儲空間大小限制;
為簡化從鏈表中查找節(jié)點,再定義 map
屬性,用以存儲不同鍵指向鏈表節(jié)點的引用。
定義成員方法,set(key,value)
用以添加數(shù)據(jù),get(key)
讀取一條數(shù)據(jù)。
4.4 set(key,value)
如果 map 中存在當前 key,則修改當前節(jié)點的值,然后從鏈表中把當前節(jié)點移動到鏈表頭部;
否則:
判斷當前鏈表節(jié)點數(shù)量是否達到了存儲上線,如果是,則刪除鏈表尾部的節(jié)點。同時從 map 中移除相應的節(jié)點引用;
創(chuàng)建新節(jié)點,然后插入到鏈表頭部,并添加 map 引用。
4.5 get(key)
如果 map 中存在當前 key,從鏈表中讀取節(jié)點,將其移動到鏈表頭部,并返回結果,否則返回空。
{ linkLine: LinkLine map: Map size: Number set(key, value) get(key) }
4.6 代碼實現(xiàn)
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 } } }
到此這篇關于JavaScript手寫LRU算法的示例代碼的文章就介紹到這了,更多相關JavaScript LRU算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
解析為什么axios會有params和data兩個參數(shù)
本文給大家分享為什么axios會有params和data兩個參數(shù),先來回顧一下axios的基本使用,怎么發(fā)送一個請求,本文結合實例代碼給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧2023-10-10JavaScript 關鍵字屏蔽實現(xiàn)函數(shù)
JavaScript屏蔽關鍵字,大概的思路就是去用javascript去替換已有的文本,達到替換的目的2009-08-08弱類型語言javascript開發(fā)中的一些坑實例小結【變量、函數(shù)、數(shù)組、對象、作用域等】
這篇文章主要介紹了弱類型語言javascript開發(fā)中的一些坑,結合實例形式總結分析了javascript開發(fā)中關于變量、函數(shù)、數(shù)組、對象、作用域等相關知識點常見易錯問題,需要的朋友可以參考下2019-08-08