品牌高端网站制作官网,wordpress注册美化,php做的网站模板,杭州自助建站手撕LRU缓存_右大臣的博客-CSDN博客
是LRU的升级#xff0c;多了一个访问次数的维度 实现 LFUCache 类#xff1a;
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象int get(int key) - 如果键 key 存在于缓存中#xff0c;则获取键的值#xff0c;否则返…
手撕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 f1):key(k),value(v),frequency(f){}
};
class LFUCache {
private:int cap;int minfre;//最小的频率unordered_mapint,listNode::iteratormpkey;//用记录key -val 缓存unordered_mapint,listNodempfre;//记录频率访问次数的public:LFUCache(int capacity10) {cap capacity;minfre 1;mpkey.clear();mpfre.clear();}int get(int key) {//没有这个结点if(mpkey.count(key)0){return -1;}//有结点 保存结点信息auto itmpkey[key];//找到结点位置int fre1it-frequency;//找到对应的频率int valit-value;//开始操作记录频率的表了mpfre[fre1].erase(it);//删除这个频率链表上的结点if(mpfre[fre1].size()0){//删完如果他空了//就把这个链表给删了mpfre.erase(fre1);if(fre1minfre){//如果这个频率他刚好是最小的minfre;} } //把这个结点加到高频率的链表头mpfre[fre11].push_front(Node(key,val,fre11));//更新结点缓存表的指向mpkey[key]mpfre[fre11].begin();return mpkey[key]-value;}void put(int key, int value) {if(get(key)!-1){//有这个结点//get已经帮忙更新过了只需要把值改了就行mpkey[key]-valuevalue;}else{//没有这个结点需要新添加//看结点缓存满不满if(mpkey.size()cap){//根据LRU算法找到最小频率的尾巴的结点删除auto itmpfre[minfre].back();mpkey.erase(it.key);mpfre[minfre].pop_back();//如果删完 最小频率这个链表他空了if(mpfre[minfre].size()0){mpfre.erase(minfre);}}//添加 新添加的频率置为1int freque1;mpfre[freque].push_front(Node(key,value,freque));mpkey[key]mpfre[freque].begin(); //最小频率置为1minfre1;}}
};下面是我们自己实现的双向循环链表的写法代替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-nextvtail;vtail-prevvhead;}
};
有了基本结构就能实现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-nextvtail;vtail-prevvhead;}
};
class LFUCache {
private:int cap;int minfre;unordered_mapint,Node*keymp;unordered_mapint,List*fremp;
public:LFUCache(int capacity10):cap(capacity),minfre(1) {}bool empty(List *ls){return ls-vhead-nextls-vtail?true:false;}void destroy(Node*node){node-prev-nextnode-next;node-next-prevnode-prev;}void addNode(Node*node){int frenode-frequency;if(!fremp.count(fre)){ //如果结点不在fremp[fre]new List(fre); //创建一个新链表}List*lsfremp[fre];//开始插入结点node-nextls-vhead-next;ls-vhead-next-prevnode; node-prevls-vhead;ls-vhead-nextnode;}void popTail(){Node*tmpfremp[minfre]-vtail-prev;destroy(tmp);keymp.erase(tmp-key);}int get(int key) {if(keymp.count(key)){//存在Node*curkeymp[key];int valcur-value;int frecur-frequency;destroy(cur);//删完之后如果 链表空了那就删链表if(empty(fremp[fre])){fremp.erase(fre);if(freminfre){minfre;}}//加结点cur-frequency1;addNode(cur);return val;}return -1;}void put(int key, int value) {if(get(key)!-1){keymp[key]-valuevalue;}else{//满了没if(keymp.size()cap){popTail();}Node*curnew Node(key,value);keymp[key]cur;minfre1;addNode(cur);} }
};
