LFU和 LRU是两种典型的缓存页面置换算法，了解其底层以及运行机制是CSer的必修课。
缓存是计算机中广泛应用的一种技术，包括CPU L1/L2/L3 cache，RAM中的cache，网络协议tcp缓冲区，OS页面置换算法，redis缓存等等。需要形成对”缓存”的一个整体认识。
LRU(Least Recently Used)： 最近最久未使用算法，即最久不使用的元素最先淘汰。
_LFU(Least Frequently Used)：_最近最不频繁使用算法，即考虑访问次数，如果访问次数相同，考虑时间先后。
实际上，这两者都考虑的是 程序的局部性原理。
LRU：adopts ‘bidirectional list’ and ‘hash table’ technology
LFU：adopts double hash table and bidirectional list，
can also use hash table and rbtree(set), but the time complexity is O(logn).
1 /** 2 * author: ray' 3 * date: 2021/07/15 4 * contact: 2582171339@qq.com 5 * blog: https://www.cnblogs.com/rayss 6 * github: https://github.com/XuanRay 7 * 8 * description: LRU和LFU的实现 9 * LRU code copyed from "小林coding" 10 * LFU is coded by ray' 11 */ 12 13 #include14 #include 15 #include
16 #include <string> 17 18 // LRU：adopts 'bidirectional list' and 'hash table' technology 19 template 20 class LRUCache { 21 public: 22 typedef std::pair Pair; // using Pair = std::pair ,>; ,> 23 typedef std::listList; 24 typedef std::unordered_map uMap; 25 26 explicit LRUCache(int cap) : m_capacity(cap) {} 27 28 bool put(KeyT key, ValueT value); //add element to LRUCache 29 bool get(KeyT key, ValueT* pValue); //visit element in LRUCache 30 31 std::size_t size() const { 32 return m_capacity; 33 } 34 35 LRUCache(const LRUCache&) = delete; 36 LRUCache& operator=(const LRUCache&) = delete; 37 38 ~LRUCache() { 39 m_map.clear(); 40 m_list.clear(); 41 } 42 43 private: 44 std::size_t m_capacity; // list capacity 45 List m_list; // bidirectional list 46 uMap m_map; // hash table 47 }; 48 49 50 template ,>51 bool LRUCache ::put(KeyT key, ValueT value) { 52 // find key from hash table 53 typename uMap::iterator iter = m_map.find(key); 54 55 // if key is existed 56 if (iter != m_map.end()) { 57 // delete from bi-list and hash table 58 m_list.erase(iter->second); 59 m_map.erase(iter); 60 } 61 62 // insert the element into bi-list front and hash table 63 m_list.push_front(std::make_pair(key, value)); 64 m_map[key] = m_list.begin(); 65 66 // judge whether exceed capacity 67 if (m_list.size() > m_capacity) { 68 KeyT endKey = m_list.back().first; // unlike member list::end, which returns an iterator just past this element 69 // list::back returns a direct reference 70 m_list.pop_back(); 71 m_map.erase(endKey); 72 } 73 74 return true; 75 } 76 77 template ,>78 bool LRUCache ::get(KeyT key, ValueT* pvalue) { 79 // find whether key is in hash table 80 typename uMap::iterator mapIter = m_map.find(key); 81 if (mapIter == m_map.end()) { 82 return false; 83 } 84 85 // get bi-list node 86 typename List::iterator listIter = mapIter->second; 87 88 ValueT value = listIter->second; 89 90 // delete node from bi-list and insert into the front. 91 m_list.erase(listIter); //这个迭代器已经失效了，还能push_front? 迭代器失效问题 92 m_list.push_front(std::make_pair(key, value)); 93 94 // hash table changed 95 m_map[key] = m_list.begin(); 96 97 // save the value 98 *pvalue = value; 99 100 return true; 101 } 102 103 104 105 // FLU adopted double hash table and bidirectional list 106 107 // Node information 108 template ,>109 struct Node { 110 KeyT key; 111 ValueT value; 112 int freq; 113 114 Node(KeyT k, ValueT v, int f) : key(k), value(v), freq(f) {} 115 }; 116 117 // LFUCache 118 template 119 class LFUCache { 120 public: 121 typedef std::unordered_map<int, std::list >> Freq_Table; 122 typedef std::unordered_map >::iterator> Key_Table; 123 124 // ctor 125 LFUCache(int cap = 1) : m_minfreq(0), m_capacity(cap) {} 126 127 // put and get 128 bool get(KeyT key, ValueT* pValue); 129 bool put(KeyT key, ValueT value); 130 131 std::size_t get_MinFreq() const { 132 return this->m_minfreq; 133 } 134 135 std::size_t get_Capacity() const { 136 return this->m_capacity; 137 } 138 139 // dtor 140 ~LFUCache() { 141 m_freqTable.clear(); 142 m_keyTable.clear(); 143 } 144 145 private: 146 std::size_t m_minfreq; 147 std::size_t m_capacity; 148 Freq_Table m_freqTable; 149 Key_Table m_keyTable; 150 }; 151 152 template ,>153 bool LFUCache ::get(KeyT key, ValueT* pValue) { 154 // find whether key is in key hash table 155 auto iter = m_keyTable.find(key); 156 if (iter == m_keyTable.end()) { 157 return false; 158 } 159 160 typename std::list >::iterator node = iter->second; 161 *pValue = node->value; 162 int freq = node->freq; 163 164 // delete this node 165 m_freqTable[freq].erase(node); 166 167 // if current list is NULL, delete it from freq hash table 168 if (m_freqTable[freq].size() == 0) { 169 m_freqTable.erase(freq); 170 if (m_minfreq == freq) { 171 m_minfreq += 1; 172 } 173 } 174 175 // insert the node to freq + 1 list 176 m_freqTable[freq + 1].push_front(Node (key, *pValue, freq + 1)); 177 178 //m_freqTable[freq + 1].push_front(new Node ,>(key, val, freq + 1)); ,> 179 m_keyTable[key] = m_freqTable[freq + 1].begin(); 180 181 return true; 182 } 183 184 template185 bool LFUCache ::put(KeyT key, ValueT value) { 186 typename Key_Table::iterator iter = this->m_keyTable.find(key); 187 188 // if key is not found in key hash table 189 if (iter == m_keyTable.end()) { 190 // if full 191 if (m_capacity == m_keyTable.size()) { 192 auto it = m_freqTable[m_minfreq].back(); // list的back()返回的是reference 193 m_keyTable.erase(it.key); 194 m_freqTable[m_minfreq].pop_back(); 195 if (m_freqTable[m_minfreq].size() == 0) { 196 m_freqTable.erase(m_minfreq); 197 } 198 } 199 m_freqTable[1].push_front(Node ,>(key, value, 1)); 200 m_keyTable[key] = m_freqTable[1].begin(); 201 m_minfreq = 1; 202 } 203 else { // otherwise 204 auto node = iter->second; 205 int freq = node->freq; 206 m_freqTable[freq].erase(node); 207 if (m_freqTable[freq].size() == 0) { 208 m_freqTable.erase(freq); 209 if (m_minfreq == freq) { 210 m_minfreq += 1; 211 } 212 } 213 m_freqTable[freq + 1].push_front(Node ,>(key, value, freq + 1)); 214 m_keyTable[key] = m_freqTable[freq + 1].begin(); 215 } 216 217 return true; 218 } 219 220 221 222 // test LRU 223 void testLRU() { 224 LRUCache<int, std::string> lruCache(3); 225 226 lruCache.put(1, "r"); 227 lruCache.put(2, "a"); 228 lruCache.put(3, "y"); 229 230 std::string value; 231 bool ret = true; 232 233 ret = lruCache.get(1, &value); 234 std::cout << "value = " << value << ", ret = " << ret << "\n"; 235 236 lruCache.put(4, "'"); 237 value = ""; 238 ret = lruCache.get(2, &value); 239 std::cout << "value = " << value << ", ret = " << ret << "\n"; 240 } 241 242 void testLFU() { 243 LFUCache<int, std::string> lfuCache(3); 244 lfuCache.put(1, "r"); 245 lfuCache.put(2, "a"); 246 lfuCache.put(3, "y"); 247 248 std::string value; 249 bool ret = true; 250 251 ret = lfuCache.get(1, &value); 252 std::cout << "value = " << value << ", ret = " << ret << "\n"; 253 254 value = ""; 255 ret = lfuCache.get(2, &value); 256 std::cout << "value = " << value << ", ret = " << ret << "\n"; 257 258 lfuCache.put(4, "s"); 259 260 value = ""; 261 ret = lfuCache.get(3, &value); 262 std::cout << "value = " << value << ", ret = " << ret << "\n"; 263 } 264 265 266 // test LRU and LFU 267 int main() { 268 testLRU(); 269 270 std::cout << "\n\n"; 271 std::cout << "----------------------------------------------\n\n"; 272 273 testLFU(); 274 275 system("pause"); 276 return 0; 277 } ,>,>
Original: https://www.cnblogs.com/rayss/p/15019245.html
Author: Ray-ss
Title: LRU和LFU的实现
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587818/
转载文章受原作者版权保护。转载请注明原作者出处！