标签：nullptr span lru adl 代码 div 空间 public 记录
【题目】
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 3 #include 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_mapint, Node*>dataMap;//key 真实数据节点地址
50 hash_mapint, 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 get(4) endl;
178 f->set(4, 44);
179 cout get(1) endl;
180 cout get(2) endl;
181 cout get(2) endl;
182 cout get(2) endl;
183 cout get(3) endl;
184 cout get(3) endl;
185 cout get(4) endl;
186 cout get(4) endl;
187 cout get(4) endl;
188 f->set(5, 55);
189 cout get(3) endl;
190 cout get(5) endl;
191
192 }
左神算法进阶班6_1LFU缓存实现
标签：nullptr span lru adl 代码 div 空间 public 记录
原文地址：https://www.cnblogs.com/zzw1024/p/11080778.html