缓存管理算法LRU/LFU C++实现

本文主要是介绍缓存管理算法LRU/LFU C++实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Cache缓存管理算法：

详见(7条消息) 计组——彻底搞懂cache主存映射cache容量及cache写策略_vavid的专栏-CSDN博客_cache容量

LRU-Least  Recently Used

最常用的缓存管理算法，目标时间复杂度，查询=O(1)，添加=O(1)； 

实现方式：unordered_map<int,list<pair<int,int>>::iterator>M保存节点指针;List模拟缓存序列；

 1 class LRUCache {
 2 private:
 3 int cap;
 4 unordered_map<int,list<pair<int,int>>::iterator>M;
 5 list<pair<int,int>>L;
 6 public:
 7     LRUCache(int capacity) {
 8         cap=capacity;
 9     }
10     
11     int get(int key) {
12         auto p=M.find(key);
13         if(p==M.end()){
14             return -1;
15         }else{
16             L.splice(L.begin(),L,p->second);
17             auto x=M[key];
18             return x->second;
19         }
20     }
21     
22     void put(int key, int value) {
23         auto p=M.find(key);
24         if(p==M.end()){
25             L.push_front(make_pair(key,value));
26             M.insert(make_pair(key,L.begin()));
27             if(L.size()>cap){
28                 auto x=& L.back();
29                 M.erase(x->first);
30                 L.pop_back();
31             }
32         }else{
33             p->second->second=value;
34             L.splice(L.begin(),L,p->second);
35         }
36         return;
37     }
38 };

stl::list::splice()函数声明方式：

void splice(iterator position, list<T,Allocator>& x);  
void splice(iterator position, list<T,Allocator>& x, iterator it);
void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);

实现方式参考：https://blog.csdn.net/Wchenchen0/article/details/83058928

可以理解为earse+insert:

 1 class LRUCache {
 2 private:
 3 int cap;
 4 unordered_map<int,list<pair<int,int>>::iterator>M;
 5 list<pair<int,int>>L;
 6 public:
 7     LRUCache(int capacity) {
 8         cap=capacity;
 9     }
10     
11     int get(int key) {
12         auto p=M.find(key);
13         if(p==M.end()){
14             return -1;
15         }else{
16             L.splice(L.begin(),L,p->second);
17             auto x=*M[key];
18             return x.second;
19         }
20     }
21     
22     void put(int key, int value) {
23         auto p=M.find(key);
24         if(p==M.end()){
25             L.push_front(make_pair(key,value));
26             M.insert(make_pair(key,L.begin()));
27             if(L.size()>cap){
28                 M.erase(L.back().first);
29                 L.pop_back();
30             }
31         }else{
32             p->second->second=value;
33             L.splice(L.begin(),L,p->second);
34         }
35         return;
36     }
37 };

LFU-Least Frequently Used

不常见的缓存管理算法，对新数据不友好，目标时间复杂度：查询=O(1)，添加=O(1)； 

使用尽量清晰的存储结构，4种Map，分别以key，key出现频率为键，提供映射；其中unordered_map<int,list<int>>Freqlists存储的是相同出现频次的key链表，unordered_map<int,list<int>::iterator>Freq存储的是不同key的迭代器，即节点指针；注意Freq存放的迭代器指针指向的list节点与FreqLists并无对应分组关系。

关键条件：Freqlist刷新条件，最低使用频率key所在链表为空时，更新最小频次MinFreq

 1 class LFUCache {
 2 private:
 3 unordered_map<int,list<int>::iterator>Freq;//key->key lists iter
 4 unordered_map<int,list<int>>FreqLists;//freq->key lists 
 5 unordered_map<int,int>K;//key->freq
 6 unordered_map<int,int>M;//key->value
 7 int MinFreq=0;
 8 int cap;
 9 public:
10     LFUCache(int capacity) {
11         this->cap=capacity;
12     }
13     
14     int get(int key) {
15         auto p=M.find(key);
16         if(p==M.end()){
17             return -1;
18         }else{
19             FreqLists[K[key]].erase(Freq[key]);
20             if(FreqLists[MinFreq].size()==0)MinFreq++;// update 1
21             K[key]++;
22             FreqLists[K[key]].push_front(key);
23             Freq[key]=FreqLists[K[key]].begin();
24             return M[key];
25         }
26         return -1;
27     }
28     
29     void put(int key, int value) {
30         if(cap<=0)return;
31         auto p=M.find(key);
32         if(p==M.end()){
33             if(M.size()==cap){
34                 K.erase(FreqLists[MinFreq].back());
35                 M.erase(FreqLists[MinFreq].back());
36                 FreqLists[MinFreq].pop_back();
37             }
38             MinFreq=1;
39             M[key]=value;
40             K[key]=MinFreq;
41             FreqLists[MinFreq].push_front(key);
42             Freq[key]=FreqLists[MinFreq].begin();
43         }else{
44             M[key]=value;
45             FreqLists[K[key]].erase(Freq[key]);
46             if(FreqLists[MinFreq].size()==0)MinFreq++;// update 2
47             K[key]++;
48             FreqLists[K[key]].push_front(key);
49             Freq[key]=FreqLists[K[key]].begin();
50         }
51         return;
52     }
53 };

两大类缓存管理算法需要注意的点是先从List中更新目标节点位置，再根据新节点位置更新Map，否则会造成Map迭代器指向未分配节点地址。

这篇关于缓存管理算法LRU/LFU C++实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！