JavaScript雙向鏈表實現(xiàn)LRU緩存算法的示例代碼
目標
請你設(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 。如果插入操作導致關(guān)鍵字數(shù)量超過 capacity ，則應該 逐出 最久未使用的關(guān)鍵字。 函數(shù) get 和 put 必須以 O(1) 的平均時間復雜度運行。
什么是LRU
LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間 t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。
簡介
最近最少使用算法（LRU）是大部分操作系統(tǒng)為最大化頁面命中率而廣泛采用的一種頁面置換算法。該算法的思路是，發(fā)生缺頁中斷時，選擇未使用時間最長的頁面置換出去。 從程序運行的原理來看，最近最少使用算法是比較接近理想的一種頁面置換算法，這種算法既充分利用了內(nèi)存中頁面調(diào)用的歷史信息，又正確反映了程序的局部問題。利用 LRU 算法對上例進行頁面置換的結(jié)果如圖1所示。當進程第一次對頁面 2 進行訪問時，由于頁面 7 是最近最久未被訪問的，故將它置換出去。當進程第一次對頁面 3進行訪問時，第 1 頁成為最近最久未使用的頁，將它換出。由圖1可以看出，前 5 個時間的圖像與最佳置換算法時的相同，但這并非是必然的結(jié)果。因為，最佳置換算法是從“向后看”的觀點出發(fā)的，即它是依據(jù)以后各頁的使用情況；而 LRU 算法則是“向前看”的，即根據(jù)各頁以前的使用情況來判斷，而頁面過去和未來的走向之間并無必然的聯(lián)系。
硬件支持
LRU 置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進程在內(nèi)存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：寄存器或棧。
寄存器
為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為
R = Rn-1 Rn-2 Rn-3 … R2 R1 R0
圖 2 某進程具有 8 個頁面時的 LRU 訪問情況
當進程訪問某物理塊時，要將相應寄存器的 R n -1 位置成 1。此時，定時信號將每隔一定時間(例如 100 ms)將寄存器右移一位。 如果我們把 n 位寄存器的數(shù)看做是一個整數(shù)， 那么，具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。圖2示出了某進程在內(nèi)存中具有 8 個頁面，為每個內(nèi)存頁面配置一個 8 位寄存器時的 LRU 訪問情況。這里，把 8 個內(nèi)存頁面的序號分別定為 1～8。由圖可以看出，第 3 個內(nèi)存頁面的 R 值最小，當發(fā)生缺頁時，首先將它置換出去。
棧
圖 3 用棧保存當前使用頁面時棧的變化情況
可利用一個特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進程所訪問的頁面的頁面號序列為：
4，7，0，7，1，0，1，2，1，2，6
隨著進程的訪問， 棧中頁面號的變化情況如圖 3 所示。 在訪問頁面 6 時發(fā)生了缺頁，此時頁面 4 是最近最久未被訪問的頁，應將它置換出去。
代碼實現(xiàn)
思路
Map 使用一個Map來保存當前所有節(jié)點的信息，鍵為key，值為鏈表中的具體節(jié)點。
鏈表
使用一個雙向鏈表來記錄當前節(jié)點的順序。
鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu)
保存插入節(jié)點信息，pre指向上一個節(jié)點，next指向下一個節(jié)點。
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};鏈表數(shù)據(jù)結(jié)構(gòu)
保存頭結(jié)點head和尾結(jié)點tail。
const linkLine = function () {
let head = new linkLineNode("head", "head");
let tail = new linkLineNode("tail", "tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
};鏈表頭添加
將節(jié)點插入到頭結(jié)點后面，修改頭結(jié)點的next指向以及原本頭結(jié)點的next節(jié)點的pre指向。
linkLine.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
};鏈表刪除指點節(jié)點
重新指向節(jié)點前后節(jié)點的next和pre指向。
linkLine.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};刪除并返回鏈表的最后一個節(jié)點（非tail）
取到鏈表的最后一個節(jié)點（非tail節(jié)點），刪除該節(jié)點并返回節(jié)點信息。
linkLine.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
};打印鏈表信息
將鏈表的信息按順序打印出來，入?yún)樾枰蛴〉膶傩浴?/p>
linkLine.prototype.myConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if (res != "") res += "-->";
res += h[key];
h = h.next;
}
console.log(res);
};LRUCache數(shù)據(jù)結(jié)構(gòu)
capacity保存最大容量，kvMap保存節(jié)點信息，linkLine為節(jié)點的順序鏈表。
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkLine = new linkLine();
};get
如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，并重置節(jié)點鏈表順序，將該節(jié)點移到頭結(jié)點之后，否則返回 -1 。
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
this.linkLine.delete(node);
this.linkLine.append(node);
return node.val;
}
return -1;
};put
如果關(guān)鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ，并重置節(jié)點鏈表順序，將該節(jié)點移到頭結(jié)點之后；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關(guān)鍵字數(shù)量超過 capacity ， 則應該 逐出 最久未使用的關(guān)鍵字。
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkLine.delete(node);
this.linkLine.append(node);
} else {
let node = new linkLineNode(key, value);
if (this.capacity == this.kvMap.size) {
let nodeP = this.linkLine.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkLine.append(node);
}
};完整代碼
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};
const linkLine = function () {
let head = new linkLineNode("head", "head");
let tail = new linkLineNode("tail", "tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
};
linkLine.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
};
linkLine.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};
linkLine.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
};
linkLine.prototype.myConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if (res != "") res += "-->";
res += h[key];
h = h.next;
}
console.log(res);
};
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkLine = new linkLine();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
this.linkLine.delete(node);
this.linkLine.append(node);
return node.val;
}
return -1;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkLine.delete(node);
this.linkLine.append(node);
} else {
let node = new linkLineNode(key, value);
if (this.capacity == this.kvMap.size) {
let nodeP = this.linkLine.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkLine.append(node);
}
};測試
var obj = new LRUCache(2); obj.put(1, 1); obj.put(2, 2); console.log(obj.get(1)); //---> 1 obj.put(3, 3); console.log(obj.get(2));//---> -1 obj.put(4, 4); console.log(obj.get(1));//---> -1 console.log(obj.get(3));//---> 3 console.log(obj.get(4));//---> 4
到此這篇關(guān)于JavaScript雙向鏈表實現(xiàn)LRU緩存算法的示例代碼的文章就介紹到這了,更多相關(guān)JavaScript LRU緩存算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
最近一直在使用echarts,當然也被其中的各種屬性整的有些頭大,這篇文章主要給大家介紹了關(guān)于ECharts鼠標事件處理的相關(guān)資料,需要的朋友可以參考下2021-06-06
這篇文章主要介紹了使用webpack和rollup打包組件庫的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要介紹了javascript for循環(huán)性能測試,結(jié)合實例形式分析了javascript使用for循環(huán)遍歷數(shù)組的三種常用方法及對應的時間消耗,總結(jié)javascript使用for循環(huán)遍歷數(shù)組的相關(guān)操作技巧,需要的朋友可以參考下2019-08-08
直角坐標系的設(shè)置指的是網(wǎng)格,坐標軸和區(qū)域縮放的配置,下面這篇文章主要給大家介紹了關(guān)于Echarts直角坐標系x軸y軸屬性設(shè)置的相關(guān)資料,需要的朋友可以參考下2022-11-11
js表數(shù)據(jù)排序 sort table data
對于表格的排序，是很不錯的一個功能，方便用戶快速的分析一些數(shù)據(jù)。2009-02-02
這篇文章主要為大家詳細介紹了微信小程序?qū)崿F(xiàn)本地分頁加載，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
最近在做算法題時,遇到需要創(chuàng)建二維數(shù)組并進行初始化的情況,剛開始我使用的是 new Array(n).fill(new Array(n).fill('.')) 進行二維數(shù)組的初始化,但無論怎樣我都通不過測試用例,所以本文就給大家詳細的介紹了如何解決這類問題以及將js中的fill（方法重學一下2023-09-09
本篇文章主要介紹了js圖片加載效果實例代碼（延遲加載+瀑布流加載），非常具有實用價值，需要的朋友可以參考下2017-05-05
在 JavaScript 中保留小數(shù)點后兩位的方法
在 JavaScript 中,有多種方法可以保留小數(shù)點后兩位,本文給大家分享比較常用的方法,文末給大家介紹了實現(xiàn)數(shù)據(jù)格式化保留兩位小數(shù)的多種方法,感興趣的朋友一起看看吧2023-10-10
js輸入中文效果...2006-09-09