[LC146] LRU Cache

Sunday, January 13, 2019

这道算法题来自 LeetCode #146:设计和实现一个 O(1) 复杂度的 LRU 缓存机制,要求支持获取数据 get(key) 和写入数据 put(key, value) 操作。

LRU 全称 Least Recently Used,即最近最少使用。顾名思义,该算法会优先从缓存中淘汰最近最少使用的数据,常用于虚拟页式存储管理服务。

Least Recently Used

我们可以通过一个有序的缓存列表来跟踪数据的使用频率,从而快速地淘汰最近最少使用的数据。按照 LRU 缓存机制运行流程,大体分为三种操作:初始化、写入数据、读取数据。

LRU 缓存机制的数据存放过程

Initialization

初始化一个有序的且容量固定 $Capacity$ 的缓存列表 $List$,用于存储一定量的缓存数据。假定数据在缓存列表中按照使用频率从多到少排列,则头部为最常访问的数据而尾部为最少访问的数据。

Set a value

  1. 如果数据存在,则把数据移到缓存列表的头部 $Prepend(List, Value)$ ,结束存放过程
  2. 如果数据不存在,则判断可用容量大小 $UsedCapacity > 0$
    1. 如果尚有剩余,把数据添加到缓存列表的头部 $Prepend(List, Value)$ ,同时增加已使用的缓存数量 $UsedCapacity + 1$,结束存放过程
    2. 如果已无剩余,则移除缓存列表的尾部元素 $Remove(List, Value)$ ,再把数据添加到缓存列表的头部 $Prepend(List, Value)$ ,结束存放过程

Get a value

  1. 如果数据存在,则把数据重新移到缓存列表的头部 $Remove(List, Value)$, $Prepend(List, Value)$,然后返回 $Return(Value)$,结束读取过程
  2. 如果数据不存在,则返回 $Return(-1)$

Linked List

type LinkedNode = {
  value: any,
  prev?: LinkedNode,
  next: LinkedNode | null
}

链表是一个线性的递归式数据结构,它至少包含一个指向下一个同类型数据的属性,如 next。如果还包含了一个指向了上一个同类型数据的属性,如 prev,则结果将形成双向链表。如果链表的最后一个元素的 next 总是指向头部结点,则结果形成循环链表。

三种链表
操作 数组 链表
访问 $O(1)$ $O(n)$
查找 $O(n)$ $O(n)$
插入 $O(n)$ $O(1)$
删除 $O(n)$ $O(1)$

相比于数组,链表的存储空间是非连续性的,从而提升了链表的可扩容性。对于数组来说,由于存储空间要求连续性,如果需要对其扩容,则必须重新申请一个更大的连续的空间,然后把原数组的数据复制到新的空间,其效率较低。不过,数组的随机访问可以通过偏移量计算得到对应的内存地址,其访问效率较高,时间复杂度为 $O(1)$,而链表则需要从头到尾遍历至目标结点,时间复杂度为 $O(n)$。同理,数组的插入与删除操作更耗时,而链表只需常数时间。

Design LRU Cache

type LRUCache = {
  list: DoublyLinkedNode,
  hash: Map<Number, DoublyLinkedNode>,
  capacity: Number,
  usedCapacity: Number,
  put: (key: Number, value: Number) => void,
  get: (key: Number) => Number
}

由于 LRU 会频繁地移动元素在列表中的位置,而移动操作实际包含了删除与插入操作,所以应该优先考虑 $LinkedList$ 这种能够在常数时间内完成的数据结构。

在移动过程中,我们需要定位到前继结点,所以考虑使用双向链表 $Doubly LinkedList$。由于同样需要在常数时间内定位到缓存列表的尾部,我们可以使用循环链表 $Circular LinkedList$,保证链表尾部的元素总是链接到头部结点,利用双向链表的特性,我们通过头部的前继结点定位到链表的尾结点。

综上所述,我们设计了一个复杂的链表结构即双向循环链表,使得常数时间内完成元素的移动操作。然而,$LinkedList$ 在随机读取的性能上较差,为了满足 $O(1)$ 的查找性能要求,我们考虑引入一个 $Map$ 来关联 $LinkedList$ 的结点 $Key$ 与 $Node Index$ 的信息。

Implementation

定义 LinkedNode 对象。由于这是一个循环双向链表,初始状态时 nextprev 都应该指向自身:

var LinkedNode = function(key, value) {
  this.key = key
  this.value = value
  this.prev = this
  this.next = this
}

定义 LRUCache 对象。为了简化代码,hash 属性直接用了 JavaScript Object 来实现 $Map$ 数据结构。另外,list 属性实际是 LRU 缓存链表的头结点,它的前继结点应该是链表的尾结点:

var LRUCache = function(capacity) {
  this.capacity = capacity
  this.usedCapacity = 0
  this.hash = {}
  this.list = new LinkedNode()
}
LRUCache.prototype._removeNode = function(node) {
  const { prev: before, next: after } = node
  before.next = after
  after.prev = before
}
LRUCache.prototype._prependNode = function(node) {
  const { next: head } = this.list
  this.list.next = node
  node.prev = this.list
  node.next = head
  head.prev = node
}
var contains = function(object, key) {
  return Object.prototype.hasOwnProperty.call(object, key)
}

LRUCache.prototype.get = function(key) {
  if (!contains(this.hash, key)) {
    return -1
  }
  
  const node = this.hash[key]
  this._removeNode(node)
  this._prependNode(node)
  
  return node.value
}

LRUCache.prototype.put = function(key, value) {
  if (contains(this.hash, key)) {
    const node = this.hash[key]
    node.value = value
    this._removeNode(node)
    this._prependNode(node)
    return
  }
  
  if (this.usedCapacity === this.capacity) {
    const tail = this.list.prev
    this._removeNode(tail)
    delete this.hash[tail.key]
    this.usedCapacity--
  }
  
  const node = new LinkedNode(key, value)
  this.hash[key] = node
  this._prependNode(node)
  
  this.usedCapacity++
}