Skip to main content

146. LRU Cache

分析

背景分析

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. 在 Cache replacement policies 中对他的分类是在 Simple recency-based policies 中

这篇文章中分析了 LRU 和 LFU(frequency) 的区别

To do so, the cache will need to store given items in order of their last access. Then, each time someone tries to set a new key, or access a key, we need to modify the underlying list to ensure the needed order is maintained. But why is this order relevant? Wouldn't it be better to record the number of times each item was accessed so we can evict the Least Frequently Used instead? Not necessarily. Here are some reasons why:

  1. LRU is a actually a good proxy of LFU since the more frequently a pair is accessed, the less chance it has to be evicted.
  2. You will need to store integers in addition to everything else to keep track of the number of times the items were accessed.
  3. Ordering items on their last access is very straightforward to do since it can be synchronized with operations on the cache.
  4. LFU will often force you to make an arbitrary choice of item to evict: for instance if all your pairs have been accessed only once. With LRU, you don't have such choice to make: you just evict the least recently used. No ambiguity here.

问题分析

  1. get
    1. 不存在 返回 -1
    2. 存在 更新为最近使用 返回值
  2. put
      1. 存在 更新数据 更新为最近使用
      2. 不存在
        1. 考虑容量
        2. 添加数据 并为最近使用

查 删 加都是 O(1)

方案

  1. map + 双向链表
  2. 能够记录插入顺序的map结构 (ES6 的Map就具备这个能力)
    • A Map object iterates its elements in insertion order — a for...of loop returns an array of [key, value] for each iteration.

以上内容参考了

题解

利用 ES6 的有序Map

class LRUCache {
private caches = new Map<number, number>()
private capacity: number
constructor(capacity: number) {
this.capacity = capacity
}

get(key: number): number {
const val = this.caches.get(key)
if (val === undefined) {
return -1
}
this.caches.delete(key)
this.caches.set(key, val)
return val
}

put(key: number, value: number): void {
const val = this.caches.get(key)
if (val !== undefined) {
this.caches.delete(key)
// this.caches.set(key, value)
// return
}
if (this.capacity === this.caches.size) {
const leastRecentlyUsedKey = this.caches.keys().next().value
this.caches.delete(leastRecentlyUsedKey)
}
this.caches.set(key, value)
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/

双向链表 + map

class DoubleLinkedNode {
key: number
value: number
prev: DoubleLinkedNode | null = null
next: DoubleLinkedNode | null = null

constructor(key: number, value: number) {
this.key = key
this.value = value
}
}

class DoubleLinkedList {
head = new DoubleLinkedNode(-1, -1)
tail = new DoubleLinkedNode(-1, -1)

constructor() {
this.head.next = this.tail
this.tail.prev = this.head
}

moveNodeToHeadNext(node: DoubleLinkedNode): void {
// 看看操作是否有必要,即检测node是否已经刚好是 head.next
if (node.prev === this.head) {
return
}
// head -> a -> b -> c -> node -> x -> tail
// 先处理 x 原先位置的前后元素 // 也可能是新创建的元素
node.prev && (node.prev.next = node.next)
node.next && (node.next.prev = node.prev)

// head -> node -> lastFirstNode
const lastFirstNode = this.head.next
this.head.next = node
node.prev = this.head
node.next = lastFirstNode
lastFirstNode.prev = node
}

deleteNodeFromTailPrev() {
// 防御性 从逻辑上不会在没有元素的时候调用 即 head -> tail 这样的情况
if (this.tail.prev === this.head) {
// waring
return
}
// beforeLastNode -> lastNode -> tail
const lastNode = this.tail.prev
const beforeLastNode = lastNode.prev
beforeLastNode.next = this.tail
// 释放引用 GC
lastNode.prev = null
lastNode.next = null
this.tail.prev = beforeLastNode
}
}

class LRUCache {
capacity = 0
map = new Map<number, DoubleLinkedNode>()
doubleLinkedList = new DoubleLinkedList()

constructor(capacity: number) {
this.capacity = capacity
}

/**
get
1. 不存在 返回 -1
2. 存在 把元素移到最前 返回元素的值

要实现 O(1) 的查找 上map
*/
get(key: number): number {
const node = this.map.get(key)
if (!node) {
return -1
}
this.doubleLinkedList.moveNodeToHeadNext(node)
return node.value
}

/**
put
1. 存在
更新元素
把元素移动到最前
2. 不存在
空间够吗?
不够 删除末尾元素
创建新的元素
把元素移动到最前

要实现 O(1) 的增删 上双向链表
单向找上一个 是 O(n) 的
*/
put(key: number, value: number): void {
const node = this.map.get(key)
if (node) {
node.value = value
this.doubleLinkedList.moveNodeToHeadNext(node)
return
}
if (this.map.size === this.capacity) {
this.map.delete(this.doubleLinkedList.tail.prev.key)
this.doubleLinkedList.deleteNodeFromTailPrev()
}
const newNode = new DoubleLinkedNode(key, value)
this.map.set(key, newNode)
this.doubleLinkedList.moveNodeToHeadNext(newNode)
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/