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 }
为了使查找、插入和删除都有较高的性能，我们使用一个双向链表 (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