题解 | #LFU缓存结构设计#
LFU缓存结构设计
http://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1
NC94 LFU缓存结构设计
题目描述
一个缓存结构需要实现如下功能。
- set(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值, 但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出
1. 哈希表+平衡树
方法一用到的是平衡二叉树， 在c++中可以使用stl的set，Java中可以使用TreeSet,其底层都是红黑树。（什么，你是py选手？手撕吧）本文以C++为例叙述下面的解决方法。
1.1 定义数据结构
因为这里不光有k，v，还要维护进入的时间（版本号）和频率，因此我们需要这样定义每个kv组，称为节点Node：
struct Node {
int freq; // 频率
int time; // 插入时间
int key, value;
// 重载比较方法，以频率为第一关键字，插入时间为第二关键字
bool operator< (const Node& p) const {
return p.freq == freq ? time < p.time : freq < p.freq;
}
}
这里，我们需要两个数据结构，一个是哈希表key_map，用来维护每个key对应的节点，一个是平衡树rb_tree维护node的顺序。 最后还需要记录下容量和时间戳。
unordered_map<int, Node> key_map;
set<Node> rb_tree;
int capacity, timestamp;
1.2 get、set操作
对于get操作，我们先从key_map里找到对应的节点，再c从rb_tree中取出并删掉，更新它的time和freq再放回去。
对于set操作，我们从key_map里找到对应的节点，如果有，则跟get差不太多，区别是需要更新value,如果没有，则插入缓存，这时候需要看整个cache是不是满了，如果满了，则进入淘汰策略。
淘汰策略，根据题意就是，最近最少使用的，其实按我们的Node的排序方案，就等价于平衡树里最小的节点，我们去掉这个点就好了。
class Solution {
public:
/**
* lfu design
* @param operators int整型vector<vector<>> ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> LFU(vector<vector<int> >& operators, int k) {
// write code here
init_lfu(k);
vector<int> res;
for (auto vec : operators) {
int opt = vec[0], x, y;
if (opt == 1) {
x = vec[1], y = vec[2];
set(x, y);
} else if (opt == 2) {
x = vec[1];
res.push_back(get(x));
}
}
return res;
}
private:
typedef struct Node{
int freq; // 频率
int time; // 插入时间
int key, value;
// 重载比较方法，以频率为第一关键字，插入时间为第二关键字
bool operator< (const Node& p) const {
return p.freq == freq ? time < p.time : freq < p.freq;
}
} Node;
unordered_map<int, Node> key_map;
set<Node> rb_tree;
int capacity, timestamp;
void init_lfu(int _capacity) {
capacity = _capacity;
timestamp = 1;
}
int get(int key) {
auto val_iterator = key_map.find(key);
// 如果没有
if (val_iterator == key_map.end()) return -1;
Node node = val_iterator->second;
rb_tree.erase(node);
node.freq++;
node.time = timestamp++;
rb_tree.insert(node);
key_map[node.key] = node;
return node.value;
}
void set(int key, int val) {
auto val_iterator = key_map.find(key);
// 没有
if (val_iterator == key_map.end()) {
// 缓存满
if (key_map.size() == capacity) {
// 淘汰
auto temp = rb_tree.begin();
// 这里的temp是迭代器
key_map.erase(temp->key);
rb_tree.erase(temp);
}
// 创建新Node
Node new_node{1, timestamp++, key, val};
// 装进两个结构
rb_tree.insert(new_node);
key_map[key] = new_node;
} else {
// 有，取出来，更新，再装回去
Node node = val_iterator->second;
rb_tree.erase(node);
node.freq++;
node.time = timestamp++;
node.value = val;
key_map[node.key] = node;
rb_tree.insert(node);
}
}
};
- 时间复杂度: O(qlogn), 假设有q次操作，每次操作都只涉及平衡树的增删，平衡树的复杂度均为O(logn).哈希表可近似看做O(1)
- 空间复杂度: O(K). 整个结构的最大容量为K。
2. 两个哈希表
本题还可以有一种O(1)的方法，是在论文An O(1) algorithm for implementing the LFU cache eviction scheme中介绍的。
Node跟思路一接近，但是不需要time，也不需要比较，我们再定义两个哈希表。哈希表的value是双端链表，在c++中用list
unordered_map<int, list<Node>::iterator> key_map;
unordered_map<int, list<Node>> freq_map;
int min_freq, capacity;
其中freq_map维护每个频率下，节点的双端链表，key_map维护每个key对应的节点在freq_map中位置的迭代器。
对于get操作，我们先在key_map找到这个key在freq_map的地址，如果找到了，则把它从freq_map的freq这条链表删掉，再装到freq+1这条链表的头部，加到头部的原因是保证时间有序。
对于set操作，如果找到了，跟思路1和思路2的get操作差不多。如果没有，需要删除。
删除操作我们由于维护了min_freq，就可以找到去哪条链表里面删除，而且我们知道每条链表都是根据时间戳有序的，故删掉链表尾部即可。
对于新增操作，我们同时更新min_freq=1。
class Solution {
public:
/**
* lfu design
* @param operators int整型vector<vector<>> ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> LFU(vector<vector<int> >& operators, int k) {
// write code here
init_lfu(k);
vector<int> res;
for (auto vec : operators) {
int opt = vec[0], x, y;
if (opt == 1) {
x = vec[1], y = vec[2];
set(x, y);
} else if (opt == 2) {
x = vec[1];
res.push_back(get(x));
}
}
return res;
}
private:
typedef struct Node{
int freq; // 频率
int key, value;
} Node;
unordered_map<int, list<Node>::iterator> key_map;
unordered_map<int, list<Node>> freq_map;
int min_freq, capacity;
void init_lfu(int _capacity) {
capacity = _capacity;
min_freq = 0;
}
int get(int key) {
auto val_iterator = key_map.find(key);
// 如果没有
if (val_iterator == key_map.end()) return -1;
auto node = val_iterator->second;
int val = node->value, freq = node->freq;
freq_map[freq].erase(node);
if (freq_map[freq].size() == 0) {
freq_map.erase(freq);
if (min_freq == freq)
min_freq++;
}
freq_map[freq+1].push_front(Node{freq+1, key, val});
key_map[key] = freq_map[freq+1].begin();
return val;
}
void set(int key, int val) {
auto val_iterator = key_map.find(key);
// 没有
if (val_iterator == key_map.end()) {
// 缓存满
if (key_map.size() == capacity) {
// 拿min_freq那条链表的最后一个节点
auto min_freq_last_node_iterator = freq_map[min_freq].back();
key_map.erase(min_freq_last_node_iterator.key);
freq_map[min_freq].pop_back();
if (freq_map[min_freq].size() == 0)
freq_map.erase(min_freq);
}
Node node = Node{1, key, val};
freq_map[1].push_front(node);
key_map[key] = freq_map[1].begin();
min_freq = 1;
} else {
// 有，取出来，更新，再装回去
auto node_iterator = val_iterator->second;
int freq = node_iterator->freq;
freq_map[freq].erase(node_iterator);
if (freq_map[freq].size() == 0) {
freq_map.erase(freq);
if (min_freq == freq)
min_freq++;
}
freq_map[freq+1].push_front(Node{freq+1, key, val});
key_map[key] = freq_map[freq+1].begin();
}
}
};
- 时间复杂度: O(q), 假设有q次操作，每次操作都只涉及哈希表和链表操作，可近似为O(1)。
- 空间复杂度: O(K). 整个结构的最大容量为K。
