C++ 不同缓存cache实现(超时清除, 最不经常使用LFU, LRU)

怼烎@ 2022-09-14 09:07 189阅读 0赞

### 文章目录 ###

*  1. 先验知识
 *   *  1.1 时间相关
     *  1.2 容器list 双向链表遍历删除
 *  2. 超时清除
 *  3. 最不经常使用LFU
 *  4. 经常使用LRU

*  本文主要实现不同cache, 是因为之前笔试中有个类似的问题需要实现, 并且在牛客上也有类似的训练题, 因此本文做个总结;
 *  cache中使用map作为key-value的存储, 在查询的时候速度会最快
 *  十月一也没啥地去玩, 提高一下自己的业务能力吧

# 1. 先验知识 #

## 1.1 时间相关 ##

#include <chrono> // 时间戳等头文件
    #include <unistd.h> // sleep的头文件
    using namespace std;
    using namespace std::chrono;
    void test(){ 
        // 通过高精度时钟计算当前时间(毫秒表示), 
        // time_point<high_resolution_clock> m_begin = high_resolution_clock::now(); // 当前时间戳
        auto m_begin = high_resolution_clock::now();
        usleep(50000); // 最小单位是ns, 这里延时50ms
        // sleep(1); // 注意这里是最小单位是s
        int64_t ms = duration_cast<chrono::milliseconds>(high_resolution_clock::now() - m_begin).count(); // 计算过去了多长时间 ms单位
        cout << ms <<endl;
        cout << high_resolution_clock::now().time_since_epoch().count() <<endl; // 当前时间到1970年一月一日过去了多少ms
    }

## 1.2 容器list 双向链表遍历删除 ##

*  注意删除的时候一定要把堆上创建的内存delete一下

for(auto it=temp_time.begin(); it!=temp_time.end(); it++){ 
        while(it!=temp_time.end() && 时间差 > m_time){ 
            // 清除map中节点
            temp_kv.erase((*it)->key);
            // 清除list中节点
            fd *p = *it;
            it = temp_time.erase(it); // 在链表中删除, 并返回下一个指针
            // 回收堆上
            delete p; 
            m_capacity++;
        }
    }

# 2. 超时清除 #

设计个cache, 功能: 有最大cache空间, 最长保存时间; 当cache空间为0时, 不能写入数据, 数据超时后, 清除数据;

1.  set(int key, int value) 存在则更新key, 不存在则插入, 没空间则返回false
2.  get(int key) 存在则返回对应的value, 不存在则返回-1
3.  clean() 清除超时缓存

解决方案: 使用unorderd\_map作为key,和fd的数据存储, 作为查询数据的返回空间, 使用list双向链表, 按照节点使用时间顺序保存, 超时清理时也是从头向后清理, 因为链表头是超时的, 链表尾是最新的;

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <list>
    #include <memory>
    #include <chrono>
    #include <unistd.h>
    #include <unordered_map>
    #include <queue>
    
    using namespace std;
    using namespace std::chrono;
    
    // LRU设计1 超时清理
    /* 1. 初始化时, 传入的参数 a.缓存空间最大长度, b.缓存的最长时间 2. set(key:int, value:int)->bool:已经存在(更新),未存在且插入成功(插入) 3. get(key:int) -> value, 没有返回-1 3. clean()->bool:清理所有超时的内容 对于超时清理解决: struct fd{ int key; int value; timePoint; }; map[fd.key] = fd // https://www.cnblogs.com/zuixime0515/p/10508079.html list使用介绍 维护一个链表, set或者get时, 更新timePoint, 从尾插入链表, 这样就是一个按照timePoint倒叙的链表 clean时, 从头遍历, 如果 */
    
    struct fd{ 
        int key; 
        int value;
        time_point<high_resolution_clock> timePoint=high_resolution_clock::now();
        fd(int k, int v): key(k),value(v) { }
    };
    
    class TimeoutCache{ 
    public:
        TimeoutCache(int capacity, int t):m_capacity(capacity),m_time(t){ }
        ~TimeoutCache(){ 
            cout << "析构开始" <<endl;
            for(auto &a : temp_time){ 
                delete a;
            }
            cout << "析构成功" <<endl;
        }
    
        // 存在:
        // 不存在: 判断capacity
        bool set(int k, int v){ 
            cout << "set: ";
            if(temp_kv.count(k) == 1) {  // key存在这里, 更新返回
                cout << k << "存在, 历史值:" << temp_kv[k]->value << "更新为:" <<v << endl;
                temp_kv[k]->value = v;
                update_temp_time(k);
            } else if(m_capacity != 0){  // key没在缓存, 并且有空间 插入缓存
                m_capacity--;
                fd * newFd = new fd(k, v);
                temp_kv[k] = newFd;
                insert_temp_time(newFd);
                cout << k << "不存在 插入值" << temp_kv[k]->value << endl;
            } else{  // 没空间
                cout << "空间不足" << k << "插入" << v << "失败" <<endl;
                return false;
            }
            return true;
        }
    
        // 更新时间为当前时间, 并且将节点放到最尾的位置
        void update_temp_time(int key){  
            fd *p;
            for(auto it=temp_time.begin(); it!=temp_time.end(); it++){ 
                if((*it)->key == key){ 
                    p = *it;
                    temp_time.erase(it);
                    break;
                }
            }
            cout << "提前了: " <<  p->key << " " << p->value <<endl;
            p->timePoint = high_resolution_clock::now();
            temp_time.push_back(p); 
        }
    
        // temp_time头插节点t
        void insert_temp_time(fd *t){ 
            temp_time.push_back(t);
        }
    
        // 得到key对应的value, 并且更新或者提前
        int get(int key){ 
            cout << "get: ";
            if(temp_kv.count(key) == 1){ 
                cout << key << " " << temp_kv[key]->value <<endl;
                update_temp_time(key);
                return temp_kv[key]->value;
            }else{ 
                cout << key << "不存在" << endl;
                return -1;
            }
        }
    
        // 清除所有超时的节点
        void clean(){ 
            cout << "clean: " <<endl;
            time_point<high_resolution_clock> now = high_resolution_clock::now();
            for(auto it=temp_time.begin(); it!=temp_time.end(); it++){ 
                while(it!=temp_time.end() && duration_cast<chrono::milliseconds>(now - (*it)->timePoint).count() > m_time){ 
                    // 清除map中节点
                    cout << (*it)->key << "在temp_kv已经清除, 因为时间到了.. " <<endl;
                    temp_kv.erase((*it)->key);
                    // 清除list中节点
                    fd *p = *it;
                    it = temp_time.erase(it); // 在链表中删除, 并返回下一个指针
                    // 回收堆上
                    delete p; 
                    m_capacity++;
                }
            }break;
        }
    
    private:
        unordered_map<int, fd*> temp_kv;
        list<fd*> temp_time; // 负责超时删除, 更新重排
        int m_capacity; // 最大容量
        int m_time; // 最大存在时间
    };
    
    void test(){ 
        TimeoutCache *myCache = new TimeoutCache(3, 50); // 3个空间, 4个时间长
        myCache->get(1);
        myCache->set(1,1);
        myCache->set(1,13);
        myCache->set(2,435);
        myCache->set(3,32);
        usleep(40000);
        myCache->set(1,32);
        usleep(30000); // 100毫秒过去了,么得了
        myCache->clean(); // 这里应该清除23, 保留1
        myCache->set(5,1);
        myCache->get(1);
        myCache->set(8,1);
        delete myCache;
    }
    int main(int argc, char const *argv[]){ 
        test();
        return 0;
    }

