再次简介一下这个算法LRU全称是Least Recently Used,即最近最久未使用的意思。算法每一次将最久未使用的块更新出去。但是呢上一篇笔记附上的百度的代码复杂度实在不堪入目，所以该写还是得写，刚好也分享给大家这个百度前几页没有的O(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
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
| #include<iostream>
#include<vector>
using namespace std;
const int cache_size = 10;
const int memory_size = 100;
struct cache_node
{
cache_node* l_link;
cache_node* r_link;
int cache_id;
int cache_val;
};
void init(cache_node*&head,cache_node*&tail)
{
head=new cache_node({nullptr,nullptr,0,-1});
cache_node *tmp=head;
for(int i(1); i<cache_size; i++)
{
cache_node *x = new cache_node({tmp,nullptr,0,-1});
tmp->r_link=x;
tmp = x;
}
tail = tmp;
}
int main()
{
vector<cache_node*>memory_to_cache(memory_size,nullptr);
cache_node *head,*tail;
init(head,tail);
int n;
cin>>n;
for(int i(0); i<n; i++)
{
int x;
cin>>x;
if(memory_to_cache[x]==nullptr)
{
cout<<tail->cache_val<<"被清出"<<endl;
cout<<x<<"移入栈顶"<<endl;
if(tail->cache_val!=-1)
memory_to_cache[tail->cache_val]=nullptr;
tail->l_link->r_link=nullptr;
tail->r_link=head;
head->l_link=tail;
tail=tail->l_link;
head=head->l_link;
head->l_link=nullptr;
head->cache_val=x;
memory_to_cache[x]=head;
}
else
{
if(head==memory_to_cache[x])
continue;
else
{
cout<<x<<"移入栈顶"<<endl;
memory_to_cache[x]->l_link->r_link=memory_to_cache[x]->r_link;
if(memory_to_cache[x]->r_link!=nullptr)
memory_to_cache[x]->r_link->l_link=memory_to_cache[x]->l_link;
else
{
tail=memory_to_cache[x]->l_link;
}
memory_to_cache[x]->l_link=nullptr;
memory_to_cache[x]->r_link=head;
head->l_link=memory_to_cache[x];
head=memory_to_cache[x];
}
}
}
return 0;
}
|
完整的代码就是上面附的这一些了，然后由于代码比较简单主要是考察逻辑，所以也不再附更多的注释了。值得注意的是上面的代码的第一层if else中有数行功能相同，其实可以通过调整代码位置使其合并。但是过度合并可能会造成一些可读性缺失，这里就不再做深层次的代码优化了。
