No.146 LRU Cache

No.146 LRU Cache

 

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

 

解析:

  这题其实并没有考察什么特别难的算法,主要还是考察数据结构的设计问题。

  LRU算法:最近最少使用,替换在内存中,但又不使用的内存块
   题意理解:key应该是物理块块号,而value为内存块号,相当于下标索引【但对set函数明显不对】
             正确理解应该为:key为关键字,value为key对应的值
   思考:用什么数据结构来存?

   设计:【思路没有任何难度,就是使用什么数据结构的问题!!!】

      越靠前,越新

      若不存在且未满,头插
      若不存在且已满,置最后一个无效pop_back(),头插
      若存在,原来的删除,头插


     最开始想到使用vector,后来想到头插的话,全部都要移动,还是用链表list比较好,有push_front;但是用list仍然是超时,最后根据网上查到的,使用双向链表和哈希表,来提高性能。

  第一种提交方案【超时】:
 

技术分享
  1 #include "stdafx.h"
  2 #include <list>
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 /*
  7     LRU算法:最近最少使用,替换在内存中,但又不使用的内存块
  8     题意理解:key应该是物理块块号,而value为内存块号,相当于下标索引【貌似有问题】
  9               key为关键字,value为key对应的值
 10     思考:用什么数据结构来存?
 11           最开始想到使用vector,后来想到头插的话,全部都要移动,还是用链表list比较好,有push_front
 12           list越前越新
 13     用vector:
 14         若不存在且未满,头插
 15         若不存在且已满,置最后一个无效pop_back(),头插
 16         若存在,原来的删除,头插
 17 */
 18 struct entry
 19 {
 20     int key;
 21     int value;
 22 };
 23 class LRUCache
 24 {
 25 public:
 26     LRUCache(int capacity)
 27     {
 28         capa = capacity;//
 29         size = 0;
 30     }
 31 
 32     int get(int key)
 33     {//输入:物理块号key
 34      //输出:若物理块号key在内存中,则输出其下标value(总为正);否则,输出-1
 35         auto index = find_if(cache.begin(),cache.end(), [key](const struct entry &a){return a.key == key;});
 36         if(index == cache.end())
 37             return -1;
 38         else
 39             return (*index).value;
 40     }
 41 
 42     void set(int key, int value)
 43     {//输入:物理块号key,
 44      //输出:若物理块号key不在内存中,将value插入cache中。当cache达到其容量capacity,将最近最少使用的在新的插入前置为无效
 45         auto index = find_if(cache.begin(),cache.end(), [key](const struct entry &a){return a.key == key;});//注意写法,尤其是要return
 46         entry data;
 47         data.key = key;
 48         data.value = value;
 49 
 50         if(index == cache.end())//key不存在
 51         {
 52             if(size < capa)//未满
 53             {
 54                 cache.push_front(data);
 55                 size++;
 56             }
 57             else//已满,交换
 58             {
 59                 cache.pop_back();
 60                 cache.push_front(data);
 61             }
 62         }
 63         else//key存在
 64         {
 65             cache.erase(index);
 66             cache.push_front(data);
 67         }            
 68     }
 69     void show()
 70     {
 71         for(auto const &a : cache)
 72             cout << a.key << " ";
 73         cout << endl;
 74         //for(auto const &a : cache)//测试的等同key,可以暂时不显示
 75         //    cout << a.value << " ";
 76         cout << endl;
 77     }
 78 private:
 79     int size;//cache中现有数据块
 80     int capa;//cache容量
 81     list<entry> cache;
 82 };
 83 
 84 int main()
 85 {
 86     LRUCache test(3);
 87 
 88     test.set(4, 4);
 89     test.show();//4
 90 
 91     test.set(3,3);
 92     test.show();//3 4
 93     
 94 
 95     test.set(4,4);
 96     test.show();//4 3
 97 
 98     test.set(2,2);
 99     test.show();//2 4 3 
100 
101     test.set(3,3);
102     test.show();//3 2 4  
103 
104     test.set(1,1);
105     test.show();//1 3 2 
106 
107     test.set(4,4);
108     test.show();//4 1 3 
109 
110     test.set(2,2);
111     test.show();//2 4 1 
112 
113 
114     return 0;
115 }
View Code

  为了使查找、插入和删除都有较高的性能,我们使用一个双向链表 (std::list) 和一个哈希表(std::unordered_map),因为:
  • 哈希表保存每个节点的地址,可以基本保证在 O(1) 时间内查找节点【不用map查找要遍历,复杂度太高】
  • 双向链表插入和删除效率高,单向链表插入和删除时,还要查找节点的前驱节点
  具体实现细节:
  • 越靠近链表头部,表示节点上次访问距离现在时间最短,尾部的节点表示最近访问最少
  • 访问节点时,如果节点存在,把该节点交换到链表头部,同时更新 hash 表中该节点的地址
  • 插入节点时,如果 cache 的 size 达到了上限 capacity,则删除尾部节点,同时要在 hash 表中删除对应的项;新节点插入链表头部

 

  1 #include "stdafx.h"
  2 #include <list>
  3 #include <unordered_map>
  4 #include <iostream>
  5 #include <algorithm>
  6 using namespace std;
  7 /*
  8     LRU算法:最近最少使用,替换在内存中,但又不使用的内存块
  9     题意理解:key应该是物理块块号,而value为内存块号,相当于下标索引【貌似有问题】
 10               key为关键字,value为key对应的值
 11     思考:用什么数据结构来存?
 12           最开始想到使用vector,后来想到头插的话,全部都要移动,还是用链表list比较好,有push_front
 13           list越前越新
 14     用vector:
 15         若不存在且未满,头插
 16         若不存在且已满,置最后一个无效pop_back(),头插
 17         若存在,原来的删除,头插
 18 */
 19 class LRUCache
 20 {
 21 private:
 22     struct CacheNode
 23     {
 24         int key;
 25         int value;
 26         CacheNode(int k, int v):key(k), value(v){}//写个构造函数,方便!!
 27     };
 28 public:
 29     LRUCache(int capacity)
 30     {
 31         this->capacity = capacity;//this的使用,用指针
 32     }
 33 
 34     int get(int key)
 35     {
 36         if(cacheMap.find(key) == cacheMap.end())
 37             return -1;
 38         //把当前访问的节点移到链表头部,并且更新map中该节点的地址!!!自己没想到,访问也是要更新的
 39 
 40         cacheList.push_front(*(cacheMap[key]));//一定要先插,后删,否则,会出现访问问题
 41         cacheList.erase(cacheMap[key]);//!!!要是直接移动,就更好了
 42         //cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);//【用splice()反而超时】
 43         //splice()链表独有的类型;移动:将cacheMap[key]指向的元素移动到cacheList.begin()之前的位置
 44         cacheMap[key] = cacheList.begin();
 45         return cacheMap[key]->value;
 46     }
 47 
 48     void set(int key, int value)
 49     {
 50         if(cacheMap.find(key) == cacheMap.end())//不存在
 51         {
 52             if(cacheList.size() == capacity)//已满
 53             {
 54                 cacheMap.erase(cacheList.back().key);
 55                 cacheList.pop_back();
 56             }
 57             //头插,且更新map
 58             cacheList.push_front(CacheNode(key,value));
 59             cacheMap[key] = cacheList.begin();
 60         }
 61         else
 62         {//存在,则更新位置
 63             cacheMap[key]->value = value;//!!!
 64             //cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
 65             cacheList.push_front(*(cacheMap[key]));
 66             cacheList.erase(cacheMap[key]);//!!!
 67             cacheMap[key] = cacheList.begin();
 68 
 69         }
 70     }
 71 
 72      void show()
 73      {
 74         for(auto const &a : cacheList)
 75             cout << a.key << " ";
 76         cout << endl;
 77         //for(auto const &a : cache)//测试的等同key,可以暂时不显示
 78         //    cout << a.value << " ";
 79         cout << endl;
 80      }
 81 
 82 private:
 83     list<CacheNode> cacheList;
 84     unordered_map<int, list<CacheNode>::iterator> cacheMap;
 85     int capacity;
 86 };
 87 
 88 int main()
 89 {
 90     LRUCache test(3);
 91 
 92     test.set(4, 4);
 93     test.show();//4
 94 
 95     test.set(3,3);
 96     test.show();//3 4
 97     
 98 
 99     test.set(4,4);
100     test.show();//4 3
101 
102     test.set(2,2);
103     test.show();//2 4 3 
104 
105     test.set(3,3);
106     test.show();//3 2 4  
107 
108     test.set(1,1);
109     test.show();//1 3 2 
110 
111     test.set(4,4);
112     test.show();//4 1 3 
113 
114     test.set(2,2);
115     test.show();//2 4 1 
116 
117 
118     return 0;
119 }

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。