(base) zjq@DESKTOP-82TMKG6:LeetCode101$ ./"test" 
    get: 1不存在
    set: 1不存在 插入值1
    set: 1存在, 历史值:1更新为:13
    提前了: 1 13
    set: 2不存在 插入值435
    set: 3不存在 插入值32
    set: 1存在, 历史值:13更新为:32
    提前了: 1 32
    clean: 
    2在temp_kv已经清除, 因为时间到了.. 
    3在temp_kv已经清除, 因为时间到了.. 
    set: 5不存在 插入值1
    get: 1 32
    提前了: 1 32
    set: 8不存在 插入值1
    析构开始
    析构成功

# 3. 最不经常使用LFU #

[LeetCode跳转][LeetCode]

定义两个哈希表，第一个 freq\_table 以频率 freq 为索引，每个索引存放一个双向链表，这个链表里存放所有使用频率为 freq 的缓存，缓存里存放三个信息，分别为键 key，值 value，以及使用频率 freq。第二个 key\_table 以键值 key 为索引，每个索引存放对应缓存在 freq\_table 中链表里的内存地址，这样我们就能利用两个哈希表来使得两个操作的时间复杂度均为 O(1)O(1)。同时需要记录一个当前缓存最少使用的频率 minFreq，这是为了删除操作服务的。

// 缓存的节点信息
    struct Node { 
        int key, val, freq;
        Node(int _key,int _val,int _freq): key(_key), val(_val), freq(_freq){ }
    };
    class LFUCache { 
        int minfreq, capacity;
        unordered_map<int, list<Node>::iterator> key_table;
        unordered_map<int, list<Node>> freq_table;
    public:
        LFUCache(int _capacity) { 
            minfreq = 0;
            capacity = _capacity;
            key_table.clear();
            freq_table.clear();
        }
        
        int get(int key) { 
            if (capacity == 0) return -1;
            auto it = key_table.find(key);
            if (it == key_table.end()) return -1;
            list<Node>::iterator node = it -> second;
            int val = node -> val, freq = node -> freq;
            freq_table[freq].erase(node);
            // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
            if (freq_table[freq].size() == 0) { 
                freq_table.erase(freq);
                if (minfreq == freq) minfreq += 1;
            }
            // 插入到 freq + 1 中
            freq_table[freq + 1].push_front(Node(key, val, freq + 1));
            key_table[key] = freq_table[freq + 1].begin();
            return val;
        }
        
        void put(int key, int value) { 
            if (capacity == 0) return;
            auto it = key_table.find(key);
            if (it == key_table.end()) { 
                // 缓存已满，需要进行删除操作
                if (key_table.size() == capacity) { 
                    // 通过 minFreq 拿到 freq_table[minFreq] 链表的末尾节点
                    auto it2 = freq_table[minfreq].back();
                    key_table.erase(it2.key);
                    freq_table[minfreq].pop_back();
                    if (freq_table[minfreq].size() == 0) { 
                        freq_table.erase(minfreq);
                    }
                } 
                freq_table[1].push_front(Node(key, value, 1));
                key_table[key] = freq_table[1].begin();
                minfreq = 1;
            } else { 
                // 与 get 操作基本一致，除了需要更新缓存的值
                list<Node>::iterator node = it -> second;
                int freq = node -> freq;
                freq_table[freq].erase(node);
                if (freq_table[freq].size() == 0) { 
                    freq_table.erase(freq);
                    if (minfreq == freq) minfreq += 1;
                }
                freq_table[freq + 1].push_front(Node(key, value, freq + 1));
                key_table[key] = freq_table[freq + 1].begin();
            }
        }
    };

