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

文章目录
1. 先验知识
- 1.1 时间相关
- 1.2 容器list 双向链表遍历删除
2. 超时清除
3. 最不经常使用LFU
4. 经常使用LRU
本文主要实现不同cache, 是因为之前笔试中有个类似的问题需要实现, 并且在牛客上也有类似的训练题, 因此本文做个总结;
cache中使用map作为key-value的存储, 在查询的时候速度会最快
十月一也没啥地去玩, 提高一下自己的业务能力吧
1. 先验知识 1.1 时间相关
#include  // 时间戳等头文件
#include   // sleep的头文件
using namespace std;
using namespace std::chrono;
void test(){
    // 通过高精度时钟计算当前时间(毫秒表示), 
    // time_point 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(high_resolution_clock::now() - m_begin).count(); // 计算过去了多长时间 ms单位
    cout << 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时, 不能写入数据, 数据超时后, 清除数据; 
set(int key, int value) 存在则更新key, 不存在则插入, 没空间则返回false
get(int key) 存在则返回对应的value, 不存在则返回-1
clean() 清除超时缓存 
解决方案: 使用unorderd_map作为key,和fd的数据存储, 作为查询数据的返回空间, 使用list双向链表, 按照节点使用时间顺序保存, 超时清理时也是从头向后清理, 因为链表头是超时的, 链表尾是最新的; 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
using namespace std::chrono;

// LRU设计1 超时清理


struct fd{
    int key; 
    int value;
    time_point 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 << "析构开始" <value << "更新为:" <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 << "失败" <key == key){
                p = *it;
                temp_time.erase(it);
                break;
            }
        }
        cout << "提前了: " <<  p->key << " " << p->value <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 <value;
        }else{
            cout << key << "不存在" << endl;
            return -1;
        }
    }

    // 清除所有超时的节点
    void clean(){
        cout << "clean: " < now = high_resolution_clock::now();
        for(auto it=temp_time.begin(); it!=temp_time.end(); it++){
            while(it!=temp_time.end() && duration_cast(now - (*it)->timePoint).count() > m_time){
                // 清除map中节点
                cout << (*it)->key << "在temp_kv已经清除, 因为时间到了.. " <key);
                // 清除list中节点
                fd *p = *it;
                it = temp_time.erase(it); // 在链表中删除, 并返回下一个指针
                // 回收堆上
                delete p; 
                m_capacity++;
            }
        }break;
    }

private:
    unordered_map temp_kv;
    list 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跳转 
定义两个哈希表，第一个 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::iterator> key_table;
    unordered_map> 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::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::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，输出一个答案 
解题思路: 
使用unordered_map存储数据
使用list作为queue的存储最常使用放到队列尾部, 也就是list头部
每次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 
#include 
#include  // reverse
#include  // 为了拆解单词
#include  // 为了getline带空格的字符串
#include 
#include 
using namespace std;

struct Node{
    int key, val;
    Node(int k, int v):key(k),val(v){}
};

class Solution{
    list queue_node;
    // vector queue_node;
    unordered_map::iterator> map_node;  // 这里的map'val是Node的迭代器, 用来保存key, 和迭代器来直接找到queue
    int k;
public:
    Solution(){}
    // 删除
    int remove(list::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<key< 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 LRU(vector> &operators, int k)
    {
        // write code here
        this->k = k;
        vector 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> 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;
}
C++ 不同缓存cache实现(超时清除, 最不经常使用LFU, LRU)

C/C++/C#相关栏目本月热门文章
