算法就像搭乐高:带你手撸 LFU 算法
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
460. LFU Cache | 460. LFU 缓存 | 🔴 |
上篇文章 带你手写LRU算法 写了 LRU 缓存淘汰算法的实现方法,本文来写另一个著名的缓存淘汰算法:LFU 算法。
LRU 算法的淘汰策略是 Least Recently Used,也就是每次淘汰那些最久没被使用的数据;而 LFU 算法的淘汰策略是 Least Frequently Used,也就是每次淘汰那些使用次数最少的数据。
LRU 算法的核心数据结构是使用哈希链表 LinkedHashMap
,首先借助链表的有序性使得链表元素维持插入顺序,同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。
从实现难度上来说,LFU 算法的难度大于 LRU 算法,因为 LRU 算法相当于把数据按照时间排序,这个需求借助链表很自然就能实现,你一直从链表头部加入元素的话,越靠近头部的元素就是新的数据,越靠近尾部的元素就是旧的数据,我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
而 LFU 算法相当于是把数据按照访问频次进行排序,这个需求恐怕没有那么简单,而且还有一种情况,如果多个数据拥有相同的访问频次,我们就得删除最早插入的那个数据。也就是说 LFU 算法是淘汰访问频次最低的数据,如果访问频次最低的数据有多条,需要淘汰最旧的数据。
所以说 LFU 算法是要复杂很多的,而且经常出现在面试中,因为 LFU 缓存淘汰算法在工程实践中经常使用,也有可能是因为 LRU 算法太简单了。不过话说回来,这种著名的算法的套路都是固定的,关键是由于逻辑较复杂,不容易写出漂亮且没有 bug 的代码。
那么本文我就带你拆解 LFU 算法,自顶向下,逐步求精,就是解决复杂问题的不二法门。
一、算法描述
要求你写一个类,接受一个 capacity
参数,实现 get
和 put
方法:
class LFUCache {
// 构造容量为 capacity 的缓存
public LFUCache(int capacity) {}
// 在缓存中查询 key
public int get(int key) {}
// 将 key 和 val 存入缓存
public void put(int key, int val) {}
}
class LFUCache {
public:
// 构造容量为 capacity 的缓存
LFUCache(int capacity) {}
// 在缓存中查询 key
int get(int key) {}
// 将 key 和 val 存入缓存
void put(int key, int val) {}
};
class LFUCache:
def __init__(self, capacity: int):
# 构造容量为 capacity 的缓存
pass
def get(self, key: int) -> int:
# 在缓存中查询 key
pass
def put(self, key: int, val: int) -> None:
# 将 key 和 val 存入缓存
pass
type LFUCache struct {
}
// 构造容量为 capacity 的缓存
func Constructor(capacity int) *LFUCache {
return &LFUCache{}
}
// Get 从缓存中查询 key,并返回其对应的值。如果key不存在,则返回 -1。
func (c *LFUCache) Get(key int) int {
return 0
}
// Put 将 key 和 value 存入缓存中。如果容量已满,则需要删除缓存中最近最少使用的元素
func (c *LFUCache) Put(key int, value int) {
}
var LFUCache = function (capacity) {
// 构造容量为 capacity 的缓存
}
LFUCache.prototype.get = function (key) {
// 在缓存中查询 key
}
LFUCache.prototype.put = function (key, val) {
// 将 key 和 val 存入缓存
}
get(key)
方法会去缓存中查询键 key
,如果 key
存在,则返回 key
对应的 val
,否则返回 -1。
put(key, value)
方法插入或修改缓存。如果 key
已存在,则将它对应的值改为 val
;如果 key
不存在,则插入键值对 (key, val)
。
当缓存达到容量 capacity
时,则应该在插入新的键值对之前,删除使用频次(后文用 freq
表示)最低的键值对。如果 freq
最低的键值对有多个,则删除其中最旧的那个。
// 构造一个容量为 2 的 LFU 缓存
LFUCache cache = new LFUCache(2);
// 插入两对 (key, val),对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
// 查询 key 为 1 对应的 val
// 返回 10,同时键 1 对应的 freq 变为 2
cache.get(1);
// 容量已满,淘汰 freq 最小的键 2
// 插入键值对 (3, 30),对应的 freq 为 1
cache.put(3, 30);
// 键 2 已经被淘汰删除,返回 -1
cache.get(2);
// 构造一个容量为 2 的 LFU 缓存
LFUCache cache(2);
// 插入两对 (key, val),对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
// 查询 key 为 1 对应的 val
// 返回 10,同时键 1 对应的 freq 变为 2
cache.get(1);
// 容量已满,淘汰 freq 最小的键 2
// 插入键值对 (3, 30),对应的 freq 为 1
cache.put(3, 30);
// 键 2 已经被淘汰删除,返回 -1
cache.get(2);
# 构造一个容量为 2 的 LFU 缓存
cache = LFUCache(2)
# 插入两对 (key, val),对应的 freq 为 1
cache.put(1, 10)
cache.put(2, 20)
# 查询 key 为 1 对应的 val
# 返回 10,同时键 1 对应的 freq 变为 2
cache.get(1)
# 容量已满,淘汰 freq 最小的键 2
# 插入键值对 (3, 30),对应的 freq 为 1
cache.put(3, 30)
# 键 2 已经被淘汰删除,返回 -1
cache.get(2)
// 构造一个容量为 2 的 LFU 缓存
cache := Constructor(2)
// 插入两对 (key, val),对应的 freq 为 1
cache.Put(1, 10)
cache.Put(2, 20)
// 查询 key 为 1 对应的 val
// 返回 10,同时键 1 对应的 freq 变为 2
cache.Get(1)
// 容量已满,淘汰 freq 最小的键 2
// 插入键值对 (3, 30),对应的 freq 为 1
cache.Put(3, 30)
// 键 2 已经被淘汰删除,返回 -1
cache.Get(2)
// 构造一个容量为 2 的 LFU 缓存
var cache = new LFUCache(2);
// 插入两对 (key, val),对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
// 查询 key 为 1 对应的 val
// 返回 10,同时键 1 对应的 freq 变为 2
cache.get(1);
// 容量已满,淘汰 freq 最小的键 2
// 插入键值对 (3, 30),对应的 freq 为 1
cache.put(3, 30);
// 键 2 已经被淘汰删除,返回 -1
cache.get(2);
二、思路分析
一定先从最简单的开始,根据 LFU 算法的逻辑,我们先列举出算法执行过程中的几个显而易见的事实:
1、调用 get(key)
方法时,要返回该 key
对应的 val
。
2、只要用 get
或者 put
方法访问一次某个 key
,该 key
的 freq
就要加一。
3、如果在容量满了的时候进行插入,则需要将 freq
最小的 key
删除,如果最小的 freq
对应多个 key
,则删除其中最旧的那一个。
好的,我们希望能够在 O(1) 的时间内解决这些需求,可以使用基本数据结构来逐个击破:
1、使用一个 HashMap
存储 key
到 val
的映射,就可以快速计算 get(key)
。
HashMap<Integer, Integer> keyToVal;
unordered_map<int, int> keyToVal;
keyToVal = {}
keyToVal := make(map[int]int)
var keyToVal = new Map();
2、使用一个 HashMap
存储 key
到 freq
的映射,就可以快速操作 key
对应的 freq
。
HashMap<Integer, Integer> keyToFreq;
unordered_map<int, int> keyToFreq;
keyToFreq = {}
keyToFreq := make(map[int]int)
var keyToFreq = new Map();
3、这个需求应该是 LFU 算法的核心,所以我们分开说: