JavaScript雙向鏈表實現(xiàn)LRU緩存算法的示例代碼
目標
請你設計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結構。 實現(xiàn) LRUCache 類： LRUCache(int capacity) 以 正整數(shù) 作為容量 capacity 初始化 LRU 緩存 int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。 void put(int key, int value) 如果關鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數(shù)量超過 capacity ，則應該 逐出 最久未使用的關鍵字。 函數(shù) get 和 put 必須以 O(1) 的平均時間復雜度運行。
什么是LRU
LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間 t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。
簡介
最近最少使用算法（LRU）是大部分操作系統(tǒng)為最大化頁面命中率而廣泛采用的一種頁面置換算法。該算法的思路是，發(fā)生缺頁中斷時，選擇未使用時間最長的頁面置換出去。 從程序運行的原理來看，最近最少使用算法是比較接近理想的一種頁面置換算法，這種算法既充分利用了內存中頁面調用的歷史信息，又正確反映了程序的局部問題。利用 LRU 算法對上例進行頁面置換的結果如圖1所示。當進程第一次對頁面 2 進行訪問時，由于頁面 7 是最近最久未被訪問的，故將它置換出去。當進程第一次對頁面 3進行訪問時，第 1 頁成為最近最久未使用的頁，將它換出。由圖1可以看出，前 5 個時間的圖像與最佳置換算法時的相同，但這并非是必然的結果。因為，最佳置換算法是從“向后看”的觀點出發(fā)的，即它是依據(jù)以后各頁的使用情況；而 LRU 算法則是“向前看”的，即根據(jù)各頁以前的使用情況來判斷，而頁面過去和未來的走向之間并無必然的聯(lián)系。
硬件支持
LRU 置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：寄存器或棧。
寄存器
為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為
R = Rn-1 Rn-2 Rn-3 … R2 R1 R0
圖 2 某進程具有 8 個頁面時的 LRU 訪問情況
當進程訪問某物理塊時，要將相應寄存器的 R n -1 位置成 1。此時，定時信號將每隔一定時間(例如 100 ms)將寄存器右移一位。 如果我們把 n 位寄存器的數(shù)看做是一個整數(shù)， 那么，具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。圖2示出了某進程在內存中具有 8 個頁面，為每個內存頁面配置一個 8 位寄存器時的 LRU 訪問情況。這里，把 8 個內存頁面的序號分別定為 1～8。由圖可以看出，第 3 個內存頁面的 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é)點信息，pre指向上一個節(jié)點，next指向下一個節(jié)點。
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};鏈表數(shù)據(jù)結構
保存頭結點head和尾結點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é)點插入到頭結點后面，修改頭結點的next指向以及原本頭結點的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ù)結構
capacity保存最大容量，kvMap保存節(jié)點信息，linkLine為節(jié)點的順序鏈表。
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkLine = new linkLine();
};get
如果關鍵字 key 存在于緩存中，則返回關鍵字的值，并重置節(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
如果關鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value ，并重置節(jié)點鏈表順序，將該節(jié)點移到頭結點之后；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數(shù)量超過 capacity ， 則應該 逐出 最久未使用的關鍵字。
/**
* @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
到此這篇關于JavaScript雙向鏈表實現(xiàn)LRU緩存算法的示例代碼的文章就介紹到這了,更多相關JavaScript LRU緩存算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文給大家分享基于javascript制作的qq空間相冊展示效果，涉及到html\css布局思維，浮動定位詳解，具體實現(xiàn)代碼大家參考下本文2017-12-12
這篇文章主要介紹了JavaScript 作用域的相關資料，文中講解非常詳細，幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-07-07
在寫原生的Javascript的時候，因為IE的JS引擎與標準瀏覽器的JS引擎之間總有那么些差異，所以經(jīng)常會去判斷是否是IE瀏覽器2014-04-04
Axios?get?post請求傳遞參數(shù)的實現(xiàn)代碼
axios是基于promise用于瀏覽器和node.js的http客戶端，支持瀏覽器和node.js，能攔截請求和響應，這篇文章主要介紹了axios?get?post請求傳遞參數(shù)的操作代碼,需要的朋友可以參考下2022-11-11
這篇文章主要介紹了JS批量操作CSS屬性。需要的朋友可以過來參考下，希望對大家有所幫助2013-12-12
下面小編就為大家?guī)硪黄猨s實現(xiàn)(全選)多選按鈕的方法【附實例】。小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-03-03
這篇文章主要介紹了javascript鼠標滑動評分控件實現(xiàn)方法,以完整實例形式詳細分析了javascript操作鼠標事件及頁面元素樣式實現(xiàn)評分效果的方法,需要的朋友可以參考下2015-05-05
javascript實現(xiàn)點擊提交按鈕后顯示loading的方法
這篇文章主要介紹了javascript實現(xiàn)點擊提交按鈕后顯示loading的方法,涉及javascript動態(tài)設置頁面元素樣式的相關技巧,需要的朋友可以參考下2015-07-07
這篇文章主要介紹了JS常用倒計時代碼,結合實例形式總結分析了JS常用的倒計時功能實現(xiàn)方法,具有一定參考借鑒價值,需要的朋友可以參考下2017-02-02
WEB 前端開發(fā)中防治重復提交的實現(xiàn)方法
這篇文章主要介紹了JS WEB 前端開發(fā)中防治重復提交的實現(xiàn)方法,涉及到表單提交的幾種方式介紹，非常不錯具有參考借鑒價值，需要的朋友可以參考下2016-10-10