0460. LFU Cache¶
题目信息¶
- 题号:
0460
- 难度:
Hard
- 主题:
缓存设计、访问频率、最久未使用、固定容量
- 原题:
- 重点:
get和更新已有键都会增加频率、满容量时先淘汰最低频率、频率并列时淘汰最久未使用、操作平均O(1)
题目重述¶
实现固定容量的 LFUCache。get(key):键存在时返回其值并把使用频率增加 1;键不存在时返回 -1。put(key, value):若键已存在,更新其值并把频率增加 1;若键不存在,则插入频率为 1 的新键。
插入新键前若缓存已满,先删除使用频率最低的键;若有多个键频率相同,则删除其中最久未使用的键。一次成功的 get 或对已有键的 put 都算一次使用,会更新并列淘汰所依据的新近程度。
capacity 位于 [0, 10^4];键位于 [0, 10^5],值位于 [0, 10^9],总调用次数不超过 2 * 10^5。容量为 0 时任何 put 都不能保存数据。get 和 put 都要求平均 O(1) 时间。
自建示例¶
频率较低的键先被淘汰:
初始:capacity = 2
调用:put(1,10), put(2,20), get(1), put(3,30), get(2), get(3)
查询输出:10、-1、30
解释:get(1) 后键 1 的频率为 2,键 2 的频率仍为 1;插入键 3 时淘汰键 2。
容量为零:
初始:capacity = 0
调用:put(5,50), get(5)
查询输出:-1
解释:零容量缓存不能保存任何键值对。
频率桶内用访问顺序解决并列¶
用一个按频率编号的双向链表集合保存键:同一频率的键位于同一个桶内,链表头是最近使用,尾部是最久未使用。哈希表把每个键映射到其值、频率和链表迭代器,因此可以在 O(1) 时间从旧桶删除并放入频率加一的新桶。
额外维护 minFrequency。新键总是进入频率 1 的桶;淘汰时直接取最低频率桶的尾节点。若某频率桶被移空且它正是最低频率,就把最低频率提升到下一桶。
C++ 实现¶
class LFUCache {
struct Entry {
int value;
int frequency;
std::list<int>::iterator position;
};
int capacity;
int minFrequency = 0;
std::unordered_map<int, Entry> entries;
std::unordered_map<int, std::list<int>> buckets;
void touch(int key) {
Entry& entry = entries[key];
int oldFrequency = entry.frequency;
auto bucketIt = buckets.find(oldFrequency);
bucketIt->second.erase(entry.position);
if (bucketIt->second.empty()) {
buckets.erase(bucketIt);
if (minFrequency == oldFrequency) ++minFrequency;
}
++entry.frequency;
buckets[entry.frequency].push_front(key);
entry.position = buckets[entry.frequency].begin();
}
public:
LFUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = entries.find(key);
if (it == entries.end()) return -1;
touch(key);
return entries[key].value;
}
void put(int key, int value) {
if (capacity == 0) return;
auto it = entries.find(key);
if (it != entries.end()) {
it->second.value = value;
touch(key);
return;
}
if (entries.size() == static_cast<size_t>(capacity)) {
auto& leastUsed = buckets[minFrequency];
int victim = leastUsed.back();
leastUsed.pop_back();
if (leastUsed.empty()) buckets.erase(minFrequency);
entries.erase(victim);
}
buckets[1].push_front(key);
entries[key] = {value, 1, buckets[1].begin()};
minFrequency = 1;
}
};
代码分析¶
频率哈希表定位桶,链表迭代器定位桶内节点,二者合起来使访问、升频和淘汰都不需要遍历。链表头插保证同频时最新访问在前,尾删正好淘汰最久未使用者;每个操作的平均时间复杂度为 O(1),空间复杂度为 O(capacity)。