JavaScript雙向鏈表實現(xiàn)LFU緩存算法
什么是LFU
LFU(Least Frequently Used),最近最少使用策略,也就是說在一段時間內,數(shù)據被使用頻次最少的,優(yōu)先被淘汰。
它是一種用于管理計算機內存的緩存算法,采用LFU算法的最簡單方法是為每個加載到緩存的塊分配一個計數(shù)器。每次引用該塊時,計數(shù)器將增加一。當緩存達到容量并有一個新的內存塊等待插入時,系統(tǒng)將搜索計數(shù)器最低的塊并將其從緩存中刪除。
描述
請你為 最不經常使用(LFU)緩存算法設計并實現(xiàn)數(shù)據結構。
實現(xiàn) LFUCache 類:
LFUCache(int capacity) - 用數(shù)據結構的容量 capacity 初始化對象
int get(int key) - 如果鍵 key 存在于緩存中,則獲取鍵的值,否則返回 -1 。
void put(int key, int value) - 如果鍵 key 已存在,則變更其值;如果鍵不存在,請插入鍵值對。
當緩存達到其容量 capacity 時,則應該在插入新項之前,移除最不經常使用的項。
在此問題中,當存在平局(即兩個或更多個鍵具有相同使用頻率)時,應該去除 最近最久未使用 的鍵。
為了確定最不常使用的鍵,可以為緩存中的每個鍵維護一個 使用計數(shù)器 。使用計數(shù)最小的鍵是最久未使用的鍵。
當一個鍵首次插入到緩存中時,它的使用計數(shù)器被設置為 1 (由于 put 操作)。對緩存中的鍵執(zhí)行 get 或 put 操作,使用計數(shù)器的值將會遞增。
函數(shù) get 和 put 必須以 O(1) 的平均時間復雜度運行。
解題思路
1、構造節(jié)點結構體
保存對應的數(shù)據信息
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、構造雙向鏈表
構造帶有頭尾節(jié)點的雙向鏈表,head和tail為哨兵節(jié)點,不保存信息,僅用于標記頭尾。
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、編寫鏈表頭添加節(jié)點方法
將節(jié)點插入到鏈表的頭結點之后,其他節(jié)點往后移。
LFULinkLine.prototype.addNode = function (node) { ? this.head.next.pre = node; ? node.pre = this.head; ? node.next = this.head.next; ? this.head.next = node; };
4、編寫刪除節(jié)點方法
將節(jié)點從鏈表中刪除。
LFULinkLine.prototype.removeNode = function (node) { ? node.pre.next = node.next; ? node.next.pre = node.pre; };
5、構造LRU緩存結構體
構造LRU緩存結構體,具體信息如下代碼,capacity用于保存最大緩存數(shù),即該類的容量;num保存當前存儲的數(shù)據量,用于判別是否超出最大容量;minFreq保存當前存儲的數(shù)據中的最小頻率,刪除的時候需要優(yōu)先刪除頻率最小的;kvMap保存節(jié)點詳細信息,索引為節(jié)點的key值,查詢可以直接從這里查出信息;freqMap保存對應頻率的鏈表信息,索引為節(jié)點的freq(頻率),刪除的時候可以快速從這里獲取需要刪除節(jié)點的信息。
/** ?* @param {number} capacity ?*/ var LFUCache = function (capacity) { ? this.capacity = capacity;//最大緩存 ? this.num = 0;//當前數(shù)目 ? this.minFreq = 0;//當前最小頻率 ? this.kvMap = new Map();//保存節(jié)點信息 ? this.freqMap = new Map();//保存對應頻率的鏈表信息 };
6、編寫get方法
get主要有以下兩種情況:
(1)節(jié)點存在
- 通過kvMap獲取到對應節(jié)點
- 將節(jié)點從freqMap中刪除
- 判斷是否需要修改minFreq
- 修改節(jié)點的freq
- 重新將節(jié)點插入freqMap
- 返回節(jié)點的value
(2)節(jié)點不存在
容量capacity為0或者kvMap中沒有該節(jié)點信息,直接返回-1即可。
/** ?* @param {number} key ?* @return {number} ?*/ LFUCache.prototype.get = function (key) { ? if (this.capacity === 0) return -1; ? if (!this.kvMap.has(key)) return -1; ? //通過kvMap獲取到對應節(jié)點 ? let node = this.kvMap.get(key); ? let linkLine = this.freqMap.get(node.freq); ? //將節(jié)點從freqMap中刪除 ? linkLine.removeNode(node); ? //判斷是否需要修改minFreq ? //清空了 ? if (linkLine.head.next === linkLine.tail) { ? ? this.freqMap.delete(node.freq); ? ? if (this.minFreq == node.freq) this.minFreq++; ? } ? //修改節(jié)點的freq ? node.freq++; ? //重新將節(jié)點插入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é)點的value ? return node.val; };
7、編寫put方法
put操作主要有以下兩種情況:
(1)更新
- 通過kvMap獲取到對應節(jié)點
- 將節(jié)點從freqMap中刪除
- 判斷是否需要修改minFreq
- 更新節(jié)點信息
- 重新將節(jié)點插入freqMap
(2)存入
存入情況下又有兩種情況:
容量已滿
- 通過minFreq找到需要刪除的節(jié)點
- 將節(jié)點從freqMap中刪除
- 判斷是否需要修改minFreq
- 將新節(jié)點插入freqMap
- 更新minFreq
容量未滿
- 修改num
- 將新節(jié)點插入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)) { ? ? //更新 ? ? //通過kvMap獲取到對應節(jié)點 ? ? let node = this.kvMap.get(key); ? ? //將節(jié)點從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é)點信息 ? ? node.val = value; ? ? node.freq++; ? ? //重新將節(jié)點插入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) {//存滿 ? ? ? //通過minFreq找到需要刪除的節(jié)點 ? ? ? let freq = this.minFreq; ? ? ? let linkLine = this.freqMap.get(freq); ? ? ? let node = linkLine.tail.pre; ? ? ? //將節(jié)點從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é)點插入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) { ? ? ? //存滿 ? ? ? 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) ?*/
到此這篇關于JavaScript雙向鏈表實現(xiàn)LFU緩存算法的文章就介紹到這了,更多相關JavaScript LFU緩存算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
利用CSS、JavaScript及Ajax實現(xiàn)圖片預加載的三大方法
本文主要介紹了利用CSS、JavaScript及Ajax實現(xiàn)圖片預加載的三大方法。具有很好的參考價值,下面跟著小編一起來看下吧2017-01-01