目標(biāo)

請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)一個(gè)滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。 實(shí)現(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)鍵字?jǐn)?shù)量超過(guò) capacity ，則應(yīng)該 逐出 最久未使用的關(guān)鍵字。 函數(shù) get 和 put 必須以 O(1) 的平均時(shí)間復(fù)雜度運(yùn)行。

什么是LRU

LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁(yè)面置換算法，選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間 t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其 t 值最大的，即最近最少使用的頁(yè)面予以淘汰。

簡(jiǎn)介

最近最少使用算法（LRU）是大部分操作系統(tǒng)為最大化頁(yè)面命中率而廣泛采用的一種頁(yè)面置換算法。該算法的思路是，發(fā)生缺頁(yè)中斷時(shí)，選擇未使用時(shí)間最長(zhǎng)的頁(yè)面置換出去。 從程序運(yùn)行的原理來(lái)看，最近最少使用算法是比較接近理想的一種頁(yè)面置換算法，這種算法既充分利用了內(nèi)存中頁(yè)面調(diào)用的歷史信息，又正確反映了程序的局部問(wèn)題。利用 LRU 算法對(duì)上例進(jìn)行頁(yè)面置換的結(jié)果如圖1所示。當(dāng)進(jìn)程第一次對(duì)頁(yè)面 2 進(jìn)行訪問(wèn)時(shí)，由于頁(yè)面 7 是最近最久未被訪問(wèn)的，故將它置換出去。當(dāng)進(jìn)程第一次對(duì)頁(yè)面 3進(jìn)行訪問(wèn)時(shí)，第 1 頁(yè)成為最近最久未使用的頁(yè)，將它換出。由圖1可以看出，前 5 個(gè)時(shí)間的圖像與最佳置換算法時(shí)的相同，但這并非是必然的結(jié)果。因?yàn)椋罴阎脫Q算法是從“向后看”的觀點(diǎn)出發(fā)的，即它是依據(jù)以后各頁(yè)的使用情況；而 LRU 算法則是“向前看”的，即根據(jù)各頁(yè)以前的使用情況來(lái)判斷，而頁(yè)面過(guò)去和未來(lái)的走向之間并無(wú)必然的聯(lián)系。

硬件支持

LRU 置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)面各有多少時(shí)間未被進(jìn)程訪問(wèn)，以及如何快速地知道哪一頁(yè)是最近最久未使用的頁(yè)面，須有兩類硬件之一的支持：寄存器或棧。

寄存器

為了記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為

R = Rn-1 Rn-2 Rn-3 … R2 R1 R0

圖 2 某進(jìn)程具有 8 個(gè)頁(yè)面時(shí)的 LRU 訪問(wèn)情況

當(dāng)進(jìn)程訪問(wèn)某物理塊時(shí)，要將相應(yīng)寄存器的 R n -1 位置成 1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如 100 ms)將寄存器右移一位。 如果我們把 n 位寄存器的數(shù)看做是一個(gè)整數(shù)， 那么，具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁(yè)面，就是最近最久未使用的頁(yè)面。圖2示出了某進(jìn)程在內(nèi)存中具有 8 個(gè)頁(yè)面，為每個(gè)內(nèi)存頁(yè)面配置一個(gè) 8 位寄存器時(shí)的 LRU 訪問(wèn)情況。這里，把 8 個(gè)內(nèi)存頁(yè)面的序號(hào)分別定為 1～8。由圖可以看出，第 3 個(gè)內(nèi)存頁(yè)面的 R 值最小，當(dāng)發(fā)生缺頁(yè)時(shí)，首先將它置換出去。

棧

圖 3 用棧保存當(dāng)前使用頁(yè)面時(shí)棧的變化情況

可利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)，而棧底則是最近最久未使用頁(yè)面的頁(yè)面號(hào)。假定現(xiàn)有一進(jìn)程所訪問(wèn)的頁(yè)面的頁(yè)面號(hào)序列為：

4，7，0，7，1，0，1，2，1，2，6

隨著進(jìn)程的訪問(wèn)， 棧中頁(yè)面號(hào)的變化情況如圖 3 所示。 在訪問(wèn)頁(yè)面 6 時(shí)發(fā)生了缺頁(yè)，此時(shí)頁(yè)面 4 是最近最久未被訪問(wèn)的頁(yè)，應(yīng)將它置換出去。

代碼實(shí)現(xiàn)

思路

• Map 使用一個(gè)Map來(lái)保存當(dāng)前所有節(jié)點(diǎn)的信息，鍵為key，值為鏈表中的具體節(jié)點(diǎn)。

• 鏈表

  使用一個(gè)雙向鏈表來(lái)記錄當(dāng)前節(jié)點(diǎn)的順序。

鏈表節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

保存插入節(jié)點(diǎn)信息，pre指向上一個(gè)節(jié)點(diǎn)，next指向下一個(gè)節(jié)點(diǎn)。

const linkLineNode = function (key = "", val = "") {
  this.val = val;
  this.key = key;
  this.pre = null;
  this.next = null;
};

鏈表數(shù)據(jù)結(jié)構(gòu)

保存頭結(jié)點(diǎn)head和尾結(jié)點(diǎn)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é)點(diǎn)插入到頭結(jié)點(diǎn)后面，修改頭結(jié)點(diǎn)的next指向以及原本頭結(jié)點(diǎn)的next節(jié)點(diǎn)的pre指向。

linkLine.prototype.append = function (node) {
  node.next = this.head.next;
  node.pre = this.head;
  this.head.next.pre = node;
  this.head.next = node;
};

鏈表刪除指點(diǎn)節(jié)點(diǎn)

重新指向節(jié)點(diǎn)前后節(jié)點(diǎn)的next和pre指向。

linkLine.prototype.delete = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};

刪除并返回鏈表的最后一個(gè)節(jié)點(diǎn)（非tail）

取到鏈表的最后一個(gè)節(jié)點(diǎn)（非tail節(jié)點(diǎn)），刪除該節(jié)點(diǎn)并返回節(jié)點(diǎn)信息。

linkLine.prototype.pop = function () {
  let node = this.tail.pre;
  node.pre.next = this.tail;
  this.tail.pre = node.pre;
  return node;
};

打印鏈表信息

將鏈表的信息按順序打印出來(lái)，入?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é)點(diǎn)信息，linkLine為節(jié)點(diǎn)的順序鏈表。

/**
 * @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é)點(diǎn)鏈表順序，將該節(jié)點(diǎn)移到頭結(jié)點(diǎn)之后，否則返回 -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é)點(diǎn)鏈表順序，將該節(jié)點(diǎn)移到頭結(jié)點(diǎn)之后；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過(guò) capacity ， 則應(yīng)該 逐出 最久未使用的關(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);
  }
};

測(cè)試

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雙向鏈表實(shí)現(xiàn)LRU緩存算法的示例代碼的文章就介紹到這了,更多相關(guān)JavaScript LRU緩存算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論