缓存淘汰算法 LRU 和 LFU

灰太狼 2023-03-04 10:30 18阅读 0赞

缓存是一个计算机思维，对于重复的计算，缓存其结果，下次再算这个任务的时候，不去真正的计算，而是直接返回结果，能加快处理速度。当然有些会随时间改变的东西，缓存会失效，得重新计算。

比如缓存空间只有2个，要缓存的数据有很多，1，2，3，4，5，那么当缓存空间满了，需要淘汰一个缓存出去，其中淘汰算法有 LRU，LFU，FIFO，SC二次机会，老化算法，时钟工作集算法等等。

# 算法流程 #

**LRU，最近最少使用**，把数据加入一个链表中，按访问时间排序，发生淘汰的时候，把访问时间最旧的淘汰掉。  
比如有数据 1，2，1，3，2  
此时缓存中已有（1，2）  
当3加入的时候，得把后面的2淘汰，变成（3，1）

**LFU，最近不经常使用**，把数据加入到链表中，按频次排序，一个数据被访问过，把它的频次+1，发生淘汰的时候，把频次低的淘汰掉。  
比如有数据 1，1，1，2，2，3  
缓存中有（1(3次)，2(2次)）  
当3加入的时候，得把后面的2淘汰，变成（1(3次)，3(1次)）  
区别：LRU 是得把 1 淘汰。

显然  
LRU对于循环出现的数据，缓存命中不高  
比如，这样的数据，1，1，1，2，2，2，3，4，1，1，1，2，2，2.....  
当走到3，4的时候，1，2会被淘汰掉，但是后面还有很多1，2

LFU对于交替出现的数据，缓存命中不高  
比如，1，1，1，2，2，3，4，3，4，3，4，3，4，3，4，3，4......  
由于前面被（1(3次)，2(2次)）  
3加入把2淘汰，4加入把3淘汰，3加入把4淘汰，然而3，4才是最需要缓存的，1去到了3次，谁也淘汰不了它了。

# 实现 #

