460. LFU Cache

相关问题：146. LRU Cache

问题：

设计类LFUCache，实现LFU Cache

Least Frequently Used

优先度为：访问频率最多优先 的缓存。

• 缓存大小一定，capacity
• get(key)：通过key查找value，若缓存中不存在key，返回-1
• put(key, value)：插入缓存key=value。

Example 1:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3
 

Constraints:
0 <= capacity, key, value <= 10^4
At most 10^5 calls will be made to get and put.

　　

解法：LFU

c++中 利用 map 和 unordered_map 来实现：

• cache：map：存储cache链表(头新，尾旧)。<frequency: list>（拥有frequency优先级排序）
  • ⚠️ 注意：list若==empty，记得要删除map中这个frequency元素。
• kl：unordered_map：存储对应key在cache中的位置<frequency, list_idx>，方便直接访问。
• kv：另：为了存储value，追加unordered_map保存key：value对应关系。

那么，对于cache，我们有以下两个基本操作：

• 追加key：value对
  • update(key, value)【假设，此操作cache已经不超过最大容量】
    • 若key存在于cache中
      • 在list中找到key（定位：kl[key]），将key从cache中删除：freq=kl[key].first; list=cache[kl[key].first]
        • cache[kl[key].first].erase(kl[key].second)
        • 解释：->cache[kl[key].freq].erase(kl[key].list_idx)
        • ⚠️ 若此时list==null，cache.erase(freq)
      • 1. freq++
      • 2. 重新加到list头：list.push_front(key)，更新key在list中的位置：kl[key]={freq, list.begin()}
      • 3. 更新 kv[key]=value
    • 若key不存在于cache中：freq=0, list=cache[freq+1]
      • 1. freq++
      • 2. 将key加到list头：list.push_front(key)，更新key在list中的位置：kl[key]={freq, list.begin()}
      • 3. 更新 kv[key]=value
• 删除最老的元素（当size超出cache容量）
  • outlast()：last = list.back()     (list = cache.begin().second)
  • kl.erase(last)
  • kv.erase(last)
  • list.pop_back()
    • ⚠️ 若此时list==null，cache.erase(freq)

再看题目所求：

• get(key)：
  • update(key)
  • return kv[key]
• put(key, value)
  • 若cache==最大容量：删除最老元素：outlast()
  • 此时，cache一定不超过最大容量：再进行：update(key, value)
    • ⚠️ 注意：若outlast失败，那证明现在的cache==最大容量，依然不能update。

代码参考：

class LFUCache {
public:
    LFUCache(int capacity) {
        size = capacity;
    }
    
    int get(int key) {
        //cout<<"get:"<<key<<endl;
        if(kv.count(key)) {
            update(key, kv[key]);
            return kv[key];
        }
        return -1;
    }
    
    void put(int key, int value) {
        //cout<<"put:"<<key<<"= "<<value<<endl;
        if(!kv.count(key) && kv.size()==size) {
            //cout<<"outlast"<<endl;
            if(false==outlast()) return;
        }
        update(key, value);
        return;
    }
private:
    int size;
    map<int, list<int>> cache;//frequency: key list(oldest->back; new->begin)
    unordered_map<int, int> kv;//key:value
    unordered_map<int, pair<int, list<int>::iterator>> kf;//key:frequency,idx
    void update(int key, int value) {
        if(kv.count(key)) {//exist
            cache[kf[key].first].erase(kf[key].second);
            if(cache[kf[key].first].empty()) cache.erase(kf[key].first);
        }
        kv[key] = value;
        kf[key].first++;
        cache[kf[key].first].push_front(key);
        kf[key].second = cache[kf[key].first].begin();
    }
    bool outlast() {
        if(cache.empty()) return false;
        int last = cache.begin()->second.back();//cache.begin->minimal frequency
        //cout<<"out:"<<last<<endl;
        cache.begin()->second.pop_back();
        if(cache.begin()->second.empty()) cache.erase(cache.begin());
        kv.erase(last);
        kf.erase(last);
        return true;
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */