手撕LRU緩存_右大臣的博客-CSDN博客
是LRU的升級，多了一個訪問次數的維度
實現?LFUCache?類：
LFUCache(int capacity)?- 用數據結構的容量?capacity?初始化對象int get(int key)?- 如果鍵?key?存在于緩存中，則獲取鍵的值，否則返回?-1?。void put(int key, int value)?- 如果鍵?key?已存在，則變更其值；如果鍵不存在，請插入鍵值對。當緩存達到其容量?capacity?時，則應該在插入新項之前，移除最不經常使用的項。在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除?最近最久未使用?的鍵。
為了確定最不常使用的鍵，可以為緩存中的每個鍵維護一個?使用計數器?。使用計數最小的鍵是最久未使用的鍵。
當一個鍵首次插入到緩存中時，它的使用計數器被設置為?1?(由于 put 操作)。對緩存中的鍵執行?get?或?put?操作，使用計數器的值將會遞增。
函數?get?和?put?必須以?O(1)?的平均時間復雜度運行。
LRU的實現是一個哈希表加上一個雙鏈表
而LFU則要復雜多了，需要用兩個哈希表再加上N個雙鏈表才能實現
LFU需要為每一個頻率構造一個雙向鏈表
460. LFU 緩存 - 力扣（LeetCode）? 一個邏輯講解
總的來說就是下圖這樣：
?所以針對LRU的模仿寫法，我就直接用STL的list去做
因為LFU多了頻率，所以需要重構結點，，就不像LRU那個一樣用pair對組了
//因為多了頻率，所以重構結點，，就不像LRU那個一樣用pair對組了
struct Node
{int key;int value;int frequency;Node(int k,int v,int f=1):key(k),value(v),frequency(f){}
};
class LFUCache {
private:int cap;int minfre;//最小的頻率unordered_map<int,list<Node>::iterator>mpkey;//用記錄key -val 緩存unordered_map<int,list<Node>>mpfre;//記錄頻率訪問次數的public:LFUCache(int capacity=10) {cap = capacity;minfre = 1;mpkey.clear();mpfre.clear();}int get(int key) {//沒有這個結點if(mpkey.count(key)==0){return -1;}//有結點 ，保存結點信息auto it=mpkey[key];//找到結點位置int fre1=it->frequency;//找到對應的頻率int val=it->value;//開始操作記錄頻率的表了mpfre[fre1].erase(it);//刪除這個頻率鏈表上的結點if(mpfre[fre1].size()==0){//刪完如果他空了//就把這個鏈表給刪了mpfre.erase(fre1);if(fre1==minfre){//如果這個頻率他剛好是最小的minfre++;} } //把這個結點加到高頻率的鏈表頭mpfre[fre1+1].push_front(Node(key,val,fre1+1));//更新結點緩存表的指向mpkey[key]=mpfre[fre1+1].begin();return mpkey[key]->value;}void put(int key, int value) {if(get(key)!=-1){//有這個結點//get已經幫忙更新過了，只需要把值改了就行mpkey[key]->value=value;}else{//沒有這個結點，需要新添加//看結點緩存滿不滿if(mpkey.size()==cap){//根據LRU算法，找到最小頻率的尾巴的結點，刪除auto it=mpfre[minfre].back();mpkey.erase(it.key);mpfre[minfre].pop_back();//如果刪完 最小頻率這個鏈表他空了if(mpfre[minfre].size()==0){mpfre.erase(minfre);}}//添加 新添加的頻率置為1int freque=1;mpfre[freque].push_front(Node(key,value,freque));mpkey[key]=mpfre[freque].begin(); //最小頻率置為1minfre=1;}}
};
下面是我們自己實現的雙向循環鏈表的寫法，代替list
構建結點和鏈表
為了方便操作，給雙向鏈表加上了虛擬的頭結點和尾結點，并在初始化的時候首尾相接。
struct Node
{int key;int value;int frequency;Node*prev;Node*next;Node():key(-1),value(-1),frequency(0),prev(nullptr),next(nullptr){}Node(int k,int v):key(k),value(v),frequency(1),prev(nullptr),next(nullptr){}
};
struct List//雙向鏈表
{int frequency;//虛擬 頭 尾 結點Node*vhead;Node*vtail;List(int f):frequency(f),vhead(new Node()),vtail(new Node()){vhead->next=vtail;vtail->prev=vhead;}
};有了基本結構就能實現LFU以及自己手撕鏈表的一些簡單操作
這里需要用到的有，插入，刪除結點，以及鏈表判空，和返回鏈表最后一個尾結點
struct Node
{int key;int value;int frequency;Node*prev;Node*next;Node():key(-1),value(-1),frequency(0),prev(nullptr),next(nullptr){}Node(int k,int v):key(k),value(v),frequency(1),prev(nullptr),next(nullptr){}
};
struct List//雙向鏈表
{int frequency;//虛擬 頭 尾 結點Node*vhead;Node*vtail;List(int f):frequency(f),vhead(new Node()),vtail(new Node()){vhead->next=vtail;vtail->prev=vhead;}
};
class LFUCache {
private:int cap;int minfre;unordered_map<int,Node*>keymp;unordered_map<int,List*>fremp;
public:LFUCache(int capacity=10):cap(capacity),minfre(1) {}bool empty(List *ls){return ls->vhead->next==ls->vtail?true:false;}void destroy(Node*node){node->prev->next=node->next;node->next->prev=node->prev;}void addNode(Node*node){int fre=node->frequency;if(!fremp.count(fre)){ //如果結點不在fremp[fre]=new List(fre); //創建一個新鏈表}List*ls=fremp[fre];//開始插入結點node->next=ls->vhead->next;ls->vhead->next->prev=node; node->prev=ls->vhead;ls->vhead->next=node;}void popTail(){Node*tmp=fremp[minfre]->vtail->prev;destroy(tmp);keymp.erase(tmp->key);}int get(int key) {if(keymp.count(key)){//存在Node*cur=keymp[key];int val=cur->value;int fre=cur->frequency;destroy(cur);//刪完之后如果 鏈表空了，那就刪鏈表if(empty(fremp[fre])){fremp.erase(fre);if(fre==minfre){minfre++;}}//加結點cur->frequency+=1;addNode(cur);return val;}return -1;}void put(int key, int value) {if(get(key)!=-1){keymp[key]->value=value;}else{//滿了沒if(keymp.size()==cap){popTail();}Node*cur=new Node(key,value);keymp[key]=cur;minfre=1;addNode(cur);} }
};
