模拟

双向链表LRU 缓存

  1. class Solution {
  2.     list<pair<int, int>> mCache;
  3.     int mCapacity;
  4. public:
  5.     Solution(int capacity):mCapacity(capacity){
  6.          // write code here
  7.     }
  9.     int get(int key) {
  10.          // write code here
  11.         auto iter=mCache.begin();
  12.         for(;iter!=mCache.end();++iter){
  13.             if(iter->first==key){
  14.                 break;
  15.             }
  16.         }
  17.         if (iter==mCache.end()) return -1;
  18.         auto temp = *iter;
  19.         mCache.erase(iter);
  20.         mCache.emplace_front(temp);
  21.         return temp.second;
  23.     }
  25.     void set(int key, int value){
  26.          // write code here
  27.         auto iter=mCache.begin();
  28.         for(;iter!=mCache.end();++iter){
  29.             if(iter->first==key){
  30.                 break;
  31.             }
  32.         }
  33.         if (iter!=mCache.end()) mCache.erase(iter);
  34.         if(mCache.size()==mCapacity){
  35.             auto iter = --mCache.end();
  36.             mCache.erase(iter);
  37.         }
  39.             mCache.emplace_front(make_pair(key, value));
  41.     }
  42. };

本实现存在的问题：

  1. 链表对于键的查找开销相当大，因为比起连续地址的数组和 vector类型，链表在访问的时候多一个指针的递归，在底层上内存访问也可能回慢一点；

    待优化部分

    于是利用 哈希表来对键值查询的过程做优化 也即是优化如下代码块：

    1. auto iter=mCache.begin();
    2. for(;iter!=mCache.end();++iter){
    3.  if(iter->first==key){
    4.      break;
    5.  }
    6. }

    哈希表 双向链表 LRU 缓存

    整体代码如下：

    1. class Solution {
    2.  list<pair<int, int>> mCache;
    3.  unordered_map<int, list<pair<int,int>>::iterator> mp;
    4.  int mCapacity;
    5. public:
    6.  Solution(int capacity):mCapacity(capacity){
    7.       // write code here
    8.  }
    10.  int get(int key) {
    11.       // write code here
    12.      if(mp.find(key)!=mp.end()){
    13.          int value = mp[key]->second;
    14.          mCache.erase(mp[key]);
    15.          mCache.emplace_front(make_pair(key, value));
    16.          mp[key] = mCache.begin();
    17.          return value;
    18.      }else return -1;   
    19.  }
    21.  void set(int key, int value){
    22.       // write code here
    23.      if(mp.find(key)!=mp.end()) // 链表中存在键删除后重新插入；
    24.          mCache.erase(mp[key]);
    25.      else if(mCache.size()==mCapacity){ // 不存在键同时链表满容量；
    26.          mp.erase(mCache.back().first);
    27.          mCache.pop_back();
    28.      }
    29.          // 插入键值对到表头；
    31.          mCache.emplace_front(make_pair(key, value));
    32.          mp[key] = mCache.begin();
    33.  }
    34. };

优化性能

image.png
可以看出结果很好；其实第二种方法做的时候没想到，是我看评论区被别人的方法启发的做出来的；

日期