赞
踩
LFU全称是最不经常使用算法(Least Frequently Used),LFU算法的基本思想和所有的缓存算法一样,一定时期内被访问次数最少的页,在将来被访问到的几率也是最小的。
相较于 LRU 算法,LFU 更加注重于使用的频率。 LRU 其实可以看作是频率为 1 的LFU。
从上图中我们可以看到,LFU是根据频率来进行排序,当我们插入的时候,会把新插入的放到链表的尾部,因为新插入的一定没有出现过的,所以频率都会是1,所以会放在最后。
整个算法流程如下:
整体算法如下:
根据题目中的描述,我们除了维护一个键值对之外,还要为这个键值对维护一个计数器:
struct Node {
int key, value, freq;
Node() : key(0), value(0), freq(1) {}
Node(int key, int value) : key(key), value(value), freq(1) {}
};
很明显,除了 LFUCache 的容量之外,我们还要维护一个最小频率,到时候清除缓存是清除最小频率的最久未使用:
class LFUCache {
private:
int capacity_, minFreq_;
std::unordered_map<int, Node*> keyNode_; //从键到节点的映射
std::unordered_map<int, std::list<Node*>> freqList_; //从频率到节点链表的映射
std::unordered_map<Node*, std::list<Node*>::iterator> nodeIter_; //从节点到其在列表中位置的映射
};
这里我们需要一个私有成员函数,也就是更新频率的函数,其实逻辑还是比较好理解的。
void updateFrequency(Node* node) {
int freq = node->freq;
auto& nodeList = freqList_[freq]; //获取该频率对应的节点链表
nodeList.erase(nodeIter_[node]); // 从该链表中删除该节点,因为该节点的频率注定被改变了
// 如果当前频率的节点链表为空,删除该频率并更新最小频率
if (nodeList.empty()) {
freqList_.erase(freq);
if (minFreq_ == freq) minFreq_++; //当前删除的频率链表为最小频率时,更新最小频率
}
//增加节点的频率,并将其插入到新的频率-节点链表的最前面
node->freq++;
freqList_[node->freq].push_front(node);
nodeIter_[node] = freqList_[node->freq].begin(); //记录每个节点在各自链表中的位置
}
class LFUCache {
private:
...
public:
LFUCache(int capacity) : capacity_(capacity), minFreq_(0) {}
};
// 获取指定键的值
int get(int key) {
if (keyNode_.find(key) == keyNode_.end()) {
return -1;
} else {
Node* node = keyNode_[key];
updateFrequency(node);
return node->value;
}
}
//插入或更新键值对 void put(int key, int value) { if (capacity_ == 0) return; //容量为0,直接返回 // 更新值、更新频率 if (keyNode_.find(key) != keyNode_.end()) { Node* node = keyNode_[key]; node->value = value; updateFrequency(node); } else { // 容量已满 if (keyNode_.size() == capacity_) { auto& nodeList = freqList_[minFreq_]; //找到最小频率的那个 nodelist Node* node = nodeList.back(); //最小频率的最久未使用节点 keyNode_.erase(node->key); //从键到节点的映射中删除该节点 nodeIter_.erase(node); // 从节点到其所属位置映射中删除该节点 nodeList.pop_back(); //从获取到的频率链表中删除该节点 if (nodeList.empty()) freqList_.erase(minFreq_); //如果频率列表为空,删除该频率链表 delete node; } //如果缓存未满的情况下,插入新节点并更新相关映射 Node* newNode = new Node(key, value); keyNode_[key] = newNode; freqList_[1].push_front(newNode); nodeIter_[newNode] = freqList_[1].begin(); minFreq_ = 1; //重置最小频率 } }
struct Node { int key, value, freq; Node() : key(0), value(0), freq(1) {} Node(int key, int value) : key(key), value(value), freq(1) {} }; class LFUCache { private: int capacity_, minFreq_; std::unordered_map<int, Node*> keyNode_; //从键到节点的映射 std::unordered_map<int, std::list<Node*>> freqList_; //从频率到节点链表的映射 std::unordered_map<Node*, std::list<Node*>::iterator> nodeIter_; //从节点到其在列表中位置的映射 // 无论使用 get 还是 put 方法都会导致节点频率的增加 void updateFrequency(Node* node) { int freq = node->freq; auto& nodeList = freqList_[freq]; //获取该频率对应的节点链表 nodeList.erase(nodeIter_[node]); // 从该链表中删除该节点,因为该节点的频率注定被改变了 // 如果当前频率的节点链表为空,删除该频率并更新最小频率 if (nodeList.empty()) { freqList_.erase(freq); if (minFreq_ == freq) minFreq_++; //当前删除的频率链表为最小频率时,更新最小频率 } //增加节点的频率,并将其插入到新的频率-节点链表的最前面 node->freq++; freqList_[node->freq].push_front(node); nodeIter_[node] = freqList_[node->freq].begin(); //记录每个节点在各自链表中的位置 } public: LFUCache(int capacity) : capacity_(capacity), minFreq_(0) {} int get(int key) { if (keyNode_.find(key) == keyNode_.end()) { return -1; } else { Node* node = keyNode_[key]; updateFrequency(node); return node->value; } } void put(int key, int value) { if (capacity_ == 0) return; //容量为0,直接返回 // 更新值、更新频率 if (keyNode_.find(key) != keyNode_.end()) { Node* node = keyNode_[key]; node->value = value; updateFrequency(node); } else { // 容量已满 if (keyNode_.size() == capacity_) { auto& nodeList = freqList_[minFreq_]; //找到最小频率的那个 nodelist Node* node = nodeList.back(); //最小频率的最久未使用节点 keyNode_.erase(node->key); //从键到节点的映射中删除该节点 nodeIter_.erase(node); // 从节点到其所属位置映射中删除该节点 nodeList.pop_back(); //从获取到的频率链表中删除该节点 if (nodeList.empty()) freqList_.erase(minFreq_); //如果频率列表为空,删除该频率链表 delete node; } //如果缓存未满的情况下,插入新节点并更新相关映射 Node* newNode = new Node(key, value); keyNode_[key] = newNode; freqList_[1].push_front(newNode); nodeIter_[newNode] = freqList_[1].begin(); minFreq_ = 1; //重置最小频率 } } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。