来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
设计并实现最不经常使用(LFU)缓存的数据结构。它应该支持以下操作:get
和put
。
get(key)
- 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。put(key, value)
- 如果键不存在,请设置或插入值。当缓存达到其容量时,它应该在插入新项目之前,使最不经常使用的项目无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,最近最少使用的键将被去除。
进阶:
你是否可以在 O(1) 时间复杂度内执行两项操作?
示例:
1 2 3 4 5 6 7 8 9 10 11 12 |
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4 |
二、题目解析
LFU算法是LRU算法的改进版本,LRU算法强调最近最少使用,逐步淘汰掉很久没有使用的缓存。而LFU在LRU的基础上引入了使用频率限制,优先使用频率来淘汰缓存。在频率同等的情况下,再通过LRU淘汰较久没有使用的。
虽然只是增加了一个维度的判断,但是在逻辑和编码上,多出来的麻烦就不止一个档次了。因为题目要求在O(1)
的时间复杂度内完成两项操作。对于get
操作而言,如果使用哈希表来保存所有的缓存节点,可以在O(1)
的时间复杂度完成。但是对于put
操作来说,想要把它在O(1)
的时间复杂度内插入,就不简单了,必须要有合适的数据结构来支撑才行,因为除了保存频次以外还有记录节点的使用时间。如果像LRU一样使用链表来存,每个缓存节点都要先找到合适的位置才能插入,时间复杂度是O(n)
。
这里可以采取的方式是使用两个哈希表来保存所有的节点,其中一个以缓存的key值作为哈希表的key,另外一个以缓存出现的频率作为哈希表的key。假设保存所有缓存节点的哈希表为cache
,保存频率的哈希表为freq
,那么它的操作逻辑为:
三、代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
// 缓存节点 struct cacheNode { int key, val, freq; // 键 }; class LFUCache { private: unordered_map<int, list<cacheNode *>> freq; // 保存所有频次的节点 unordered_map<int, cacheNode *> cache; // 保存所有的缓存节点 int min; // 出现最小的频次 int capacity; // 容量 int size; // 大小 void incrFreq(unordered_map<int, cacheNode *>::iterator &itCache) { cacheNode *node; unordered_map<int, list<cacheNode *> >::iterator itFreq; node = itCache->second; // 找到对应频率的链表 itFreq = freq.find(node->freq); if (itFreq == freq.end()) throw logic_error("unexpect error: cannot file list in freq map"); // 从当前链表移除 itFreq->second.remove(node); if (itFreq->second.empty()) { freq.erase(node->freq); // 当前删除的节点是最小频率节点 if (node->freq == min) min++; } // 增加频率 node->freq++; itFreq = freq.find(node->freq); if (itFreq == freq.end()) { freq.insert(pair<int, list<cacheNode *>>(node->freq, list<cacheNode *>())); itFreq = freq.find(node->freq); } itFreq->second.push_front(node); } // 添加新节点 void putNewNode(int key, int value) { cacheNode *node, *p; unordered_map<int, cacheNode *>::iterator itCache; unordered_map<int, list<cacheNode *> >::iterator itFreq; if (this->size == this->capacity) { // 缓存容量上限了,到使用频率最低的删除最近最少使用 itFreq = freq.find(min); if(itFreq == freq.end()) // 这里必须要有节点,否则异常 throw logic_error("unexpect error: cannot find list in min freq map"); if (itFreq->second.empty()) // 链表的节点数量不为0 throw logic_error("unexpect error: min freq list is empty"); node = itFreq->second.back(); // 弹出最近最少使用的,先清除缓存列表中的 cache.erase(node->key); // 然后清除频率表中的 itFreq->second.pop_back(); if (itFreq->second.empty()) { // 如果列表中的元素删完了,完全移除key freq.erase(min); } this->size--; } else { node = new cacheNode; } // 给node节点赋值 min = node->freq = 1; node->key = key; node->val = value; // 先插入到以频率为key的哈希表 itFreq = freq.find(min); if(itFreq == freq.end()) { // 这里可能是不存在对应节点的,如果不存在,创建一个节点 freq.insert(pair<int, list<cacheNode *>>(min, list<cacheNode *>())); itFreq = freq.find(min); } itFreq->second.push_front(node); // 然后插入到缓存哈希表 cache.insert(pair<int, cacheNode*>(key, node)); this->size++; } // 插入已经存在的节点 void putExistNode(int key, int value, unordered_map<int, cacheNode *>::iterator &itCache) { cacheNode *node; unordered_map<int, list<cacheNode *> >::iterator itFreq; // 找到了对应的缓存,更新缓存的value,然后把频率加一 node = itCache->second; node->val = value; incrFreq(itCache); } public: LFUCache(int capacity) { this->size = 0; this->min = 0; this->capacity = capacity; } int get(int key) { cacheNode *node; unordered_map<int, cacheNode *>::iterator itCache; unordered_map<int, list<cacheNode *> >::iterator itFreq; if (capacity == 0) return -1; itCache = cache.find(key); if (itCache == cache.end()) // 没有找到对应的cache,直接返回 return -1; incrFreq(itCache); return itCache->second->val; } void put(int key, int value) { cacheNode *node; unordered_map<int, cacheNode *>::iterator itCache; unordered_map<int, list<cacheNode *> >::iterator itFreq; if (capacity == 0) return; itCache = cache.find(key); if (itCache == cache.end()) { // 插入新值 putNewNode(key, value); } else { // 更新旧值 putExistNode(key, value, itCache); } } }; |
评论