LRU

简单介绍

还记得第一次听到些词是在计算机组成原理课上,讲高速缓存存储器-cache章节涉及到的,当时一脸懵逼不知道说的是啥。

  • LRU - 最近最少使用策略(Lastest Recently Used)
  • LFU - 最少使用策略(Lastest Frequently Used)
  • FIFO - 先进先出(First In First Out)

大家都是比较实在的人,相信大家肯定也不喜欢硬背这些东西,其实他们离我们生活很近,只是我们忽略了没有在意它们。

你可以试想一下如果现在有一大堆书,你会以什么方式扔这些书,对应⼀下,你的选择标准是不是和上⾯的三种策略神似呢?

链表实现LRU

下面用链表实现以下LRU策略。

要求是:链表做存储,当链表满了,我们就按照LRU最近最少使用策略的丢数据。

1.链表数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LRULinkedList<T> {

// 记录当前容量
private int CAPACITY = 0;

// 默认容量
private int DEFAULT_CAPACITY = 5;

// 设置守卫简化代码
private SNode head;

// 链表节点
class SNode<T> {
// 数据
T data;
// 指向下一个节点的指针
SNode next;
}
}

守卫

守卫的意思是守护边界,用于管理边界的一些操作,因为边界操作往往会出现很多种情况十分复杂,利用守卫就可以屏蔽掉多种情况,这是编码的一种技巧。

下面用两组场景,说一下写它的原因。

第一组

比如往链表结点p后⾯插⼊⼀个新的结点,正常插入只需要这样写。

1
2
newNode->next = p->next; 
p->next = newNode;

但是,当我们要向⼀个空链表中插⼊第⼀个结点,上面两行代码就不工作了,代码要在原有的基础上写一层判断,像下面这样子。

1
2
3
if(head == null){
head = newNode;
}

第二组

再比如删除链表中的节点,如果要删除p节点的后继节点,只需要这样写

1
p->next = p->next->next;

但是如果要删除最后一个节点,就要多写下面的内容。

1
2
3
if (head->next == null) { 
head = null;
}

这么写简直太糟糕了,条件少还能吼得住,条件多少一个就是bug,怪不得老加班。那问题来了,有没有办法省掉第一组和第二组判断的那部分代码呢?

这时候就要用守卫来解决了,带守卫的链表叫带头链表,没有守卫节点的叫不带头链表,守卫在链表中并不存任何数据,像下图这样。

title

这样的技巧在数据结构与算法代码编写中十分常用,⽐如插⼊排序、归并排序、动态规划等,如果感觉有点不太理解,带守卫和不带守卫都可以尝试着写写,debug一下看看。

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
// 添加
public void add(T data) {

SNode preNode = findPreNode(data);

if(preNode != null){
// 删除前一个节点的下一个节点,也就是当前节点有点绕。。
delete(preNode);
// 插入到头
insertBegin(data);
}else{
if(CAPACITY > DEFAULT_CAPACITY){
// 删除最后节点
deleteEnd();
}
insertBegin(data);
}

}

// 删除队尾
public void deleteEnd() {
SNode ptr = head;

// 判断队列是否为空
if(ptr.next == null){
return;
}

// 找到倒数第二个节点
while(ptr.next.next != null){
ptr = ptr.next;
}

// 删除最后节点
SNode tmp = ptr.next;
ptr.next = null;
tmp = null;
CAPACITY--;
}

public void insertBegin(T data) {
// 插入对头
SNode next = head.next;
head.next = new SNode(data,next);
CAPACITY++;
}

// 删除当前节点
public void delete(SNode preNode) {
SNode tmp = preNode.next;
preNode.next = tmp.next;
tmp = null;
CAPACITY--;

}

// 寻找data对应的前一个节点
public SNode findPreNode(T data) {
SNode node = head;
while(node.next != null){
if(data.equals(node.next.data)){
return node;
}
node = node.next;
}

return null;
}

方便折腾下面是源码