# 4. 经常使用LRU #

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能 set(key, value)：将记录(key, value)插入该结构 get(key)：返回key对应的value值 \[要求\] set和get方法的时间复杂度为O(1) 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。 当缓存的大小超过K时，移除最  
不经常使用的记录，即set或get最久远的。 若opt=1，接下来两个整数x, y，表示set(x, y) 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1 对于每个操作2，输出一个答案

解题思路:

1.  使用unordered\_map存储数据
2.  使用list作为queue的存储最常使用放到队列尾部, 也就是list头部
3.  每次set或者get一个值,先从queue中拿出来, 在放到queue头部, 这样就保证每次处理key , 都能将key置前了

输入：[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
    返回值：[1,-1]
    说明：
    第一次操作后：最常使用的记录为("1", 1)
    第二次操作后：最常使用的记录为("2", 2)，("1", 1)变为最不常用的
    第三次操作后：最常使用的记录为("3", 2)，("1", 1)还是最不常用的
    第四次操作后：最常用的记录为("1", 1)，("2", 2)变为最不常用的
    第五次操作后：大小超过了3，所以移除此时最不常使用的记录("2", 2)，加入记录("4", 4)，并且为最常使用的记录，然后("3", 2)变为最不常使用的记录

#include <iostream>
    #include <vector>
    #include <algorithm> // reverse
    #include <sstream> // 为了拆解单词
    #include <string> // 为了getline带空格的字符串
    #include <unordered_map>
    #include <list>
    using namespace std;
    
    struct Node{ 
        int key, val;
        Node(int k, int v):key(k),val(v){ }
    };
    
    class Solution{ 
        list<Node> queue_node;
        // vector<Node> queue_node;
        unordered_map<int, list<Node>::iterator> map_node;  // 这里的map'val是Node的迭代器, 用来保存key, 和迭代器来直接找到queue
        int k;
    public:
        Solution(){ }
        // 删除
        int remove(list<Node>::iterator &ite){ 
            int k=ite->key;
            int v=ite->val;
            queue_node.erase(ite);
            // queue_node.erase(ite);
            map_node.erase(k);
            return v;
        }
    
        // 给队列和map添加值
        void add(int key, int val){ 
            // cout<< queue_node.begin()->key<<endl;
            // if(queue_node.size()==0) queue_node.push_back(Node(key, val));
            // else queue_node.insert(queue_node.begin(), Node(key, val));
            // cout<< queue_node.begin()->key<<endl;
            queue_node.push_front(Node(key, val));
            map_node[key] = queue_node.begin(); // 相当于把当前这个节点的指针保存到了map中
            if(queue_node.size() > this->k){ 
                auto last_node = queue_node.end(); // 得到最后一位的下一位 xxx#的#
                --last_node;
                remove(last_node);
            }
        }
    
        // set
        void set(int key, int val){ 
            auto ite = map_node.find(key);  // 判断当前key在不在
            if(ite != map_node.end()) remove(ite->second); // 找到了则需要删除在重新在头插入
            add(key, val);
        }
    
        int get(int key){ 
            auto ite = map_node.find(key);
            if(ite != map_node.end()){   // 如果当前key已经在map里面, 则删除map在重新插入, 以此提前
                int val = remove(ite->second); 
                add(key, val); 
                return val;
            }
            return -1;
        }
    
        vector<int> LRU(vector<vector<int>> &operators, int k)
        { 
            // write code here
            this->k = k;
            vector<int> ans;
            for (auto &input : operators)
            { 
                if (input[0] == 1)
                { 
                    set(input[1], input[2]);
                }
                else if(input[0] == 2)
                { 
                    ans.push_back(get(input[1]));
                }
            }
            return ans;
        }
    };
    
    int main(){ 
        vector<vector<int>> input = { { 1,1,1},{ 1,2,2},{ 1,3,2},{ 2,1},{ 1,4,4},{ 2,2}};
        // Solution s = new Solution();
        Solution s;
        s.LRU(input, 3);
        return 0;
    }

[LeetCode]: https://leetcode-cn.com/problems/lfu-cache/