LRU Cache 和 LFU Cache

作者 Lucyyang 日期 2020-03-12
LRU Cache 和 LFU Cache

Easy choice, hard life; hard choice, easy life.

总结一下两道缓存器设计题目,分别是LRU CacheLFU Cache。二者设计既有共同点,也有区别,下面分别进行讨论。

LRU Cache

先普及下知识,什么是Least Recently Used (LRU) cache:在一个缓存器中,存储着容量(capacity)以内的元素(key, value),对该存储器无论事存(put)还是取(get)都相当于使用了一次该元素。当容量达到上限,继续存储时,该存储器就会扔掉最少的元素。例如容量为2时,我们先put(key = 1, value = 1),再put(key = 2, value = 2),当我们调用get(key = 1)时,(1,1)这个元素的优先级就提高了,如果再次put(key = 3, value = 3),则会将最少使用的(2,2)丢掉。

题目:要求实现LRU Cache中put和get时间复杂度都为O(1)的方法

方法:要求删除和插入时间复杂度都为O(1),那么最先想到的就是double list,假设我们已经知道了一个节点node的位置,删除该节点只需node->pre->next = node->next,node->next->pre = node->pre即可完成。如果double list要插入node_new,只需node_new->pre = node->pre, node_new->next = node,node->pre->next = node_new, node->pre = node_new即可。C++中,list即为double list。

那么接下来的问题就是如何在O(1)时间内找到double list的节点位置,我们可以用hash table进行实现,C++中的数据结构为unordered_map。在unordered_map中存储key和对应的double list节点的地址(迭代器),则当我们查询某个元素的时候即可快速返回其在double list中的位置。

HashLinkedList.jpg

接下来就是具体的实现逻辑了,通过伪代码的方法进行介绍:

class LRUCache {
private:
int capacity; //容量,全局变量
list<pair<int, int>> recent; // double list,存储key 和value
unordered_map<int, list<pair<int, int>>::iterator> map; // hash table,用于查找并返回double list中的节点位置
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
// 如果在hash table 中找到了key,
//采用一个trick:通过调用put函数,将其优先级提到最高
//返回该元素value
// 否则返回-1表示该元素不存在
}
void put(int key, int value) {
// 分两种情况,一是cache中已经有这个元素了,只需消除本来元素,并将优先级提前
// 另一种是该元素是新的,此时要判断现有元素个数是否已经要超过容量了
//如果超过了容量,则删去双向链表最末端的元素(即最少使用的元素),再将该元素插入至头部
//如果没有超过容量,直接插入至链表头部,不要忘了更新hash table
// 根据以上逻辑,可以将元素插入链表以及更新hash table放到最后一起做
}
};

最后的实现代码:

class LRUCache {
private:
int capacity;
list<pair<int, int>> recent;
unordered_map<int, list<pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if(map.find(key) != map.end()){
put(key, map[key]->second);
return map[key]->second; //返回的是val,因此是第二个值
}
return -1;
}
void put(int key, int value) {
if(map.find(key) != map.end()) {
auto it = map[key];
recent.erase(it);
}else if(recent.size() >= capacity) {
map.erase(recent.back().first);
printf("erase:%d\n",recent.back().first);
recent.pop_back();
}
recent.push_front({key, value});
printf("put:%d\n",recent.front());
map[key] = recent.begin(); // 注意更新map中key的值
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

LFU Cache

LFU Cache是指,根据元素的使用频率,当元素超过容量上限时,优先删除使用频率最低的元素,如果有多个使用频率最低的元素,优先删除最近不使用的那个(这点和LRU Cache一致)。LFU Cache的put和get也可以做到O(1)复杂度,不过做法稍微复杂一些。

方法:首先因为要统计元素的使用频率,我们需要重新对node设计一个struct,包括其key, value, 频率freq以及指向链表的一个指针。我们采用两个hash table,第一个存储的是key和对应的node结构,第二个map存储了一个频率链表。即按照不同的使用频率进行划分,而之前提到的node指针就指向了该链表中的节点的位置。但我们put一个节点时,如果该节点已经存在,我们就会将其提升到频率+1的链表头,删去原来所在的链表位置。此外我们用一个min_freq_记录当前使用最少的节点的频率,当元素超过容量时,我们优先删去min_freq_对应的链表的尾,即实现了删除最低频率下最少使用的元素。

twoHash.png

该题逻辑比较复杂,在面试中常作为LRU的follow up,一般只要求回答具体使用的结构即可。

实现代码:

struct CacheNode {
int key;
int value;
int freq;
// 指向链表节点的指针
list<int>::const_iterator it;
};
class LFUCache {
private:
int capacity_;
int min_freq_;
// key -> CahceNode
unordered_map<int, CacheNode> n_; // 用于存储节点
unordered_map<int, list<int>> l_; // 用于查找使用频率
// touch方法用于更新节点的频率,并将node从原先的频率链表中提升到freq+1的频率链表
void touch(CacheNode& node) {
// Step 1: update the frequency
const int prev_freq = node.freq;
const int freq = ++(node.freq);
// Step 2: 在原先的链表中删除节点
l_[prev_freq].erase(node.it);
// Step 3: 如果原先频率的链表已经没有值并且是最小元素,则对min_freq_进行更新
if(l_[prev_freq].empty() && prev_freq == min_freq_) {
// Delete the list
l_.erase(prev_freq);
// Increase the min freq
++min_freq_;
}
// Step 4: 注意是在新的频率链表的头部进行插入
l_[freq].push_front(node.key);
// Step 5: 更新node的位置指针
node.it = l_[freq].cbegin();
}
public:
LFUCache(int capacity): capacity_(capacity), min_freq_(0) { }
int get(int key) {
auto it = n_.find(key);
if (it == n_.cend()) return -1;
touch(it->second); //更新node的链表位置提升频率
return it->second.value;
}
void put(int key, int value) {
if (capacity_ == 0) return;
auto it = n_.find(key);
if (it != n_.cend()) {
it->second.value = value; // same key, not the same value
touch(it->second);
return;
}
if (n_.size() == capacity_) {
// No capacity, need to remove one entry that
// 1. has the lowest freq
// 2. least recently used if there are multiple ones
// Step 1: remove the element from min_freq_ list
const int key_to_evict = l_[min_freq_].back();
l_[min_freq_].pop_back();
// Step 2: remove the key from cache
n_.erase(key_to_evict);
}
// 如果是新元素,freq则为1并更新min_freq_
const int freq = 1;
min_freq_ = freq;
// Add the key to the freq list
l_[freq].push_front(key);
// 更新hash table的位置
n_[key] = {key, value, freq, l_[freq].cbegin()};
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/