写在前面

LFU（Least Frequency Used）算法也是一种缓存淘汰策略，顾名思义就是淘汰掉使用频次最少的数据，如果多个最低频次使用的就删除最久远的呢个。前文的LRU算法是仅仅删除最久远的呢个，因此单独一个哈希链表就足够了，但是LFU还涉及到使用频次的问题。

  • 首先，为了快速获取key对应的value值，哈希表自然是逃不过了，同时想快速插入和删除元素，那么链表也逃不过了呀
  • 如何将二者结合起来，首先肯定需要一个key到value的映射；其次是freq到key的映射。首先key到value的映射不能一对多，同时freq到key的映射是需要一对多的，那么可以考虑freq映射到一连串的key(节点)
  • 抽象出节点Node：包含哪些信息呢？
    • 肯定要有value，因为需要快速获取对应值
    • freq? 也需要，因为当get时，需要将对应的freq更新并更换位置
    • key? 也需要，因为容量不够需要删除时，需要删除对应的keyTable
  • 前面已经确认需要用一个unordered_map<int,list<Node>> freqTable来快速定位某一频率的系列点
  • 那当利用key信息查找节点时，如何快速获取呢？
    • key到节点位置的映射：unordered_map<int,list<Node>::iterator> keyTable；这里主要用到了链表的特性：插入和删除不会使原有的迭代器失效。

get、put对应的操作

整个过程就是在考虑需要更改对应的表有哪些？更改表中的哪些信息？每一步操作都要记得考虑更改什么表？对应的哪些值？

get操作

  • 不存在，则直接返回

  • 存在，返回值，但注意同时需要更新哪个表？什么值？

    • 更新访问次数，这就会涉及到Frequency-Table，需要删除原有位置（这个过程需要注意是否会更改MiniFrequency的值），然后添加到新位置

    • 最后再返回结果

      put操作

  • 注意题目中容量是可以为零的，如果没有容量直接返回

  • 先看是否存在？存在则更改值，更改就意味着访问了

    • 访问就类似get操作，步骤几乎同上

  • 若不存在，检查容量

    • 未满，直接插入，插入时频率为最小的1，同时添加到Key-Table
    • 已满，先删除最小频率的末尾，再插入，同时添加到Key-Table

利用内置的数据结构

利用C++自有的set容器，可以做到自动排序，同时根据访问次数和访问时间排序，学习一下官解的写法。

定义Node节点

自定义排序，相等则按照时间排序（升序，时间值越大越新），否则按照访问频次排序（升序）

struct Node {
    int cnt, time, key, value;

    Node(int _cnt, int _time, int _key, int _value):cnt(_cnt), time(_time), key(_key), value(_value){}
    
    bool operator < (const Node& rhs) const {
        return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
    }
};

贴个代码

class LFUCache {
public:
    LFUCache(int capacity) {
        this->capacity=capacity;
        this->miniFrq=0;   // 一开始设置为零
        keyT.clear();
        frqT.clear();
    }
    
    int get(int key) {
        // 没找到可以直接返回，但是找到了就不能返回了
        if(!keyT.count(key))
            return -1;
        list<Node>::iterator it=keyT[key];
        //  当前key对应的val和freq
        int val=it->value;
        int freq=it->freq;
        // 用迭代器删除所在位置
        frqT[freq].erase(it);
        // 判断删除后是否为空链表
        if(frqT[freq].size()==0){
            frqT.erase(freq);  // 删除对应的freq
            // 如果删除的整好是最小频率链表则更新最小频率
            if(miniFrq==freq)
                miniFrq++;
        }
        // 加入新的链表
        frqT[freq+1].push_front(Node(key,val,freq+1));
        keyT[key]=frqT[freq+1].begin();
        // 返回值
        return val;
    }
    
    void put(int key, int value) {
        // 注意容量可以是为零的
        if (capacity == 0) return;
        // 先需要判断该key是否存在
        if(keyT.count(key)){
            // 存在，则更新值，更新位置,更新keyTable的迭代器位置
            auto it=keyT[key];
            int freq=it->freq;
            frqT[freq].erase(it);
            // 判断删除后是否为空链表
            if(frqT[freq].size()==0){
                frqT.erase(freq);  // 删除对应的freq
                // 如果删除的整好是最小频率链表则更新最小频率
                if(miniFrq==freq) miniFrq++;       
            }
            // 加入新的链表
            frqT[freq+1].push_front(Node(key,value,freq+1));
            keyT[key]=frqT[freq+1].begin();
            return;
        }
        if(keyT.size()<capacity){
            // 直接插入到频率为1的链表中并更新minifreq，更新keyTable的迭代位置
            frqT[1].push_front(Node(key,value,1));
            keyT[key]=frqT[1].begin();
            miniFrq=1;
            return;
        }
        // 如果会超出，则先删除最小频率的尾结点,清空keyTable
        keyT.erase(frqT[miniFrq].back().key);
        frqT[miniFrq].pop_back();
        // 此时即便最小频率的链表为空，也不影响后续，因为插入一定会将minifrq变为1
        if(frqT[miniFrq].size()==0)
            frqT.erase(miniFrq);
        // 然后插入
        frqT[1].push_front(Node(key,value,1));
        keyT[key]=frqT[1].begin();
        miniFrq=1;
    }
private:
    int capacity; // 最大容量
    int miniFrq;  // 最小频次
    struct Node{
        int value;  // 
        int key;    // 删除哈希表中的键值对时需要
        int freq;   // 操作节点时，快速知道其对应的频率，从而更换链表位置
        Node(int k,int v,int f):key(k),value(v),freq(f){}
    };
    // 对get(key)操作时，快速返回value，并更改其freq，更改对应链表的位置
    // value好说，单哈希就够了，但是快速定位？链表迭代器位置？
    // 链表还有一个特性，呢就是插入和删除会造成原有list迭代器的失效，vector中不行
    unordered_map<int,list<Node>::iterator> keyT;  // int key, node位置
    // frequency的快速定位，主要是满足删除操作，设定开头是最新的，末尾是最旧的数据
    unordered_map<int,list<Node>> frqT;     //   int freq, list
};

$\cdots$ end $\cdots$