JavaScript實現(xiàn)LRU算法的示例詳解
不知道屏幕前的朋友們,有沒有和我一樣,覺得LRU算法原理很容易理解,實現(xiàn)起來卻很復(fù)雜。
明明一個map就能解決,標(biāo)準答案卻總要使用雙向鏈表。
實現(xiàn)思路很很容易理解,但是下筆寫代碼總是磕磕絆絆。
但是這個算法在前端使用場景很多,面試經(jīng)常問,正巧我遇到了這個問題,因此抓住機會和大家記錄分享一下
LRU簡介
least Recently Used 最近最少使用,用于操作系統(tǒng)內(nèi)存管理,在前端開發(fā)中常用于優(yōu)化頁面性能和資源利用率。
直接翻譯就是“最不經(jīng)常使用的數(shù)據(jù),重要性是最低的,應(yīng)該優(yōu)先刪除”
以下是在前端中使用LRU算法的幾個應(yīng)用場景:
前端路由:在單頁應(yīng)用(SPA)中,通過將路由信息保存在緩存中,可以避免每次訪問頁面時都需要重新加載數(shù)據(jù),從而提高頁面響應(yīng)速度和用戶體驗。
圖片懶加載:對于大型圖片庫,可以使用LRU算法對已加載的圖片進行緩存,當(dāng)一個新圖片需要被加載時,可以先檢查該圖片是否已經(jīng)在緩存中存在,如果存在則直接從緩存中獲取,否則從服務(wù)器加載。
數(shù)據(jù)緩存:對于需要頻繁讀取的數(shù)據(jù)或者需要復(fù)雜計算才能得出結(jié)果的數(shù)據(jù),可以使用LRU算法對其進行緩存,以減少重復(fù)計算的時間。
字體應(yīng)用:對于網(wǎng)站上使用的字體文件,可以使用LRU算法將最常用的字體文件存儲在緩存中,從而加快頁面渲染速度和節(jié)省網(wǎng)絡(luò)流量。
總之,LRU算法可用于提升前端應(yīng)用的性能和用戶體驗,但需要根據(jù)具體的應(yīng)用場景選擇合適的算法并進行合理的配置。
如何實現(xiàn)
那么如何實現(xiàn)一個LRU 算法呢?我們一起看看leetcode 146這道題目
設(shè)計一個LRU類,實現(xiàn)get put 方法
題目簡單描述:
請你設(shè)計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。
實現(xiàn) LRUCache 類:
- LRUCache(int capacity) 以 正整數(shù) 作為容量 capacity 初始化 LRU 緩存
- int get(int key) 如果關(guān)鍵字 key 存在于緩存中,則返回關(guān)鍵字的值,否則返回 -1 。
- void put(int key, int value) 如果關(guān)鍵字 key 已經(jīng)存在,則變更其數(shù)據(jù)值 value ;如果不存在,則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字數(shù)量超過 capacity ,則應(yīng)該 逐出 最久未使用的關(guān)鍵字。
實現(xiàn)思路
我們使用一個map 來緩存數(shù)據(jù)。
當(dāng)獲取數(shù)據(jù)key 時,優(yōu)先判斷是否存在于map,如果在我們先拿到這個值存為temp,然后從map中刪除,重新set進map中
當(dāng)插入數(shù)據(jù)時,優(yōu)先判斷是否存在于map,如果不存在,直接set,如果存在,刪除后哦嗎,重新set
這樣我們保證最近使用的都在map 的最下層,當(dāng)內(nèi)存超出時,直接刪除map 頂層元素即可
this.map.delete(this.map.keys().next().value)
var LRUCache = function(capacity) { this.capacity = capacity this.map = new Map() } LRUCache.prototype.get = function(key) { if(this.map.has(key)) { let temp = this.map.get(key) this.map.delete(key) this.map.set(key,temp) return temp } else { return -1 } } LRUCache.prototype.put = function(key, value) { if(this.map.has(key)) { this.map.delete(key) } this.map.set(key,value) if(this.map.size > this.capacity) { this.map.delete(this.map.keys().next().value) } }
缺陷
雖然該實現(xiàn)使用了 Map 對象,但是在最壞情況下,如果哈希函數(shù)分布不均勻,可能會導(dǎo)致哈希沖突,使得某些操作的時間復(fù)雜度變?yōu)?O(n)。因此,在實際應(yīng)用中,如果需要高效地處理大規(guī)模數(shù)據(jù),建議使用雙向鏈表或其他更高效的數(shù)據(jù)結(jié)構(gòu)。
假設(shè)有一個哈希表,大小為 5,使用的哈希函數(shù)為 key % 5。現(xiàn)在插入以下 6 個鍵值對:
{key: 1, value: 'a'} {key: 2, value: 'b'} {key: 3, value: 'c'} {key: 4, value: 'd'} {key: 6, value: 'e'} {key: 11, value: 'f'}
根據(jù)給定的哈希函數(shù) key % 5,可以將每個鍵映射到哈希表中的一個桶。具體來說,將鍵除以 5 并取余數(shù),以得到它應(yīng)該插入的桶的索引。
使用這個哈希函數(shù),將上述六個鍵值對插入哈希表中,得到以下結(jié)果:
在索引 1 的桶中插入 {key: 1, value: 'a'}
在索引 2 的桶中插入 {key: 2, value: 'b'}
'在索引 3 的桶中插入 {key: 3, value: 'c'}
在索引 4 的桶中插入 {key: 4, value: 'd'}
在索引 1 的桶中插入 {key: 6, value: 'e'}
在索引 1 的桶中插入 {key: 11, value: 'f'}
注意,在將鍵為 6 和 11 的鍵值對插入哈希表時,它們都被映射到索引 1 的桶中。這是因為它們分別與 1 余數(shù)相同。
當(dāng)出現(xiàn)哈希沖突時,即多個鍵被映射到同一桶時
這種情況下,在操作時需要遍歷整個桶來查找指定的鍵值對,因此操作的時間復(fù)雜度變?yōu)?O(n)。
雙向鏈表+哈希表
那么如何達到O(1)的時間復(fù)雜度呢?
那肯定選用 map 查詢。修改,刪除也要盡量 O(1) 完成。搜尋常見的數(shù)據(jù)結(jié)構(gòu),鏈表,棧,隊列,樹,圖。樹和圖排除,棧和隊列無法任意查詢中間的元素,也排除。所以選用鏈表來實現(xiàn)。但是如果選用單鏈表,刪除這個結(jié)點,需要 O(n) 遍歷一遍找到前驅(qū)結(jié)點。所以選用雙向鏈表,在刪除的時候也能 O(1) 完成。
核心就是:最近最多使用的節(jié)點永遠在鏈表結(jié)尾,最近最少使用的節(jié)點在鏈表開頭。
雙向鏈表
雙向鏈表的結(jié)構(gòu)
value: 存儲的值
prev: 指向前一個元素的指針
next: 指向下一個元素的指針
Head和Tail是虛擬的頭部和尾部節(jié)點,這是為了方便找到鏈表的首末設(shè)定的
┌──────>┐ ┌───────>┐ ┌───────>┐
head • (x|"three"|•) (•|"two"|•) (•|"one"|x) • tail
└<────────┘ └<───────┘ └<─────┘
實現(xiàn)思路
1.使用一個Map 對象來存儲鍵值對
2.使用一個雙向鏈表維護鍵值對的順序
3.抽離出一個addToTaill 方法(將節(jié)點插入末尾)抽離出一個remove 方法(刪除節(jié)點)
4.當(dāng)執(zhí)行put 操作時,判斷節(jié)點是否在map中
- 如果存在,獲取當(dāng)前節(jié)點值,在雙向鏈表中remove刪除改節(jié)點,重新調(diào)用 addToTail 添加到末尾
- 如果不存在,建立一個雙向鏈表節(jié)點,調(diào)用 addToTail 添加到末尾,同時添加進map
- 如果超過容量this.size > this.cap,刪除當(dāng)前head節(jié)點,從map中刪除當(dāng)前key
5.當(dāng)執(zhí)行g(shù)et 操作時,判斷節(jié)點是否在map中
- 如果不存在,返回-1
- 如果存在,獲取當(dāng)前key,value,重新執(zhí)行put 操作
class ListNode { constructor(key, value) { this.key = key; this.val = value; this.prev = null; this.next = null; } } class LRUCache { constructor(capacity = 10) { this.capacity = capacity; // 實際保存的鍵值對數(shù)量 this.size = 0; this.map = {}; //代表最舊的節(jié)點 this.head = null; //代表最新的節(jié)點 this.tail = null; } get(key) { const node = this.map.get(key); if (!node) return -1; let node = this.map[key]; this.put(node.key, node.val); return node.value; } put(key, value) { if(this.map[key]) { let node = this.map[key] node.val = value this.remove(node) this.addTotail(node) } else { let node = new ListNode(key,value) this.addTotail(node) this.map[key] = node this.size++ } if (this.size > this.cap) { let key = this.head.key; this.remove(this.head); delete this.map[key]; this.size--; } } addToTail(node) { if(this.tail) { this.tail.next = node node.prev = this.tail this.tail = node } else { this.tail = node this.head = node } } remove(node) { if(node.prev) { node.prev.next = node.next } else { this.head = this.head.next } if(node.next) { node.next.prev = node.prev } else { this.tail = this.tail.prev } node.prev = node.next = null; } }
以上就是JavaScript實現(xiàn)LRU算法的示例詳解的詳細內(nèi)容,更多關(guān)于JavaScript LRU算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
JavaScript實現(xiàn)更改網(wǎng)頁背景與字體顏色的方法
這篇文章主要介紹了JavaScript實現(xiàn)更改網(wǎng)頁背景與字體顏色的方法,可實現(xiàn)點擊按鈕改變網(wǎng)頁背景色的功能,具有一定參考借鑒價值,需要的朋友可以參考下2015-02-02JavaScript String(字符串)對象的簡單實例(推薦)
下面小編就為大家?guī)硪黄狫avaScript String(字符串)對象的簡單實例(推薦)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2016-08-08web前端開發(fā)中常見的多列布局解決方案整理(一定要看)
多列布局在web前端開發(fā)中也是較為常見的,今天小編給大家介紹這里會提到的多列布局有兩列定寬加一列自適應(yīng)、多列不定寬加一列自適應(yīng)、多列等分三種,感興趣的朋友一起看看吧2017-10-10javascript數(shù)據(jù)結(jié)構(gòu)與算法之檢索算法
查找數(shù)據(jù)有2種方式,順序查找和二分查找。順序查找適用于元素隨機排列的列表。二分查找適用于元素已排序的列表。二分查找效率更高,但是必須是已經(jīng)排好序的列表元素集合2015-04-04利用JS判斷用戶是否上網(wǎng)(連接網(wǎng)絡(luò))
本篇文章主要介紹了利用JS判斷用戶是否上網(wǎng)(連接網(wǎng)絡(luò))。需要的朋友可以過來參考下,希望對大家有所幫助2013-12-12