JavaScript雙向鏈表實(shí)現(xiàn)LFU緩存算法
什么是LFU
LFU(Least Frequently Used),最近最少使用策略,也就是說(shuō)在一段時(shí)間內(nèi),數(shù)據(jù)被使用頻次最少的,優(yōu)先被淘汰。
它是一種用于管理計(jì)算機(jī)內(nèi)存的緩存算法,采用LFU算法的最簡(jiǎn)單方法是為每個(gè)加載到緩存的塊分配一個(gè)計(jì)數(shù)器。每次引用該塊時(shí),計(jì)數(shù)器將增加一。當(dāng)緩存達(dá)到容量并有一個(gè)新的內(nèi)存塊等待插入時(shí),系統(tǒng)將搜索計(jì)數(shù)器最低的塊并將其從緩存中刪除。
描述
請(qǐng)你為 最不經(jīng)常使用(LFU)緩存算法設(shè)計(jì)并實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。
實(shí)現(xiàn) LFUCache 類(lèi):
LFUCache(int capacity) - 用數(shù)據(jù)結(jié)構(gòu)的容量 capacity 初始化對(duì)象
int get(int key) - 如果鍵 key 存在于緩存中,則獲取鍵的值,否則返回 -1 。
void put(int key, int value) - 如果鍵 key 已存在,則變更其值;如果鍵不存在,請(qǐng)插入鍵值對(duì)。
當(dāng)緩存達(dá)到其容量 capacity 時(shí),則應(yīng)該在插入新項(xiàng)之前,移除最不經(jīng)常使用的項(xiàng)。
在此問(wèn)題中,當(dāng)存在平局(即兩個(gè)或更多個(gè)鍵具有相同使用頻率)時(shí),應(yīng)該去除 最近最久未使用 的鍵。
為了確定最不常使用的鍵,可以為緩存中的每個(gè)鍵維護(hù)一個(gè) 使用計(jì)數(shù)器 。使用計(jì)數(shù)最小的鍵是最久未使用的鍵。
當(dāng)一個(gè)鍵首次插入到緩存中時(shí),它的使用計(jì)數(shù)器被設(shè)置為 1 (由于 put 操作)。對(duì)緩存中的鍵執(zhí)行 get 或 put 操作,使用計(jì)數(shù)器的值將會(huì)遞增。
函數(shù) get 和 put 必須以 O(1) 的平均時(shí)間復(fù)雜度運(yùn)行。
解題思路
1、構(gòu)造節(jié)點(diǎn)結(jié)構(gòu)體
保存對(duì)應(yīng)的數(shù)據(jù)信息
const LFUNode = function ( ? key = "", ? val = "", ? freq = 0, ? pre = null, ? next = null ) { ? this.key = key; ? this.val = val; ? this.freq = freq; ? this.pre = pre; ? this.next = next; };
2、構(gòu)造雙向鏈表
構(gòu)造帶有頭尾節(jié)點(diǎn)的雙向鏈表,head和tail為哨兵節(jié)點(diǎn),不保存信息,僅用于標(biāo)記頭尾。
const LFULinkLine = function (node) { ? let head = new LFUNode("head"); ? let tail = new LFUNode("tail"); ? head.next = node; ? tail.pre = node; ? node.pre = head; ? node.next = tail; ? this.head = head; ? this.tail = tail; };
3、編寫(xiě)鏈表頭添加節(jié)點(diǎn)方法
將節(jié)點(diǎn)插入到鏈表的頭結(jié)點(diǎn)之后,其他節(jié)點(diǎn)往后移。
LFULinkLine.prototype.addNode = function (node) { ? this.head.next.pre = node; ? node.pre = this.head; ? node.next = this.head.next; ? this.head.next = node; };
4、編寫(xiě)刪除節(jié)點(diǎn)方法
將節(jié)點(diǎn)從鏈表中刪除。
LFULinkLine.prototype.removeNode = function (node) { ? node.pre.next = node.next; ? node.next.pre = node.pre; };
5、構(gòu)造LRU緩存結(jié)構(gòu)體
構(gòu)造LRU緩存結(jié)構(gòu)體,具體信息如下代碼,capacity用于保存最大緩存數(shù),即該類(lèi)的容量;num保存當(dāng)前存儲(chǔ)的數(shù)據(jù)量,用于判別是否超出最大容量;minFreq保存當(dāng)前存儲(chǔ)的數(shù)據(jù)中的最小頻率,刪除的時(shí)候需要優(yōu)先刪除頻率最小的;kvMap保存節(jié)點(diǎn)詳細(xì)信息,索引為節(jié)點(diǎn)的key值,查詢(xún)可以直接從這里查出信息;freqMap保存對(duì)應(yīng)頻率的鏈表信息,索引為節(jié)點(diǎn)的freq(頻率),刪除的時(shí)候可以快速?gòu)倪@里獲取需要?jiǎng)h除節(jié)點(diǎn)的信息。
/** ?* @param {number} capacity ?*/ var LFUCache = function (capacity) { ? this.capacity = capacity;//最大緩存 ? this.num = 0;//當(dāng)前數(shù)目 ? this.minFreq = 0;//當(dāng)前最小頻率 ? this.kvMap = new Map();//保存節(jié)點(diǎn)信息 ? this.freqMap = new Map();//保存對(duì)應(yīng)頻率的鏈表信息 };
6、編寫(xiě)get方法
get主要有以下兩種情況:
(1)節(jié)點(diǎn)存在
- 通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn)
- 將節(jié)點(diǎn)從freqMap中刪除
- 判斷是否需要修改minFreq
- 修改節(jié)點(diǎn)的freq
- 重新將節(jié)點(diǎn)插入freqMap
- 返回節(jié)點(diǎn)的value
(2)節(jié)點(diǎn)不存在
容量capacity為0或者kvMap中沒(méi)有該節(jié)點(diǎn)信息,直接返回-1即可。
/** ?* @param {number} key ?* @return {number} ?*/ LFUCache.prototype.get = function (key) { ? if (this.capacity === 0) return -1; ? if (!this.kvMap.has(key)) return -1; ? //通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn) ? let node = this.kvMap.get(key); ? let linkLine = this.freqMap.get(node.freq); ? //將節(jié)點(diǎn)從freqMap中刪除 ? linkLine.removeNode(node); ? //判斷是否需要修改minFreq ? //清空了 ? if (linkLine.head.next === linkLine.tail) { ? ? this.freqMap.delete(node.freq); ? ? if (this.minFreq == node.freq) this.minFreq++; ? } ? //修改節(jié)點(diǎn)的freq ? node.freq++; ? //重新將節(jié)點(diǎn)插入freqMap ? if (this.freqMap.has(node.freq)) { ? ? linkLine = this.freqMap.get(node.freq); ? ? linkLine.addNode(node); ? } else { ? ? this.freqMap.set(node.freq, new LFULinkLine(node)); ? } ? //返回節(jié)點(diǎn)的value ? return node.val; };
7、編寫(xiě)put方法
put操作主要有以下兩種情況:
(1)更新
- 通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn)
- 將節(jié)點(diǎn)從freqMap中刪除
- 判斷是否需要修改minFreq
- 更新節(jié)點(diǎn)信息
- 重新將節(jié)點(diǎn)插入freqMap
(2)存入
存入情況下又有兩種情況:
容量已滿(mǎn)
- 通過(guò)minFreq找到需要?jiǎng)h除的節(jié)點(diǎn)
- 將節(jié)點(diǎn)從freqMap中刪除
- 判斷是否需要修改minFreq
- 將新節(jié)點(diǎn)插入freqMap
- 更新minFreq
容量未滿(mǎn)
- 修改num
- 將新節(jié)點(diǎn)插入freqMap
- 更新minFreq
/** ?* @param {number} key ?* @param {number} value ?* @return {void} ?*/ LFUCache.prototype.put = function (key, value) { ? if (this.capacity === 0) return; ? if (this.kvMap.has(key)) { ? ? //更新 ? ? //通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn) ? ? let node = this.kvMap.get(key); ? ? //將節(jié)點(diǎn)從freqMap中刪除 ? ? let linkLine = this.freqMap.get(node.freq); ? ? linkLine.removeNode(node); ? ? //判斷是否需要修改minFreq ? ? if (linkLine.head.next === linkLine.tail) { ? ? ? if (this.minFreq == node.freq) this.minFreq++; ? ? ? this.freqMap.delete(node.freq); ? ? } ? ? //更新節(jié)點(diǎn)信息 ? ? node.val = value; ? ? node.freq++; ? ? //重新將節(jié)點(diǎn)插入freqMap ? ? if (this.freqMap.has(node.freq)) { ? ? ? linkLine = this.freqMap.get(node.freq); ? ? ? linkLine.addNode(node); ? ? } else { ? ? ? linkLine = new LFULinkLine(node); ? ? ? this.freqMap.set(node.freq, linkLine); ? ? } ? } else {//存入 ? ? if (this.capacity == this.num) {//存滿(mǎn) ? ? ? //通過(guò)minFreq找到需要?jiǎng)h除的節(jié)點(diǎn) ? ? ? let freq = this.minFreq; ? ? ? let linkLine = this.freqMap.get(freq); ? ? ? let node = linkLine.tail.pre; ? ? ? //將節(jié)點(diǎn)從freqMap中刪除 ? ? ? ? linkLine.removeNode(node); ? ? ? this.kvMap.delete(node.key); ? ? ? //判斷是否需要修改minFreq ? ? ? if (linkLine.head.next === linkLine.tail) { ? ? ? ? this.freqMap.delete(node.freq); ? ? ? } ? ? } else { ? ? ? //修改num ? ? ? this.num++; ? ? } ? ? //將新節(jié)點(diǎn)插入freqMap ? ? let node = new LFUNode(key, value, 0); ? ? this.kvMap.set(key, node); ? ? if (this.freqMap.has(0)) { ? ? ? let linkLine = this.freqMap.get(0); ? ? ? linkLine.addNode(node); ? ? } else { ? ? ? let linkLine = new LFULinkLine(node); ? ? ? this.freqMap.set(0, linkLine); ? ? } ? ? //更新minFreq ? ? this.minFreq = 0; ? } };
代碼
const LFUNode = function ( ? key = "", ? val = "", ? freq = 0, ? pre = null, ? next = null ) { ? this.key = key; ? this.val = val; ? this.freq = freq; ? this.pre = pre; ? this.next = next; }; const LFULinkLine = function (node) { ? let head = new LFUNode("head"); ? let tail = new LFUNode("tail"); ? head.next = node; ? tail.pre = node; ? node.pre = head; ? node.next = tail; ? this.head = head; ? this.tail = tail; }; LFULinkLine.prototype.addNode = function (node) { ? this.head.next.pre = node; ? node.pre = this.head; ? node.next = this.head.next; ? this.head.next = node; }; LFULinkLine.prototype.removeNode = function (node) { ? node.pre.next = node.next; ? node.next.pre = node.pre; }; /** ?* @param {number} capacity ?*/ var LFUCache = function (capacity) { ? this.capacity = capacity; ? this.num = 0; ? this.minFreq = 0; ? this.kvMap = new Map(); ? this.freqMap = new Map(); }; /** ?* @param {number} key ?* @return {number} ?*/ LFUCache.prototype.get = function (key) { ? if (this.capacity === 0) return -1; ? if (!this.kvMap.has(key)) return -1; ? let node = this.kvMap.get(key); ? let linkLine = this.freqMap.get(node.freq); ? linkLine.removeNode(node); ? //清空了 ? if (linkLine.head.next === linkLine.tail) { ? ? this.freqMap.delete(node.freq); ? ? if (this.minFreq == node.freq) this.minFreq++; ? } ? node.freq++; ? if (this.freqMap.has(node.freq)) { ? ? linkLine = this.freqMap.get(node.freq); ? ? linkLine.addNode(node); ? } else { ? ? this.freqMap.set(node.freq, new LFULinkLine(node)); ? } ? return node.val; }; /** ?* @param {number} key ?* @param {number} value ?* @return {void} ?*/ LFUCache.prototype.put = function (key, value) { ? if (this.capacity === 0) return; ? if (this.kvMap.has(key)) { ? ? //更新 ? ? let node = this.kvMap.get(key); ? ? node.val = value; ? ? let linkLine = this.freqMap.get(node.freq); ? ? linkLine.removeNode(node); ? ? if (linkLine.head.next === linkLine.tail) { ? ? ? if (this.minFreq == node.freq) this.minFreq++; ? ? ? this.freqMap.delete(node.freq); ? ? } ? ? node.freq++; ? ? if (this.freqMap.has(node.freq)) { ? ? ? linkLine = this.freqMap.get(node.freq); ? ? ? linkLine.addNode(node); ? ? } else { ? ? ? linkLine = new LFULinkLine(node); ? ? ? this.freqMap.set(node.freq, linkLine); ? ? } ? } else { ? ? //存入 ? ? if (this.capacity == this.num) { ? ? ? //存滿(mǎn) ? ? ? let freq = this.minFreq; ? ? ? let linkLine = this.freqMap.get(freq); ? ? ? let node = linkLine.tail.pre; ? ? ? linkLine.removeNode(node); ? ? ? this.kvMap.delete(node.key); ? ? ? if (linkLine.head.next === linkLine.tail) { ? ? ? ? this.freqMap.delete(node.freq); ? ? ? } ? ? } else { ? ? ? this.num++; ? ? } ? ? let node = new LFUNode(key, value, 0); ? ? this.kvMap.set(key, node); ? ? if (this.freqMap.has(0)) { ? ? ? let linkLine = this.freqMap.get(0); ? ? ? linkLine.addNode(node); ? ? } else { ? ? ? let linkLine = new LFULinkLine(node); ? ? ? this.freqMap.set(0, linkLine); ? ? } ? ? this.minFreq = 0; ? } }; /** ?* Your LFUCache object will be instantiated and called as such: ?* var obj = new LFUCache(capacity) ?* var param_1 = obj.get(key) ?* obj.put(key,value) ?*/
到此這篇關(guān)于JavaScript雙向鏈表實(shí)現(xiàn)LFU緩存算法的文章就介紹到這了,更多相關(guān)JavaScript LFU緩存算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
如何判斷Javascript對(duì)象是否存在的簡(jiǎn)單實(shí)例
下面小編就為大家?guī)?lái)一篇如何判斷Javascript對(duì)象是否存在的簡(jiǎn)單實(shí)例。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-05-05詳解javascript腳本何時(shí)會(huì)被執(zhí)行
這篇文章主要介紹了詳解javascript腳本何時(shí)會(huì)被執(zhí)行,幫助大家更好的理解和使用JavaScript,感興趣的朋友可以了解下2021-02-02如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列
這篇文章主要介紹了如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列。棧和隊(duì)列是web開(kāi)發(fā)中最常用的兩種數(shù)據(jù)結(jié)構(gòu)。絕大多數(shù)用戶(hù),甚至包括web開(kāi)發(fā)人員,都不知道這個(gè)驚人的事實(shí)。,需要的朋友可以參考下2019-06-06JavaScript實(shí)現(xiàn)彩虹文字效果的方法
這篇文章主要介紹了JavaScript實(shí)現(xiàn)彩虹文字效果的方法,涉及javascript操作文字樣式的技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-04-04利用CSS、JavaScript及Ajax實(shí)現(xiàn)圖片預(yù)加載的三大方法
本文主要介紹了利用CSS、JavaScript及Ajax實(shí)現(xiàn)圖片預(yù)加載的三大方法。具有很好的參考價(jià)值,下面跟著小編一起來(lái)看下吧2017-01-01