算法之缓存LFU

算法之缓存LFU

LFU(Least Frequently Used)最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小”的思路。

举个例子,缓存空间大小为3:

  • put(1,”a”)
  • put(2,”b”)
  • get(1)
  • get(2)
  • put(3,”c”)
  • put(4,”d”) // 按照LFU应该淘汰{3,”c”}

如何设计

  1. 缓存需要存储key-value对.

显然,对于key-value对的存储使用map是很高效的。时间复杂度可以达到O(1)级别。

  1. 假设使用数组存储访问次数:
    • 那么插入数据时,复杂度是O(1),次数直接插入数组末尾
    • 访问时,复杂度是O(1).
    • 淘汰时,复杂度是O(n),遍历淘汰最小值。
  2. 假设使用有序数组存储访问次数:
    • 那么插入数据时,复杂度是O(1),次数直接插入数组末尾
    • 访问时,复杂度是O(logn).
    • 淘汰时,复杂度是O(1),遍历淘汰最小值。
  3. 使用两层链表,外层链表的每个节点代表一组拥有同样访问次数的key,每个节点自身也是一个链表,内层链表确保上次访问时间最早的key位于内层链表的尾部。在这一数据结构下,我们在插入key时判断外层链表尾部元素的freq(次数)是否为0,如果是,将key插入该内层链表的头部,如果否,生成一个只包含key的外层链表,插入到外层链表的尾部。在访问key时,将该key移动到外层链表的下一个节点的头部。这样一来,在移除key时,只需要移除外层链表尾部元素的尾部元素即可,插入、访问、移除的时间复杂度都是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
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
class Node<K,V> {
K key;
V value;
int frequency = 0; //访问次数
Node next; //下一元素
Node prev; //前一元素
NodeQueue nq; //所属的外层链表元素

Node(K key, V value) {
this.key = key;
this.value = value;
}
}
class NodeQueue {
NodeQueue next; //下一元素
NodeQueue prev; //前一元素
Node tail; //尾部Node
Node head; //头部Node

public NodeQueue(NodeQueue next, NodeQueue prev, Node tail, Node head) {
this.next = next;
this.prev = prev;
this.tail = tail;
this.head = head;
}
}
// 非线程安全
// 基于“如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小”的思路。
// 如果访问次数相同的元素有多个,则移除最久访问的那个
public class LFUCache<K, V> {
private NodeQueue tail; //链表尾部的NodeQueue
private int capacity; //容量
private HashMap<K, Node> map; //存储key-value对的HashMap

//构造方法
public LFUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<K, Node>(capacity);
}

private void oneStepUp(Node n) {
n.frequency++; //使用次数+1
boolean singleNodeQ = false; //为true时,代表此NodeQueue中只有一个Node元素
if (n.nq.head == n.nq.tail)
singleNodeQ = true;
if (n.nq.next != null) {
if (n.nq.next.tail.frequency == n.frequency) {
//右侧NodeQueue的访问次数与Node当前访问次数一样,将此Node置于右侧NodeQueue的头部
removeNode(n); //从当前NodeQueue中删除Node
//把Node插入到右侧NodeQueue的头部
n.prev = n.nq.next.head;
n.nq.next.head.next = n;
n.nq.next.head = n;
n.nq = n.nq.next;
} else if (n.nq.next.tail.frequency > n.frequency) {
//右侧NodeQueue的访问次数大于Node当前访问次数,则需要在两个NodeQueue之间插入一个新的NodeQueue
if (!singleNodeQ) {
removeNode(n);
NodeQueue nnq = new NodeQueue(n.nq.next, n.nq, n, n);
n.nq.next.prev = nnq;
n.nq.next = nnq;
n.nq = nnq;
}
//如果当前NodeQueue中只有一个Node,那么其实不需要任何额外操作了
}
} else {
//此NodeQueue的next == null,说明此NodeQueue已经位于外层链表头部了,这时候需要往外侧链表头部插入一个新的NodeQueue
if (!singleNodeQ) {
removeNode(n);
NodeQueue nnq = new NodeQueue(null, n.nq, n, n);
n.nq.next = nnq;
n.nq = nnq;
}
//同样地,如果当前NodeQueue中只有一个Node,不需要任何额外操作
}
}

private Node removeNode(Node n) {
//如果NodeQueue中只有一个Node,那么移除整个NodeQueue
if (n.nq.head == n.nq.tail) {
removeNQ(n.nq);
return n;
}
if (n.prev != null)
n.prev.next = n.next;
if (n.next != null)
n.next.prev = n.prev;
if (n.nq.head == n)
n.nq.head = n.prev;
if (n.nq.tail == n)
n.nq.tail = n.next;
n.prev = null;
n.next = null;
return n;
}

private void removeNQ(NodeQueue nq) {
if (nq.prev != null)
nq.prev.next = nq.next;
if (nq.next != null)
nq.next.prev = nq.prev;
if (this.tail == nq)
this.tail = nq.next;
}

public V get(K key) {
Node n = map.get(key);
if (n == null)
return null;
oneStepUp(n);
return (V)n.value;
}

public void put(K key, V value) {
if (capacity == 0)
return;

Node cn = map.get(key);
//key已存在的情况下,更新value值,并将Node右移
if (cn != null) {
cn.value = value;
oneStepUp(cn);
return;
}
//cache已满的情况下,把外层链表尾部的内层链表的尾部Node移除
if (map.size() == capacity) {
map.remove(removeNode(this.tail.tail).key);
}
//插入新的Node
Node n = new Node(key, value);
if (this.tail == null) {
//tail为null说明此时cache中没有元素,直接把Node封装到NodeQueue里加入
NodeQueue nq = new NodeQueue(null, null, n, n);
this.tail = nq;
n.nq = nq;
} else if (this.tail.tail.frequency == 0) {
//外层链表尾部元素的访问次数是0,那么将Node加入到外层链表尾部元素的头部
// 之所以加到头部,是因为要求“如果访问次数相同的元素有多个,则移除最久访问的那个”
n.prev = this.tail.head;
this.tail.head.next = n;
n.nq = this.tail;
this.tail.head = n;
} else {
//外层链表尾部元素的访问次数不是0,那么实例化一个只包含此Node的NodeQueue,加入外层链表尾部
NodeQueue nq = new NodeQueue(this.tail, null, n, n);
this.tail.prev = nq;
this.tail = nq;
n.nq = nq;
}
//最后把key和Node存入HashMap中
map.put(key, n);
}
}

treemap

还有一种使用 jdk treemap 实现 LFU 的方案,treemap 可以实现对key的排序,其底层是一棵树,实现了map接口:

1
2
3
4
5
private TreeMap<Wrapper<K extends Comparable >,V> caches = new TreeMap<>(); //有序
/**
* 1. 我们在 Wrapper 中记录这个key 被访问的次数
* 2. treemap 排序是针对 key的,所有重写 Wrapper<K> 的compareTo 方法,返回 K 的compareTo 结果。
*/
-------------本文结束感谢您的阅读-------------
坚持分享,您的支持将鼓励我继续创作!
0%