JavaScript雙向鏈表實現LFU緩存算法

Posted on by

什麼是LFU

LFU（Least Frequently Used），最近最少使用策略，也就是說在一段時間內，數據被使用頻次最少的，優先被淘汰。
它是一種用於管理計算機內存的緩存算法，采用LFU算法的最簡單方法是為每個加載到緩存的塊分配一個計數器。每次引用該塊時，計數器將增加一。當緩存達到容量並有一個新的內存塊等待插入時，系統將搜索計數器最低的塊並將其從緩存中刪除。

描述

請你為 最不經常使用（LFU）緩存算法設計並實現數據結構。

實現 LFUCache 類：

LFUCache(int capacity) – 用數據結構的容量 capacity 初始化對象

int get(int key) – 如果鍵 key 存在於緩存中，則獲取鍵的值，否則返回 -1 。

void put(int key, int value) – 如果鍵 key 已存在，則變更其值；如果鍵不存在，請插入鍵值對。

當緩存達到其容量 capacity 時，則應該在插入新項之前，移除最不經常使用的項。

在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除 最近最久未使用 的鍵。

為瞭確定最不常使用的鍵，可以為緩存中的每個鍵維護一個 使用計數器 。使用計數最小的鍵是最久未使用的鍵。

當一個鍵首次插入到緩存中時，它的使用計數器被設置為 1 (由於 put 操作)。對緩存中的鍵執行 get 或 put 操作，使用計數器的值將會遞增。

函數 get 和 put 必須以 O(1) 的平均時間復雜度運行。

解題思路

1、構造節點結構體

保存對應的數據信息

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、構造雙向鏈表

構造帶有頭尾節點的雙向鏈表，head和tail為哨兵節點，不保存信息，僅用於標記頭尾。

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、編寫鏈表頭添加節點方法

將節點插入到鏈表的頭結點之後，其他節點往後移。

LFULinkLine.prototype.addNode = function (node) {
  this.head.next.pre = node;
  node.pre = this.head;
  node.next = this.head.next;
  this.head.next = node;
};

4、編寫刪除節點方法

將節點從鏈表中刪除。

LFULinkLine.prototype.removeNode = function (node) {
  node.pre.next = node.next;
  node.next.pre = node.pre;
};

5、構造LRU緩存結構體

構造LRU緩存結構體，具體信息如下代碼，capacity用於保存最大緩存數，即該類的容量；num保存當前存儲的數據量，用於判別是否超出最大容量；minFreq保存當前存儲的數據中的最小頻率，刪除的時候需要優先刪除頻率最小的；kvMap保存節點詳細信息，索引為節點的key值，查詢可以直接從這裡查出信息；freqMap保存對應頻率的鏈表信息，索引為節點的freq（頻率），刪除的時候可以快速從這裡獲取需要刪除節點的信息。

/**
 * @param {number} capacity
 */
var LFUCache = function (capacity) {
  this.capacity = capacity;//最大緩存
  this.num = 0;//當前數目
  this.minFreq = 0;//當前最小頻率
  this.kvMap = new Map();//保存節點信息
  this.freqMap = new Map();//保存對應頻率的鏈表信息
};

6、編寫get方法

get主要有以下兩種情況：

（1）節點存在

  • 通過kvMap獲取到對應節點
  • 將節點從freqMap中刪除
  • 判斷是否需要修改minFreq
  • 修改節點的freq
  • 重新將節點插入freqMap
  • 返回節點的value

（2）節點不存在
容量capacity為0或者kvMap中沒有該節點信息，直接返回-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獲取到對應節點
  let node = this.kvMap.get(key);
  let linkLine = this.freqMap.get(node.freq);
  //將節點從freqMap中刪除
  linkLine.removeNode(node);
  //判斷是否需要修改minFreq
  //清空瞭
  if (linkLine.head.next === linkLine.tail) {
    this.freqMap.delete(node.freq);
    if (this.minFreq == node.freq) this.minFreq++;
  }
  //修改節點的freq
  node.freq++;
  //重新將節點插入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));
  }
  //返回節點的value
  return node.val;
};

7、編寫put方法

put操作主要有以下兩種情況：

（1）更新

  • 通過kvMap獲取到對應節點
  • 將節點從freqMap中刪除
  • 判斷是否需要修改minFreq
  • 更新節點信息
  • 重新將節點插入freqMap

（2）存入

存入情況下又有兩種情況：

容量已滿

  • 通過minFreq找到需要刪除的節點
  • 將節點從freqMap中刪除
  • 判斷是否需要修改minFreq
  • 將新節點插入freqMap
  • 更新minFreq

容量未滿

  • 修改num
  • 將新節點插入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獲取到對應節點
    let node = this.kvMap.get(key);
    //將節點從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);
    }
    //更新節點信息
    node.val = value;
    node.freq++;
    //重新將節點插入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找到需要刪除的節點
      let freq = this.minFreq;
      let linkLine = this.freqMap.get(freq);
      let node = linkLine.tail.pre;
      //將節點從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++;
    }
    //將新節點插入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雙向鏈表實現LFU緩存算法的文章就介紹到這瞭,更多相關JavaScript LFU緩存算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：