什么是 LFU ？
-
LFU （Least Frequently Used）是最近最不常用算法；
-
它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素；
-
如果两个元素的访问频率相同，则淘汰最久没被访问的元素；
- 也就是说 LFU 淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；
- 如果频率相同，则按时间维度淘汰掉最久远的那个元素；
复杂度
-
时间复杂度：get 时间复杂度 O(1)，put 时间复杂度 O(1)，由于两个操作从头至尾都只利用了哈希表的插入删除还有链表的插入删除，且它们的时间复杂度均为 O(1)O，所以保证了两个操作的时间复杂度均为 O(1)；
-
空间复杂度：O(capacity)，其中 capacity 为 LFU 的缓存容量，哈希表中不会存放超过缓存容量的键值对；
代码实现
TS
JS
class LFUCache {
size: number;
values: Map<number, number> = new Map();
times: Map<number, number> = new Map();
useMap: Map<number, Set<number>> = new Map();
min: number;
constructor(capacity: number) {
// 缓存空间大小
this.size = capacity;
// 缓存存储
this.values = new Map(); // key:value
this.times = new Map(); // key：次数
// 找到当前次数最小的key
// useMap更新的逻辑，其实vue的响应式依赖管理很像
this.useMap = new Map(); // 次数：key，set(key)
this.min = 0; // 最小次数是多少
}
get(key: number): number {
if (this.values.has(key)) {
// 更新计数
this.updateCount(key);
return this.values.get(key);
}
return -1;
}
put(key: number, value: number): void {
// 缓存空间为 0，不操作
if (this.size === 0) return;
if (this.values.has(key)) {
// key值存在，不需要淘汰
this.values.set(key, value);
this.updateCount(key);
} else {
// key值不存在，判断是否超过缓存 size
if (this.size === this.values.size) {
// 满了需要淘汰掉 次数最少的、最长时间未访问的
let minSet = this.useMap.get(this.min);
let minKey = minSet.keys().next().value;
minSet.delete(minKey);
this.values.delete(minKey);
this.times.delete(minKey);
}
// 加入缓存
this.values.set(key, value);
// 这个数据出现了 1 次
let useSet = this.useMap.get(1) || (new Set() as Set<number>);
useSet.add(key);
this.useMap.set(1, useSet);
this.times.set(key, 1);
this.min = 1;
}
}
updateCount(key: number): void {
let time = this.times.get(key);
let useSet = this.useMap.get(time);
if (this.min === time && useSet.size === 1) {
//当前次数是最小值 并且 这个次数set集合只有一个 key
this.min += 1;
}
time += 1;
useSet.delete(key);
useSet = this.useMap.get(time) || new Set();
useSet.add(key);
this.useMap.set(time, useSet);
this.times.set(key, time);
}
}
var LFUCache = function (capacity) {
// 缓存空间大小
this.size = capacity
// 缓存存储
this.values = new Map() // key:value
this.times = new Map() // key:次数
// 找到当前次数最小的 key
// useMap 更新的逻辑，其实 vue 的响应式依赖管理很像
this.useMap = new Map() // 次数：set(key)
this.min = 0 // 最小次数是多少
};
LFUCache.prototype.updateCount = function (key) {
let time = this.times.get(key)
let useSet = this.useMap.get(time)
if (this.min === time && useSet.size === 1) {
//当前次数是最小值 并且 这个次数set集合只有一个 key
this.min += 1
}
time += 1
useSet.delete(key)
useSet = this.useMap.get(time) || new Set()
useSet.add(key)
this.useMap.set(time, useSet)
this.times.set(key, time)
}
LFUCache.prototype.get = function (key) {
if (this.values.has(key)) {
// 更新计数
this.updateCount(key)
return this.values.get(key)
}
return -1
};
LFUCache.prototype.put = function (key, value) {
// 缓存空间为 0，不操作
if (this.size === 0) return
if (this.values.has(key)) {
// key值存在，不需要淘汰
this.values.set(key, value)
this.updateCount(key)
} else {
// key值不存在，判断是否超过缓存 size
if (this.size === this.values.size) {
// 满了需要淘汰掉 次数最少的、最长时间未访问的
let minSet = this.useMap.get(this.min)
let minKey = minSet.keys().next().value
minSet.delete(minKey)
this.values.delete(minKey)
this.times.delete(minKey)
}
// 加入缓存
this.values.set(key, value)
// 这个数据出现了 1 次
let useSet = this.useMap.get(1) || new Set()
useSet.add(key)
this.useMap.set(1, useSet)
this.times.set(key, 1)
this.min = 1
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 347. 前 k 个高频元素
上一篇
评论
