LRU 缓存实现 #
如何实现LRU缓存方案？应该使用什么数据结构？ #
我们给出了可以引用的总可能页码。我们还给出了缓存（或内存）大小（缓存一次可以容纳的页帧数）。LRU 缓存方案是当缓存已满并且引用缓存中不存在的新页面时删除最近最少使用的帧。
使用队列和散列的 LRU 缓存实现： #
要解决该问题，需要遵循以下想法：
我们使用两种数据结构来实现 LRU Cache。
- 队列是使用双向链表实现的。队列的最大大小将等于可用帧的总数（缓存大小）。最近使用的页面将靠近前端，最近最少使用的页面将靠近后端。
- 以页码为键、对应队列节点的地址为值的哈希。
当一个页面被引用时，所需的页面可能在内存中。如果它在内存中，我们需要分离列表的节点并将其带到队列的前面。 如果所需的页面不在内存中，我们会将其放入内存中。简单来说，我们将一个新节点添加到队列的前面，并更新哈希中相应的节点地址。如果队列已满，即所有帧都已满，我们从队列的后面删除一个节点，并将新节点添加到队列的前面。
**示例 –**考虑以下参考字符串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
使用 3 页框架的最近最少使用 (LRU) 页面替换算法查找页面错误数。
下面是上述方法的图示：
**注意：**最初内存中没有任何元素。
请按照以下步骤解决问题：
- 创建一个 LRUCache 类，声明一个 int 类型的列表、一个 <int, list
> 类型的无序映射以及一个用于存储缓存最大大小的变量 - 在LRUCache的refer函数中
- 如果队列中不存在该值，则将该值推入队列前面，如果队列已满，则删除最后一个值
- 如果该值已经存在，则将其从队列中删除并将其推入队列的前面
- 在显示函数print中，LRUCache使用从前面开始的队列
javascript 代码示例: #
// JavaScript program to implement LRU cache
// using Set and LinkedList
class LRUCache {
constructor(capacity) {
this.cache = new Set();
this.capacity = capacity;
}
// This function returns false if key is not
// present in cache. Else it moves the key to
// front by first removing it and then adding
// it, and returns true.
get(key) {
if (!this.cache.has(key)) {
return false;
}
this.cache.delete(key);
this.cache.add(key);
return true;
}
/* Refers key x with in the LRU cache */
refer(key) {
if (!this.get(key)) {
this.put(key);
}
}
// displays contents of cache in Reverse Order
display() {
const list = [...this.cache];// The reverse() method of
// Array class is used to reverse the elements in the array
list.reverse();
let ans="";
for (const key of list) {
ans = ans +key + " ";
}
console.log(ans);
}
put(key) {
if (this.cache.size === this.capacity) {
const firstKey = this.cache.values().next().value;
this.cache.delete(firstKey);
}
this.cache.add(key);
}
}
// Driver code
const ca = new LRUCache(4);
ca.refer(1);
ca.refer(2);
ca.refer(3);
ca.refer(1);
ca.refer(4);
ca.refer(5);
ca.display();
golang 代码示例: #
package main
import (
"fmt"
"testing"
)
type LRUCache struct {
list []int
csize int
ma map[int]int
}
func (lru *LRUCache) refer(x int) {
if index, ok := lru.ma[x]; !ok {
// 如果存在,比较当前的容量是否已达上限
if len(lru.list) == lru.csize {
// 如果已达上限,则删除栈顶元素
lru.list = lru.list[:lru.csize-1]
}
} else {
// 如果存在, 则删除对应 index 位置的值, 并将期追加到队尾
lru.list = append(lru.list[:index-1], lru.list[index+1:]...)
}
lru.list = append(lru.list, x)
lru.ma[x] = len(lru.list)
}
func (lru *LRUCache) Display() {
for i := len(lru.list) - 1; i >= 0; i-- {
fmt.Println(lru.list[i])
}
}
func NewLRUCache(size int) *LRUCache {
ma := make(map[int]int)
return &LRUCache{
list: []int{},
csize: size,
ma: ma,
}
}
func Test_NewLRUCache(t *testing.T) {
cache := NewLRUCache(4)
cache.refer(1)
cache.refer(2)
cache.refer(3)
cache.refer(1)
cache.refer(4)
cache.refer(5)
cache.Display()
}
时间复杂度： O(1)，我们使用Linked HashSet数据结构来实现缓存。Linked HashSet 为添加元素和检索元素提供恒定的时间复杂度。 辅助空间： O(n)，我们需要在缓存中存储n个元素，所以空间复杂度为O(n)。