实现一个 LRU-K

[francecil]

LRU: 最近最少使用算法，即 数据最近使用过，将来也很可能使用过。 leetcode 原题
LRU-K: 当某个数据块被访问了k次，该数据块会被移动到缓存队列中。像 LRU 就是 LRU-1 ，数据被访问了就直接放缓存队列中。

• : 实现 LRU
• : 实现 LRU-K

[francecil]

LRU

原理

LRU（Least recently used，最近最少使用）缓存放置策略

LRU 的算法流程如下：

1. 维护一个缓存队列，新数据入队该队列
2. 命中缓存后将数据项重新入队
3. 缓存满后出队队首元素

执行一次 放置缓存 指令后，数据项一定会在该缓存队列中

实现

实现 LRU 有多种方式，可以用数组或者链表，不过存取的效率较低，业界较常用的是 LinkedHashMap （即 hashmap + 双向链表 实现 ）,那么在 JavaScript 中应该怎么快速实现呢？

利用 Map 数据结构

一开始以为 Map 仅用来做 HashMap 的数据结构，忘记还提供方法返回 Iterator （按插入顺序），导致我自己写了一个 双向链表 , Map 中保存的链表中节点。。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  // hashmap 存储 k-v 快速get
  this.map = new Map()
  // DoublyLinkedList <-> Node { value }
  this.mapTail = {
  };
  this.mapHead = {
  };
  this.mapHead.nextNode = this.mapTail
  this.mapTail.previousNode = this.mapHead
  // 置于链表尾部
  this._pushNode = function (node) {
    let mapTailPreviousNode = this.mapTail.previousNode
    mapTailPreviousNode.nextNode = node
    node.previousNode = mapTailPreviousNode
    node.nextNode = this.mapTail
    this.mapTail.previousNode = node
    this.map.set(node.key, node)
  }
  // 删除该节点在链表中的链接
  this._removeNode = function (node) {
    let previousNode = node.previousNode
    let nextNode = node.nextNode
    previousNode.nextNode = nextNode
    nextNode.previousNode = previousNode
    // 从hashmap中删除
    this.map.delete(node.key)
  }
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  let node = this.map.get(key)
  if (!node) {
    return -1
  } else {
    this._removeNode(node)
    this._pushNode(node)
    return node.value
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {

  let node = this.map.get(key)
  if (node) {
    // 更新值
    node.value = value
    this._removeNode(node)
    this._pushNode(node)
  } else {
    if (this.map.size >= this.capacity) {
      // 删除首个节点
      this._removeNode(this.mapHead.nextNode)
    }
    this._pushNode({
      key,
      value,
    })
  }
};

var cache = new LRUCache(2 /* 缓存容量 */);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

其实只要知道最早插入的元素的key 即可，这点可以 通过 map.keys().next() 实现

修改后的代码如下：

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) {
    return -1
  } else {
    let value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {

  if (!this.map.has(key)) {
    if (this.map.size >= this.capacity) {
      // 删除首个节点
      this.map.delete(this.map.keys().next().value)
    }
    this.map.set(key, value)
  } else {
    this.map.delete(key)
    this.map.set(key, value)
  }
};

优缺点

优点即实现简单。

缺点：存在缓存污染的问题，即对周期性的，偶发性的数据缓存操作，会降低缓存命中率

举例，周期性的操作，以下访问没有命中过缓存

var cache = new LRUCache(2) // 容量为2的缓存
cache.get(1) // -1 未命中缓存
cache.put(1,1)  // [1]
cache.get(2) // -1 未命中缓存
cache.put(2,2) // [1,2]
cache.get(3) // -1 未命中缓存
cache.put(3,3) // [2,3]
cache.get(1) // -1 未命中缓存
cache.put(1,1) // [3,1]
cache.get(2) // -1 未命中缓存

偶发性的缓存操作，导致高频 get(1) 反而没有命中过缓存，

var cache = new LRUCache(2) 
cache.get(1) // -1 未命中缓存
cache.put(1,1)  // [1]
cache.put(2,2) // [1,2]
cache.put(3,3) // [2,3]
cache.get(1) // -1 未命中缓存
cache.put(1,1) // [3,1]
cache.put(5,5) // [1,5]
cache.put(6,6) // [5,6]
cache.get(1) // -1 未命中缓存

[francecil]

LRU-K

原理

执行K次 放置缓存 指令后，数据项才会放在缓存队列中

LRU-K 的算法流程如下：

1. 初始化一个缓存队列和访问历史队列（通常后者容量比前者大或相同）
2. 命中缓存后将数据项重新入队缓存队列
3. 缓存满后出队缓存队列队首元素
4. 对于未命中缓存的数据项，在访问历史队列中记录该项被访问的次数。若达到K次，删除访问历史队列中该项的记录，并将该数据项入队缓存队列。该访问历史队列的数据可以用 LRU 或 FIFO 来淘汰

实现

history 用 LRUCache ， cache 借助 Map 实现

var LRUKCache = function (k, capacity) {
  this.k = k
  this.capacity = capacity
  this.history = new LRUCache(capacity * 2)
  this.cache = new Map()
}
/** 
 * @param {number} key
 * @return {number}
 */
LRUKCache.prototype.get = function (key) {
  if (!this.cache.has(key)) {
    return -1
  } else {
    let value = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, value)
    return value
  }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUKCache.prototype.put = function (key, value) {

  if (!this.cache.has(key)) {
    // 判断 history 中该项是否达到k次
    let count = this.history.get(key)
    // 保持与 lru-1 实现一致
    if (count === -1) {
      count = 0
    }
    if (count + 1 === this.k) {
      // 达到k次，从 history 中删除该元素，插入到 cache 中
      this.history.map.delete(key)
      if (this.cache.size >= this.capacity) {
        // 删除首个节点
        this.cache.delete(this.cache.keys().next().value)
      }
      this.cache.set(key, value)
    } else {
      this.history.put(key, count + 1)
    }
  } else {
    this.cache.delete(key)
    this.cache.set(key, value)
  }
};
var cache = new LRUKCache(2, 2) // lru-2 容量为 2
cache.put(1, 1) // []
cache.get(1) // -1 缓存未命中
cache.put(1, 2) // [1]
cache.get(1) // 2
cache.put(2, 2)
cache.put(2, 2) // [1,2]
cache.put(3, 3) // [1,2]
cache.put(4, 4)
cache.put(4, 4) // [2,4]
cache.get(1) // -1 缓存未命中
cache.get(2) // 2 [4,2]

优缺点

缓存命中率更高，降低 缓存污染 的问题

实现相对复杂，占用更多空间

参考

1. LRU . LFU 和 LRU-K 的解釋與區別
2. LRU算法 缓存淘汰策略