• 牛客网：设计LRU缓存结构 设计LFU缓存结构

    目录

    1.设计LRU缓存结构

    Get

    Set

    2.设计LFU缓存结构

    Get

    Set

    Update

    1.设计LRU缓存结构

     这题，说实话，一开始没看懂他的输入到底是什么...

    看看说明，好像又是这么一回事，就是创建一个类然后直接调用里面的方法：

    其实是维护一个双向链表，写过XV6操作系统的内存和锁那块的同学应该知道这个LRU到底是个啥。思路如下所示：

    整个LRU维护一个链表和一个哈希表两个数据结构，链表可以直接用list双向链表，哈希表用unordered_map来设计，哈希表存的是key和在链表中的迭代器的对应关系。

    Get

    首先，对于get操作，功能是这样的：对于一个给定的key，我们要在链表中查看其是否存在，这里哈希可以实现O(1)的寻找时间代价，处理流程如下：

    1.查找是否存在key对应的节点，没有则直接返回-1

    2.否则，我们先根据key在哈希中取出对应的节点，然后将对应节点删除。

    因为是LRU，所以我们要把最近使用的放在最前面（虽然用了哈希表但是按照LRU的思路还是得放最前面），所以我们把取出来的节点放到链表头部，然后再在哈希表中建立<key, list.begin()>的映射关系。

    最后返回头部节点的value

    Set

    对于set操作，功能是这样的：对于一个给定的<key, value>，如果在链表中存在key的节点，那么修改并放到链表头，如果不存在，那么直接在前面添加节点当作链表头，还要考虑链表是不是会炸掉的问题，如果容量已经达到了，那么根据LRU的原则，我们先删除链表尾部

    代码如下所示：

    1.  
    2. class Solution {
    3. public:
    4.     list<pair<int, int>> dlist;
    5.     unordered_map<int, list<pair<int, int>>::iterator> map;
    6.     int cap;
    7.     
    8.     Solution(int capacity){
    9.         cap=capacity;
    10.     }
    11.     
    12.     
    13.     int get(int key) {
    14.          // write code here
    15.         if(map.count(key)){
    16.             auto tmp=*map[key];
    17.             dlist.erase(map[key]);
    18.             dlist.push_front(tmp);
    19.             map[key]=dlist.begin();
    20.             return dlist.front().second;
    21.         }
    22.         return -1;
    23.     }
    24.     
    25.     void set(int key, int value){
    26.          if(map.count(key)){
    27.             dlist.erase(map[key]);
    28.          }else if(cap==dlist.size()){
    29.             auto tmp=dlist.back();
    30.              map.erase(tmp.first);
    31.              dlist.pop_back();
    32.          }
    33.             dlist.push_front(pair<int, int>(key, value));
    34.              map[key]=dlist.begin();        
    35.     }
    36. };
    37.  
    38. /**
    39.  * Your Solution object will be instantiated and called as such:
    40.  * Solution* solution = new Solution(capacity);
    41.  * int output = solution->get(key);
    42.  * solution->set(key,value);
    43.  */

    当然，除了可以用标准库里的数据结构，我们也可以自己手撸一个双向链表，我们需要分离出以一个将节点移动到表头的函数，以便于当我们在进行get操作找到一个节点，或者set的时候将对应的节点放到表头。

    代码如下所示，这里面有很多的细节要注意，主要是数据结构的更新和哈希的更新：

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. struct Node{
    4.     int key;
    5.     int val;
    6.     Node *prev;
    7.     Node *next;
    8.     Node(int key, int val) : key(key), val(val), next(NULL), prev(NULL) {}
    9. };
    10.  
    11. class Solution {
    12. public:
    13.     unordered_map<int, Node*> hash;
    14.     Node *head;
    15.     Node *tail;
    16.     int cap;
    17.     int size;
    18.     Solution(int capacity){
    19.         head=NULL;
    20.         tail=NULL;
    21.         cap=capacity;
    22.         size=0;
    23.         hash.clear();
    24.     }
    25.     // 将某个节点放到表头
    26.     // 如果位于尾部 需要更新尾节点
    27.     // 移到头部后需要更新指针指向以及更新头节点
    28.     void removeToHead(Node *p){
    29.         // 首先修改
    30.         if(p==head){
    31.             return;
    32.         }
    33.         p->prev->next=p->next;
    34.         if(p==tail){
    35.             tail=p->prev;
    36.         }else{
    37.             p->next->prev=p->prev;
    38.         }
    39.         p->prev=NULL;
    40.         p->next=head;
    41.         head->prev=p;
    42.         head=p;
    43.         return;
    44.     }
    45.  
    46.     int get(int key) {
    47.         if(hash.find(key)==hash.end()){
    48.             return -1;
    49.         }
    50.         removeToHead(hash[key]);
    51.         return hash[key]->val;
    52.     }
    53.  
    54.     void set(int key, int value){
    55.         if(hash.find(key)!=hash.end()){
    56.             hash[key]->val=value;
    57.             removeToHead(hash[key]);
    58.         }else if(size>=cap){
    59.             //将尾节点更新为当前节点 移动到头部
    60.             //更新哈希表 删除原来的 增加新的
    61.             int k=tail->key;
    62.             hash.erase(k);
    63.             tail->key=key;
    64.             tail->val=value;
    65.             removeToHead(tail);
    66.             hash[key]=head;
    67.         }else{
    68.             //不存在节点 且容量还没满 直接在头部插入
    69.             Node *node=new Node(key, value);
    70.             if(head==NULL){
    71.                 head=tail=node;
    72.             }else{
    73.                 node->next=head;
    74.                 node->prev=NULL;
    75.                 head->prev=node;
    76.                 head=node;
    77.             }
    78.             hash[key]=head;
    79.             size++;
    80.         }
    81.  
    82.     }
    83. };

    2.设计LFU缓存结构

    上面的LRU是最近最少使用的策略，LFU是least frequently used，从字面上来看貌似也是最近最少使用策略嘛，但是从题目来看，是还让我们记录使用set和get的次数的。

    我们这里用一个双哈希表来解决这个题目，同时在题解中看到了一个画的很好的图：

    这就是我们要维护的数据结构。首先，对于每个频率，我们维护一个双向链表，这个双向链表代表了对应频率的节点的集合，存储的是{freq, key, value}，这样就形成了频率和链表的哈希表。我们根据这个哈希表可以轻松根据频率找到双向链表，在容量不足的时候用来找删除的节点时十分迅速。其次也方便一些删除插入的更新操作。也由于要在容量不足的时候删除节点，我们需要用一个变量来存储freq最小的节点。

    第二个哈希表是key和链表节点的哈希表，这个哈希表对于get操作是十分必须的。

    接下来解析一下get和set操作的流程：

    Get

    get操作的功能是根据key找value，有了哈希表之后，我们可以直接根据key找到对应节点，然后找到value，如果没有找到则返回-1。

    Set

    set操作的功能是设置<key, value>，处理流程如下：

    1.如果之前存在这个映射关系，那么我们更新一下这个映射，关于更新是什么，之后说。

    2.如果不存在，我们就要插入这个新的映射，当然，还要考虑当前的链表是否已经满了，因此我们还需要维护一个记录剩余空间的变量。

    a.如果已经满了，我们需要做一些事情：

    首先要找到频率最低的且最少使用的节点，对于频率最低的节点，由于我们维护了频率和对应节点的集合的哈希，我们很快可以找到，对于最少使用，我们每次更新的时候是放到表头，所以最少使用的就是最后一个节点。

    找到节点之后我们要删除这个节点，删除之后我们还得检查这个链表是否为空，是空的话还得直接删除这个映射项。

    b.如果没有满，我们维护一下剩余的容量

    之后直接向freq=1的双向链表头部插入新的<freq=1, key, value>，之后也要更新对应的<key,value>映射。

    Update

    更新操作用于在set中已经存在对应的key或者对已存在节点使用了get时，更新其频率。

    首先，我们根据key取出链表节点，然后根据链表节点中的freq找到对应的链表，之后直接在链表中删除对应节点。

    如果删除后这个链表变成空了：

    删除对应映射关系，再看是否需要更新最小频率，如果被删除链表是最小频率对应的链表，那么需要更新

    最后将新的<freq+1,key,value>插入对应链表，如果是set还需要更新map

    具体代码如下所示：

    1. class Solution {
    2. public:
    3.     /**
    4.      * lfu design
    5.      * @param operators int整型vector<vector<>> ops
    6.      * @param k int整型 the k
    7.      * @return int整型vector
    8.      */
    9.     // 存频率和频率对应节点链表的字典
    10.     unordered_map<int, list<vector<int>>> freq_mp;
    11.     // 存对应键值和节点
    12.     unordered_map<int, list<vector<int>>::iterator> mp;
    13.     // 记录最小频率 用来使用LFU策略找节点
    14.     int min_freq=0;
    15.     // 存剩余容量
    16.     int size=0;
    17.     
    18.     vector<int> LFU(vector<vector<int>>& operators, int k){
    19.         vector<int> res;
    20.         size=k;
    21.         for(int i=0;i<operators.size();++i){
    22.             if(operators[i][0]==1){
    23.                 set(operators[i][1], operators[i][2]);
    24.             }else{
    25.                 res.push_back(get(operators[i][1]));
    26.             }
    27.         }
    28.         return res;
    29.     }
    30.     
    31.     void update(list<vector<int>>::iterator iter, int key, int value){
    32.         //取出双向链表中的一个节点 即 vector<int>
    33.         int freq=(*iter)[0];
    34.         freq_mp[freq].erase(iter);
    35.         //如果该频率中已经没有节点
    36.         //删除频率双向链表中的对应链表
    37.         //查看是否需要更新最小频率
    38.         if(freq_mp[freq].empty()){
    39.             freq_mp.erase(freq);
    40.             if(freq == min_freq){
    41.                 min_freq++;
    42.             }
    43.         }
    44.         //向freq+1的双向链表头部中插入
    45.         //由于原来的节点已经不存在 需要重新设置<key,value>的存储
    46.         freq_mp[freq+1].push_front({freq+1, key, value});
    47.         mp[key]=freq_mp[freq+1].begin();
    48.     }
    49.     
    50.     void set(int key, int value){
    51.         auto it=mp.find(key);
    52.         if(it!=mp.end()){
    53.             //链表中存在节点 更新value和频率
    54.             update(it->second, key, value);
    55.         }else{
    56.             //哈希表中没有该节点
    57.             //如果链表已满 删除频率最低而且最早的删掉
    58.             //频率表中删除最后一个节点
    59.             //删除对应<key,value>的节点
    60.             if(size==0){
    61.                 int oldkey=freq_mp[min_freq].back()[1];
    62.                 freq_mp[min_freq].pop_back();
    63.                 if(freq_mp[min_freq].empty()){
    64.                     freq_mp.erase(min_freq);
    65.                 }
    66.                 mp.erase(oldkey);
    67.             }else{
    68.                 //容量未满 可以直接加入
    69.                 size--;
    70.             }
    71.             min_freq=1;
    72.             freq_mp[1].push_front({1, key, value});
    73.             mp[key]=freq_mp[1].begin();
    74.         }
    75.     }
    76.     
    77.     //get操作:没有找到则返回-1
    78.     //找到则更新频率并且取出value返回
    79.     int get(int key){
    80.         int res=-1;
    81.         auto it = mp.find(key);
    82.         if(it==mp.end()){
    83.             return res;
    84.         }
    85.         auto iter = it->second;
    86.         res=(*iter)[2];
    87.         update(iter, key, res);
    88.         return res;
    89.     }
    90. };

    不得不说，数据结构和相应的存储结合真是一件巧妙的事情~

  • 相关阅读:
    java毕业设计小区停车场管理系统mybatis+源码+调试部署+系统+数据库+lw
    【系统架构设计】架构核心知识： 2.5 软件测试、系统转换计划、系统维护
    微擎模块 有间解忧杂货店小程序2.14 修复用户头像昵称不显示的BUG
    蓝桥杯刷题
    RobotFramework+Eclispe环境安装篇
    页面优化技术
    python+vue+elementui医院急诊病房预约系统django
    代码随想录--哈希--两个数组的交集
    JXLS2同一个sheet多个表格循环覆盖下面表格数据问题
    CDR插件开发之Addon插件005 - Corel.Interop.VGCore.dll库文件简介
  • 原文地址：https://blog.csdn.net/weixin_46266058/article/details/125463308