最近做笔试的时候遇到了要手撸LFU的题目,LFU在vue源码里还是有使用的,例如keep-alive的实现机制就是基于它来搞的。不多说了,直接上代码。
// 双向链表node
class DoubleLinkNode {
key: number;
val: number;
freq: number;
prev?: DoubleLinkNode | null;
next?: DoubleLinkNode | null;
constructor(key, val, freq) {
this.freq = freq;
this.key = key;
this.val = val;
}
}
// 双向链表
class DoubleLink {
size: number;
head: DoubleLinkNode | null;
tail: DoubleLinkNode | null;
constructor() {
this.size = 0;
this.head = null;
this.tail = null;
}
// 删除一个节点
remove(node: DoubleLinkNode) {
// 空链表
if (this.size < 1) {
return;
}
// 只有一个元素
if (this.size === 1) {
this.size = 0;
this.head = null;
this.tail = null;
return;
}
// 删的是头结点
if (node === this.head) {
const nextNode = node.next;
nextNode.prev = null;
this.head = nextNode;
this.size--;
return;
}
// 删的是尾结点
if (node === this.tail) {
const prevNode = node.prev;
prevNode.next = null;
this.tail = prevNode;
this.size--;
return;
}
// 正常删中间节点
const prevNode = node.prev;
const nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
this.size--;
}
// 在尾部插入一个节点
addLast(node: DoubleLinkNode) {
// 空链表
if (this.size === 0) {
this.head = node;
this.tail = node;
} else {
// 非空链表
const curTail = this.tail;
curTail.next = node;
node.prev = curTail;
this.tail = node;
}
this.size++;
}
// 是否是空链表
isEmpty() {
return this.size === 0;
}
}
// 实现LFU缓存
class LFUCache {
keyToNodeMap: Map<number, DoubleLinkNode>;
freqToKeysMap: Map<number, DoubleLink>;
capacity: number;
minFreq: number;
constructor(capacity: number) {
this.keyToNodeMap = new Map();
this.freqToKeysMap = new Map();
this.capacity = capacity;
this.minFreq = 0;
}
get(key: number): number {
if (!this.keyToNodeMap.has(key)) {
return -1;
}
const node = this.keyToNodeMap.get(key);
// 增加频次
this.increaseFreq(node);
return node.val;
}
put(key: number, value: number): void {
// key已经存在
if (this.keyToNodeMap.has(key)) {
// 修改对应的node的val即可
const node = this.keyToNodeMap.get(key);
node.val = value;
this.increaseFreq(node);
} else {
// key不存在
// 容量满了
if (this.keyToNodeMap.size >= this.capacity) {
// 删除最小频次中最久没使用的
this.removeMinFreqKey();
}
// ------------正式开始插入------------
const newNode = new DoubleLinkNode(key, value, 1);
this.keyToNodeMap.set(key, newNode);
if (!this.freqToKeysMap.get(1)) {
this.freqToKeysMap.set(1, new DoubleLink());
}
// 维护频次表
const link = this.freqToKeysMap.get(1);
link.addLast(newNode);
// 插入新 key 后最小的 freq 肯定是 1
this.minFreq = 1;
}
}
// 增加频次
increaseFreq(node: DoubleLinkNode) {
const oldFreq = node.freq;
const newFreq = node.freq + 1;
node.freq = newFreq;
// 维护频次表
const oldFreqLink = this.freqToKeysMap.get(oldFreq);
// 从旧频次表中删除这个node
oldFreqLink.remove(node);
if (oldFreqLink.isEmpty()) {
this.freqToKeysMap.delete(oldFreq);
// 如果这个频次正好是最低频次,记得更新最小频次
if (this.minFreq === oldFreq) {
this.minFreq = newFreq;
}
}
// 维护新频次表
if (!this.freqToKeysMap.get(newFreq)) {
this.freqToKeysMap.set(newFreq, new DoubleLink());
}
const newFreqLink = this.freqToKeysMap.get(newFreq);
newFreqLink.addLast(node);
}
// 删除最小频次中最久没使用的
removeMinFreqKey() {
const minFreqLink = this.freqToKeysMap.get(this.minFreq);
// 其中最先被插入的那个 node 就是该被淘汰的 node
const deletedNode = minFreqLink.head;
// 维护最小频次map
minFreqLink.remove(deletedNode);
if (minFreqLink.isEmpty()) {
this.freqToKeysMap.delete(this.minFreq);
}
// key表中删除对应Node
this.keyToNodeMap.delete(deletedNode.key);
}
// log调试方法
print() {
console.log('keyToNodeMap: ', this.keyToNodeMap);
console.log('freqToKeysMap: ', this.freqToKeysMap);
}
}
LFU(Least Frequently Used)缓存是一种缓存淘汰策略,它根据元素的使用频率来决定哪些元素应该被淘汰。在你提供的代码中,LFUCache
类实现了这种策略,下面是它的工作原理的详细描述:
这种实现方式确保了:
这种缓存策略适用于那些需要平衡访问频率和最近使用情况的场景。
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