LRU与LFU

LRU

• 注意 map<int,list<pair<int,int>>::iterator>m; 要加iterator要不然没法指向List内元素。还有list<pair<int,int>>List;

• LRU注意添加元素时要检查溢出时是否已有该元素，如果有则先get更新，再修改队首该元素的second值。

class LRUCache {
public:
    list<pair<int,int>>List;
    map<int,list<pair<int,int>>::iterator>m;
    int maxlength=0;
    LRUCache(int capacity) {
        maxlength=capacity;
    }
    
    int get(int key) {
        // 如果有该元素删除map对应的位置，再插入freq++的位置末尾
        if(m.count(key)==1){
            int second=m[key]->second;
            List.erase(m[key]);
            m.erase(key);
            List.push_back(make_pair(key,second));
            m[key]=--List.end();
            return second;
        }
        else{
            return -1;
        }
    }
    
    void put(int key, int value) {
        // 如果存在该元素则get更新，否则就当没操作过
        get(key);
        if(m.count(key)==1){
            m[key]->second=value;
            return ;
        }
        if(maxlength==m.size()){
            m.erase(List.begin()->first);
            List.erase(List.begin());
        }
        List.push_back(make_pair(key,value));
        m[key]=--List.end();
    }
};

LFU

LFU的push遇到重复元素不删除key，只是get更新key之后对value进行覆盖。

map<int,pair<int,list<pair<int,int>>::iterator>>KeyFreq用iterator指向FreqList的List中的一个节点。

class LFUCache {
public:
    int length;
    map<int,list<pair<int,int>>>FreqList;
    map<int,pair<int,list<pair<int,int>>::iterator>>KeyFreq;
    int minFreq;
    LFUCache(int capacity) {
        length=capacity;
        minFreq=0;
    }
    
    int get(int key) {
        if(length<=0||KeyFreq.count(key)==0){
            return -1;
        }
        auto l=KeyFreq[key].second;
        int freq=KeyFreq[key].first;
        int value=l->second;
    
        FreqList[freq].erase(l);
        if(freq==minFreq&&FreqList[freq].size()==0){
            minFreq=freq+1;
        }
        FreqList[freq+1].push_front(make_pair(key,value));
        KeyFreq[key]=make_pair(freq+1,FreqList[freq+1].begin());
        return value;
    }
    
    void put(int key, int value) {
        if(length<=0){
            return;
        }
        if(KeyFreq.count(key)==1){
            // 内部原有元素
            get(key);
            auto l=KeyFreq[key].second;
            l->second=value;
        }
        else{
            if(length==KeyFreq.size()){
                // 遇到push溢出的情况
                auto l=(--FreqList[minFreq].end());
                int key=l->first;
                FreqList[minFreq].erase(l);
                KeyFreq.erase(key);
            }            
            FreqList[0].push_front(make_pair(key,value));
            KeyFreq[key]=make_pair(0,FreqList[0].begin());
            minFreq=0;
        }
    }
};

• 优势：

在数据访问符合正态分布时，相比于LRU算法，LFU算法的缓存命中率会高一些。

• 劣势：

(1)LFU的复杂度要比LRU更高一些。
(2)需要维护数据的访问频次，每次访问都需要更新。
(3)早期的数据相比于后期的数据更容易被缓存下来，导致后期的数据很难被缓存。
(4)新加入缓存的数据很容易被剔除，像是缓存的末端发生“抖动”。