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 Cache设计一个数据结构，它支持两个操作：
1）get(key)：如果key在cache中，则返回对应的value值，否则返回-1
2）set(key,value):如果key不在cache中，则将该(key,value)插入cache中（注意，如果cache已满，则必须把最近最久未使用的元素从cache中删除）；如果key在cache中，则重置value的值。
- 解题思路：题目让设计一个LRU Cache，即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想，LRU全称是Least
Recently Used，即最近最久未使用的意思。在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。下面说一下LRU算法的核心思想，LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
而用什么数据结构来实现LRU算法呢？可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
那么有没有更好的实现办法呢？
那就是利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
总结一下：根据题目的要求，LRU Cache具备的操作：
1）set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
2）get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。
仔细分析一下，如果在这地方利用单链表和hashmap，在set和get中，都有一个相同的操作就是将在命中的节点移到链表头部，如果按照传统的遍历办法来删除节点可以达到题目的要求么？第二，在删除链表末尾节点的时候，必须遍历链表，然后将末尾节点删除，这个能达到题目的时间要求么？
试一下便知结果：
第一个版本实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
#include <iostream>#include <map>#include <algorithm>using namespace std;
struct Node
{ int key;
int value;
Node *next;
};class LRUCache{
private:
int count;
int size ;
map<int,Node *> mp;
Node *cacheList;
public:
LRUCache(int capacity) {
size = capacity;
cacheList = NULL;
count = 0;
}
int get(int key) {
if(cacheList==NULL)
return -1;
map<int,Node *>::iterator it=mp.find(key);
if(it==mp.end()) //如果在Cache中不存在该key， 则返回-1
{
return -1;
}
else
{
Node *p = it->second;
pushFront(p); //将节点p置于链表头部
}
return cacheList->value;
}
void set(int key, int value) {
if(cacheList==NULL) //如果链表为空，直接放在链表头部
{
cacheList = (Node *)malloc(sizeof(Node));
cacheList->key = key;
cacheList->value = value;
cacheList->next = NULL;
mp[key] = cacheList;
count++;
}
else //否则，在map中查找
{
map<int,Node *>::iterator it=mp.find(key);
if(it==mp.end()) //没有命中
{
if(count == size) //cache满了
{
Node * p = cacheList;
Node *pre = p;
while(p->next!=NULL)
{
pre = p;
p= p->next;
}
mp.erase(p->key);
count--;
if(pre==p) //说明只有一个节点
p=NULL;
else
pre->next = NULL;
free(p);
}
Node * newNode = (Node *)malloc(sizeof(Node));
newNode->key = key;
newNode->value = value;
newNode->next = cacheList;
cacheList = newNode;
mp[key] = cacheList;
count++;
}
else
{
Node *p = it->second;
p->value = value;
pushFront(p);
}
}
}
void pushFront(Node *cur) //单链表删除节点,并将节点移动链表头部，O(n)
{
if(count==1)
return;
if(cur==cacheList)
return;
Node *p = cacheList;
while(p->next!=cur)
{
p=p->next;
}
p->next = cur->next; //删除cur节点
cur->next = cacheList;
cacheList = cur;
}
void printCache(){
Node *p = cacheList;
while(p!=NULL)
{
cout<<p->key<<" ";
p=p->next;
}
cout<<endl;
}
};int main(void)
{ /*LRUCache cache(3);
cache.set(2,10);
cache.printCache();
cache.set(1,11);
cache.printCache();
cache.set(2,12);
cache.printCache();
cache.set(1,13);
cache.printCache();
cache.set(2,14);
cache.printCache();
cache.set(3,15);
cache.printCache();
cache.set(4,100);
cache.printCache();
cout<<cache.get(2)<<endl;
cache.printCache();*/
LRUCache cache(2);
cout<<cache.get(2)<<endl;
cache.set(2,6);
cache.printCache();
cout<<cache.get(1)<<endl;
cache.set(1,5);
cache.printCache();
cache.set(1,2);
cache.printCache();
cout<<cache.get(1)<<endl;
cout<<cache.get(2)<<endl;
return 0;
} |
提交之后，提示超时：
因此要对算法进行改进，如果把pushFront时间复杂度改进为O(1)的话是不是就能达到要求呢？
但是 在已知要删除的节点的情况下，如何在O(1)时间复杂度内删除节点？
如果知道当前节点的前驱节点的话，则在O(1)时间复杂度内删除节点是很容易的。而在无法获取当前节点的前驱节点的情况下，能够实现么？对，可以实现的。
具体的可以参照这几篇博文：
http://www.cnblogs.com/xwdreamer/archive/2012/04/26/2472102.html
http://www.nowamagic.net/librarys/veda/detail/261
原理：假如要删除的节点是cur，通过cur可以知道cur节点的后继节点curNext，如果交换cur节点和curNext节点的数据域，然后删除curNext节点（curNext节点是很好删除地），此时便在O(1)时间复杂度内完成了cur节点的删除。
改进版本1：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
void pushFront(Node *cur) //单链表删除节点,并将节点移动链表头部，O(1)
{
if(count==1)
return;
//先删除cur节点 ，再将cur节点移到链表头部
Node *curNext = cur->next;
if(curNext==NULL) //如果是最后一个节点
{
Node * p = cacheList;
while(p->next!=cur)
{
p=p->next;
}
p->next = NULL;
cur->next = cacheList;
cacheList = cur;
}
else //如果不是最后一个节点
{
cur->next = curNext->next;
int tempKey = cur->key;
int tempValue = cur->value;
cur->key = curNext->key;
cur->value = curNext->value;
curNext->key = tempKey;
curNext->value = tempValue;
curNext->next = cacheList;
cacheList = curNext;
mp[curNext->key] = curNext;
mp[cur->key] = cur;
}
}
|
提交之后，提示Accepted，耗时492ms，达到要求。
有没有更好的实现办法，使得删除末尾节点的复杂度也在O(1)？那就是利用双向链表，并提供head指针和tail指针，这样一来，所有的操作都是O(1)时间复杂度。
改进版本2：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
#include <iostream>#include <map>#include <algorithm>using namespace std;
struct Node
{ int key;
int value;
Node *pre;
Node *next;
};class LRUCache{
private:
int count;
int size ;
map<int,Node *> mp;
Node *cacheHead;
Node *cacheTail;
public:
LRUCache(int capacity) {
size = capacity;
cacheHead = NULL;
cacheTail = NULL;
count = 0;
}
int get(int key) {
if(cacheHead==NULL)
return -1;
map<int,Node *>::iterator it=mp.find(key);
if(it==mp.end()) //如果在Cache中不存在该key， 则返回-1
{
return -1;
}
else
{
Node *p = it->second;
pushFront(p); //将节点p置于链表头部
}
return cacheHead->value;
}
void set(int key, int value) {
if(cacheHead==NULL) //如果链表为空，直接放在链表头部
{
cacheHead = (Node *)malloc(sizeof(Node));
cacheHead->key = key;
cacheHead->value = value;
cacheHead->pre = NULL;
cacheHead->next = NULL;
mp[key] = cacheHead;
cacheTail = cacheHead;
count++;
}
else //否则，在map中查找
{
map<int,Node *>::iterator it=mp.find(key);
if(it==mp.end()) //没有命中
{
if(count == size) //cache满了
{
if(cacheHead==cacheTail&&cacheHead!=NULL) //只有一个节点
{
mp.erase(cacheHead->key);
cacheHead->key = key;
cacheHead->value = value;
mp[key] = cacheHead;
}
else
{
Node * p =cacheTail;
cacheTail->pre->next = cacheTail->next;
cacheTail = cacheTail->pre;
mp.erase(p->key);
p->key= key;
p->value = value;
p->next = cacheHead;
p->pre = cacheHead->pre;
cacheHead->pre = p;
cacheHead = p;
mp[cacheHead->key] = cacheHead;
}
}
else
{
Node * p = (Node *)malloc(sizeof(Node));
p->key = key;
p->value = value;
p->next = cacheHead;
p->pre = NULL;
cacheHead->pre = p;
cacheHead = p;
mp[cacheHead->key] = cacheHead;
count++;
}
}
else
{
Node *p = it->second;
p->value = value;
pushFront(p);
}
}
}
void pushFront(Node *cur) //双向链表删除节点,并将节点移动链表头部，O(1)
{
if(count==1)
return;
if(cur==cacheHead)
return;
if(cur==cacheTail)
{
cacheTail = cur->pre;
}
cur->pre->next = cur->next; //删除节点
if(cur->next!=NULL)
cur->next->pre = cur->pre;
cur->next = cacheHead;
cur->pre = NULL;
cacheHead->pre = cur;
cacheHead = cur;
}
void printCache(){
Node *p = cacheHead;
while(p!=NULL)
{
cout<<p->key<<" ";
p=p->next;
}
cout<<endl;
}
};int main(void)
{ LRUCache cache(3);
cache.set(1,1);
//cache.printCache();
cache.set(2,2);
//cache.printCache();
cache.set(3,3);
cache.printCache();
cache.set(4,4);
cache.printCache();
cout<<cache.get(4)<<endl;
cache.printCache();
cout<<cache.get(3)<<endl;
cache.printCache();
cout<<cache.get(2)<<endl;
cache.printCache();
cout<<cache.get(1)<<endl;
cache.printCache();
cache.set(5,5);
cache.printCache();
cout<<cache.get(1)<<endl;
cout<<cache.get(2)<<endl;
cout<<cache.get(3)<<endl;
cout<<cache.get(4)<<endl;
cout<<cache.get(5)<<endl;
return 0;
} |
提交测试结果：
可以发现，效率有进一步的提升。
其实在STL中的list就是一个双向链表，如果希望代码简短点，可以用list来实现：
具体实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <iostream>#include <map>#include <algorithm>#include <list>using namespace std;
struct Node
{ int key;
int value;
};class LRUCache{
private:
int maxSize ;
list<Node> cacheList;
map<int, list<Node>::iterator > mp;
public:
LRUCache(int capacity) {
maxSize = capacity;
}
int get(int key) {
map<int, list<Node>::iterator >::iterator it = mp.find(key);
if(it==mp.end()) //没有命中
{
return -1;
}
else //在cache中命中了
{
list<Node>::iterator listIt = mp[key];
Node newNode;
newNode.key = key;
newNode.value = listIt->value;
cacheList.erase(listIt); //先删除命中的节点
cacheList.push_front(newNode); //将命中的节点放到链表头部
mp[key] = cacheList.begin();
}
return cacheList.begin()->value;
}
void set(int key, int value) {
map<int, list<Node>::iterator >::iterator it = mp.find(key);
if(it==mp.end()) //没有命中
{
if(cacheList.size()==maxSize) //cache满了
{
mp.erase(cacheList.back().key);
cacheList.pop_back();
}
Node newNode;
newNode.key = key;
newNode.value = value;
cacheList.push_front(newNode);
mp[key] = cacheList.begin();
}
else //命中
{
list<Node>::iterator listIt = mp[key];
cacheList.erase(listIt); //先删除命中的节点
Node newNode;
newNode.key = key;
newNode.value = value;
cacheList.push_front(newNode); //将命中的节点放到链表头部
mp[key] = cacheList.begin();
}
}
};int main(void)
{ LRUCache cache(3);
cache.set(1,1);
cache.set(2,2);
cache.set(3,3);
cache.set(4,4);
cout<<cache.get(4)<<endl;
cout<<cache.get(3)<<endl;
cout<<cache.get(2)<<endl;
cout<<cache.get(1)<<endl;
cache.set(5,5);
cout<<cache.get(1)<<endl;
cout<<cache.get(2)<<endl;
cout<<cache.get(3)<<endl;
cout<<cache.get(4)<<endl;
cout<<cache.get(5)<<endl;
return 0;
} |
在前一篇文章中通过leetcode的一道题目了解了LRU算法的具体设计思路，下面继续来探讨一下另外两种常见的Cache算法：FIFO、LFU
1.FIFO算法
FIFO（First in First out），先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想，比如作业调度（先来先服务），为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维，具备公平性，并且实现起来简单，直接使用数据结构中的队列即可实现。
在FIFO Cache设计中，核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。在FIFO Cache中应该支持以下操作;
get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；
set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最早进入Cache的数据。
举个例子：假如Cache大小为3，访问数据序列为set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5)
则Cache中的数据变化为：
(1,1) set(1,1)
(1,1) (2,2) set(2,2)
(1,1) (2,2) (3,3) set(3,3)
(2,2) (3,3) (4,4) set(4,4)
(2,2) (3,3) (4,4) get(2)
(3,3) (4,4) (5,5) set(5,5)
那么利用什么数据结构来实现呢？
下面提供一种实现思路：
利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。
2.LFU算法
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子：
假设缓存大小为3，数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，
则在set(4,4)时对于LFU算法应该淘汰(3,3)，而LRU应该淘汰(1,1)。
那么LFU Cache应该支持的操作为：
get(key)：如果Cache中存在该key，则返回对应的value值，否则，返回-1；
set(key,value)：如果Cache中存在该key，则重置value值；如果不存在该key，则将该key插入到到Cache中，若Cache已满，则淘汰最少访问的数据。
为了能够淘汰最少使用的数据，因此LFU算法最简单的一种设计思路就是 利用一个数组存储 数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。
另外还有一种实现思路就是利用 小顶堆+hashmap，小顶堆插入、删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效。
如果哪位朋友有更高效的实现方式（比如O(1)时间复杂度），不妨探讨一下，不胜感激。
原文链接：[http://wely.iteye.com/blog/2227844]