左神算法进阶班6_1LFU缓存实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了左神算法进阶班6_1LFU缓存实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6212字，纯文字阅读大概需要9分钟。

内容图文

【题目】

LFU也是一个著名的缓存算法,自行了解之后实现LFU中的set 和 get

要求：两个方法的时间复杂度都为O(1)

【题解】

LFU算法与LRU算法很像

但LRU是最新使用的排在使用频率最前面，也就是LRU是通过使用时间进行排序，

使用时间越新，其使用频率越高，而使用时间越久，其使用频率越低，即当空间满时，被删除的概率最大

而LFU是根据使用次数来算使用频率的，使用次数越多，其使用频率越高，使用次数越少，使用频率越低，当空间满时越容易被删除

同样，使用hash_map表和双向链表进行存储；

hash表存储关键词与双向链表的节点地址

而双向链表的数据存储的是使用次数，每种使用次数仍然是一个双向链表，

当put一个数据，则在使用次数为1的链表节点下的链表中按put顺序依次存储

当每get一个数据，若存在，而在相对应使用次数的链表节点中拿出，放在下一个链表节点下，即使用次数 + 1的节点

记住，在相同的使用次数中，是按照使用时间顺序进行存放的，

所以，当空间满时，首先删除大链表的头中的头，即使用次数为1的节点中的头结点【最早放入】，若使用次数都一样，同样是删除该使用次数节点中链表的 头节点

所以，数据存放于链表尾部，数据删除于链表的头部

还有，当某个链表节点为空，则删除，某个链表节点不存在，则新建

比如，当使用次数为2的节点中无数据，则删出该节点，

当有一个新数据的使用次数为2时，发现不存在使用次数为2的节点，那么就应该新建一个节点

 

【代码】

　　

  1 #pragma once
  2 #include <iostream>
  3 #include <hash_map>
  4 
  5 using namespace std;
  6 
  7 struct Node//子链表
  8 {
  9     int key;
 10     int val;
 11     int num;
 12     Node* next;
 13     Node* pre;
 14     Node(int a, int b, int n) :key(a), val(b), num(n), next(nullptr), pre(nullptr) {}
 15 };
 16 
 17 struct NodeList//主链表
 18 {
 19     int num;
 20     Node* head;//子链表的头节点
 21     Node* tail;//子链表的尾结点
 22     NodeList* next;
 23     NodeList* pre;
 24     NodeList(int a) :num(a), next(nullptr), pre(nullptr)
 25     {
 26         head = new Node(0, 0, a);//新建一个子链表的头结点
 27         tail = head;
 28     }
 29 };
 30 
 31 class LFU
 32 {
 33 public:
 34     LFU(int size) :capacity(size) {}
 35     void set(int key, int value);
 36     int get(int key);
 37     
 38 private:
 39     void getNode(Node*& p, NodeList*& h);//将节点从子链表中取出
 40     void moveNode(Node*& p, NodeList*& h);//将节点向后移动
 41     void deleteNode(int num, NodeList*& h);//删除子链表
 42     void createNode(Node*p, NodeList*& h);//新建子链表,并插入在主链中
 43     void updataNode(Node*& p, NodeList*& h);//更新函数的使用次数
 44     void deleteData();//容量不足需要删除
 45 
 46 private:
 47     int capacity;
 48     NodeList* headList = new NodeList(0);//主链表的头结点
 49     hash_map<int, Node*>dataMap;//key  <——>  真实数据节点地址
 50     hash_map<int, NodeList*>headMap;//次数 <——>  链表头节点地址
 51 };
 52 
 53 void LFU::set(int key, int value)
 54 {
 55     if (this->capacity == 0)
 56         return;
 57     if (dataMap.find(key) != dataMap.end())//已经存在
 58     {
 59         Node* p = dataMap[key];//找到数据节点
 60         NodeList* h = headMap[p->num];//找到头链表节点        
 61         p->val = value;
 62 
 63         updataNode(p, h);//更新数据的使用次数        
 64     }
 65     else//如果不存在，则新建
 66     {
 67         if (dataMap.size() >= this->capacity)//容量不足，需要删除数据
 68             deleteData();
 69 
 70         Node* p = new Node(key, value, 1);//使用用一次
 71         dataMap[key] = p;//记录
 72 
 73         //将新建节点插入使用1次的子链表中
 74         if (headMap.find(1) == headMap.end())//当使用1次的子链表不存在
 75             createNode(p, headList);
 76         else
 77             moveNode(p, headMap[1]);//插入在使用次数在1的子链表中
 78     }
 79 }
 80 
 81 int LFU::get(int key)
 82 {
 83     if (dataMap.find(key) == dataMap.end())//数据不存在
 84         return -1;
 85     Node* p = dataMap[key];//找到数据节点
 86     NodeList* h = headMap[p->num];
 87     updataNode(p, h);
 88 
 89     return p->val;
 90 }
 91 
 92 void LFU::getNode(Node*& p, NodeList*& h)//将节点从子链表中取出
 93 {
 94     p->pre->next = p->next;
 95     if (p->next == nullptr)
 96         h->tail = p->pre;
 97     else
 98         p->next->pre = p->pre;
 99 }