leetcode上有两个题目  
LRU：[https://leetcode.com/problems/lru-cache/description/][https_leetcode.com_problems_lru-cache_description]  
LFU：[https://leetcode.com/problems/lfu-cache/description/][https_leetcode.com_problems_lfu-cache_description]

要求是缓存的加入put()，缓存读取get()，都要在O(1)内实现。

LRU的一个实现方法：  
用一个双向链表记录访问时间，因为链表插入删除高效，时间新的在前面，旧的在后面。  
用一个哈希表记录缓存(key, value)，哈希查找近似O(1)，发生哈希冲突时最坏O(n)，同时哈希表中得记录 (key, (value, key\_ptr))，key\_ptr 是key在链表中的地址，为了能在O(1)时间内找到该节点，并把节点提升到表头。  
链表中的key，能快速找到hash中的value，并删除。

LFU的一个实现方法：  
用一个主双向链表记录（访问次数，从链表头），从链表中按时间顺序记录着（key）  
用一个哈希表记录（key，(value, 主链表ptr，从链表ptr)）ptr表示该key在链表中的地址  
然后，get，put都在哈希表中操作，近似O(1)，哈希表中有个节点在链表中的地址，能O(1)找到，并把节点提搞访问频次，链表插入删除也都是O(1)。

\-------------------- 最后贴个AC的代码：--------------------  
代码性能：1000000次加入，读取用时  
LRU: 480ms  
LFU: 510ms  
NSCache: 2000ms  
YYCache: 1400ms

LRU：

#include <list>
    #include <unordered_map>
    
    using namespace std;
    
    class LRUCache {
        
    public:
        LRUCache(int capacity);
        ~LRUCache();
        int get(int key);               // 获取缓存，hash查找的复杂度
        void put(int key, int value);   // 加入缓存，相同的key会覆盖，hash插入的复杂度
        
    private:
        int max_capacity;
        list<pair<int, int>> m_list;           // 双向链表，pair<key, value>
        unordered_map<int, list<pair<int, int>>::iterator> u_map;   // 哈希map, vector + list 实现，<key, list::iter>
    };
    
    LRUCache::LRUCache(int capacity) {
        max_capacity = capacity;
    }
    
    LRUCache::~LRUCache() {
        max_capacity = 0;
        u_map.clear();
        m_list.clear();
    }
    
    int LRUCache::get(int key) {
        auto it = u_map.find(key);      // C++11 自动类型推断
        if (it != u_map.end()) {
            // splice() 合并 将 m_list 的 iter 移动到 m_list.begin() 中
            m_list.splice(m_list.begin(), m_list, it->second);
            return it->second->second;      // return value
        }
        return -1;
    }
    
    void LRUCache::put(int key, int value) {
        auto it = u_map.find(key);
        if (it != u_map.end()) {
            // 更新 key 的 value，并把 key 提前
            it->second->second = value;
            m_list.splice(m_list.begin(), m_list, it->second);
        } else {
            // 先判断是否满，满了要删除
            if (m_list.size() >= max_capacity) {
                int del_key = m_list.back().first;
                u_map.erase(del_key);
                m_list.pop_back();
            }
            // 插入到 u_map, list 中
            m_list.emplace_front(key, value);   // emplace_front 与 puch_front， emplace_front 不拷贝节点，不移动元素，高效
            u_map[key] = m_list.begin();
        }
    }

LFU：

#include <list>
    #include <unordered_map>
    
    using namespace std;
    
    // map value 结构
    typedef struct LFUMapValue {
        int value;
        list<pair<int, list<int> > >::iterator main_it;    
        list<int>::iterator sub_it;
    } LFUMapValue;
    
    class LFUCache {
    public:
        LFUCache(int capacity);
        ~LFUCache();
        int get(int key);
        void put(int key, int value);
        void right_move(LFUMapValue *value);  // 把一个节点的key向右提高访问次数
        
    private:
        int max_cap;
        int cur_cap;
        // 储存 pair<count, subList<key> > 结构，count 访问次数，count 小到大，key 时间由新到旧
        list<pair<int, list<int> > > m_list;
        unordered_map<int, LFUMapValue> u_map;      // 储存 <key, LFUMapValue> 结构
        unordered_map<int, LFUMapValue>::iterator map_it;
    };
    
    LFUCache::LFUCache(int capacity) {
        cur_cap = 0;
        max_cap = capacity;
        m_list.emplace_front(pair<int, list<int> >(1, list<int>()));    // 插入 count == 1 的节点
    }
    
    LFUCache::~LFUCache() {
        m_list.clear();
        u_map.clear();
    }
    
    void LFUCache::right_move(LFUMapValue *value) {
        auto pre = value->main_it;
        auto pre_sub_it = value->sub_it;
        auto next = pre;
        next++;
        
        if (next != m_list.end()) {
            if (pre->first + 1 != next->first) {        // 访问次数+1，判断是否相等
                if (pre->second.size() == 1) {
                    pre->first++;       // 这个 count 的 list 只有1个key，原地+1，不创建新节点
                } else {
                    // next 前插入一个节点
                    auto it = m_list.emplace(next, pair<int, list<int> >(pre->first + 1, list<int>()));
                    it->second.splice(it->second.begin(), pre->second, pre_sub_it);
                    value->main_it = it;
                    value->sub_it = it->second.begin();
                }
            } else {
                // 追加在 next 的 sub_list 头部
                next->second.splice(next->second.begin(), pre->second, pre_sub_it);
                value->main_it = next;
                value->sub_it = next->second.begin();
                
                // 如果 pre.size == 0 则释放
                if (pre->second.size() == 0) {
                    m_list.erase(pre);
                }
            }
        } else {
            if (pre->second.size() == 1) {
                pre->first++;       // 原地+1
            } else {
                // 新建一个节点插入
                list<int> tmp_list;
                tmp_list.splice(tmp_list.begin(), pre->second, pre_sub_it);
                // tmp_list 的迭代器不能用，加入 m_list 的时候会对，tmp_list进行拷贝构造，生成新的list插入，tmp_list被释放
                m_list.emplace_back(pair<int, list<int> >(pre->first + 1, tmp_list));
                value->main_it = m_list.end();
                (value->main_it)--;
                value->sub_it = value->main_it->second.begin();
            }
        }
    }
    
    int LFUCache::get(int key) {
        map_it = u_map.find(key);
        if (map_it == u_map.end()) {
            return -1;
        }
        
        LFUMapValue *value = &(map_it->second);
        right_move(value);
        
        return value->value;
    }
    
    void LFUCache::put(int key, int value) {
        if (max_cap == 0) {
            return ;
        }
        map_it = u_map.find(key);
        if (map_it == u_map.end()) {
            // 找不到，插入
            list<int> *firstList = &(m_list.front().second);
            if (cur_cap == max_cap) {
                // 淘汰一个
                if (firstList->size() > 0) {
                    // u_map 中删除，list 中删除
                    u_map.erase(firstList->back());
                    firstList->pop_back();
                    cur_cap--;
                }
            }
            cur_cap++;
            if (m_list.front().first != 1) {
                m_list.emplace_front(pair<int, list<int> >(1, list<int>()));
                firstList = &(m_list.front().second);
            }
            firstList->emplace_front(key);
            LFUMapValue map_value;
            map_value.value = value;
            map_value.main_it = m_list.begin();
            map_value.sub_it = firstList->begin();
            u_map[key] = map_value;
        } else {
            // 找得到，更新，提高一个访问次数
            map_it->second.value = value;
            right_move(&(map_it->second));
        }
    }

https://www.jianshu.com/p/1f8e36285539

[https_leetcode.com_problems_lru-cache_description]: https://link.jianshu.com?t=https%3A%2F%2Fleetcode.com%2Fproblems%2Flru-cache%2Fdescription%2F
[https_leetcode.com_problems_lfu-cache_description]: https://link.jianshu.com?t=https%3A%2F%2Fleetcode.com%2Fproblems%2Flfu-cache%2Fdescription%2F