100 
101 void LFU::moveNode(Node*& p, NodeList*& q)//将节点向后移动
102 {
103     p->next = q->tail->next;
104     q->tail->next = p;
105     p->pre = q->tail;
106     q->tail = p;
107 }
108 
109 void LFU::deleteNode(int num, NodeList*& h)//删除子链表
110 {
111     headMap.erase(num);//从map中删除
112     h->pre->next = h->next;
113     if (h->next != nullptr)
114         h->next->pre = h->pre;
115     delete h;
116     h = nullptr;
117 }
118 
119 
120 void LFU::createNode(Node*p, NodeList*& h)//新建子链表,并插入在主链中
121 {
122     NodeList* q = new NodeList(p->num);//新建一个子链表
123     headMap[p->num] = q;//保存对应的地址
124 
125     moveNode(p, q);////将节点放入子链表中        
126 
127     //将新子链插入主链表中
128     q->next = h->next;
129     if (h->next != nullptr)
130         h->next->pre = q;
131     h->next = q;
132     q->pre = h;
133 }
134 
135 void LFU::updataNode(Node*& p, NodeList*& h)//更新函数的使用次数
136 {
137     int num = p->num;
138     p->num++;//使用次数+1
139 
140     //将p从子链表中取出
141     getNode(p, h);
142 
143     //将该数据向后面移动
144     if (headMap.find(p->num) == headMap.end())//不存在num+1的节点,那么新建
145         createNode(p, h);
146     else
147         moveNode(p, headMap[p->num]);////将节点放入子链表中    
148 
149     //如果该子链表为空，将该子链表删除,并从map中删除
150     if (h->head == h->tail)
151         deleteNode(num, h);
152 }
153 
154 void LFU::deleteData()//容量不足需要删除
155 {
156     NodeList* p = headList->next;
157     Node* q = p->head->next;//删除子链表排在最前面的数据
158     if (q == p->tail)//要删除的数据就是最后一个数据，则删除该节点和子链表
159         deleteNode(q->num, p);
160     else
161     {
162         p->head->next = q->next;
163         q->next->pre = p->head;
164     }
165     dataMap.erase(q->key);//删除记录
166     delete q;//删除
167     q = nullptr;
168 }
169 
170 
171 void Test()
172 {
173     LFU* f = new LFU(3);
174     f->set(1, 11);
175     f->set(2, 22);
176     f->set(3, 33);
177     cout << f->get(4) << endl;
178     f->set(4, 44);
179     cout << f->get(1) << endl;
180     cout << f->get(2) << endl;
181     cout << f->get(2) << endl;
182     cout << f->get(2) << endl;
183     cout << f->get(3) << endl;
184     cout << f->get(3) << endl;
185     cout << f->get(4) << endl;
186     cout << f->get(4) << endl;
187     cout << f->get(4) << endl;
188     f->set(5, 55);
189     cout << f->get(3) << endl;
190     cout << f->get(5) << endl;
191 
192 }

 

内容总结

以上是互联网集市为您收集整理的左神算法进阶班6_1LFU缓存实现全部内容，希望文章能够帮你解决左神算法进阶班6_1LFU缓存实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---