介绍
LRU（Least Recently Used）和LFU（Least Frequently Used）是两种常见的缓存淘汰算法， 用于在缓存空间有限的情况下选择合适的缓存对象进行淘汰，以提高缓存的利用效率。
LRU算法基于”最近最少使用”的原则进行淘汰。它维护一个缓存的访问顺序链表，当有新的数据被访问时，如果数据已经在缓存中，则将其移到链表头部；如果数据不在缓存中，则将其添加到链表头部。当需要淘汰数据时，选择链表尾部的数据进行淘汰，因为尾部的数据是最近最少被访问的数据。
LFU算法基于”最不经常使用”的原则进行淘汰。它维护一个缓存对象的访问频次，对于每个访问到的对象，增加其访问频次。当需要淘汰数据时，选择访问频次最低的数据进行淘汰。
LRU和LFU算法都有各自的优势和适用场景：
- LRU算法适用于访问具有时间局部性的数据，即最近被访问的数据可能在将来一段时间内仍然会被访问。LRU算法相对较简单，容易实现，适用于大多数场景。但是，当存在”热点数据”（被频繁访问的数据）时，LRU算法可能无法有效地保证缓存的命中率。
- LFU算法适用于访问具有访问频次局部性的数据，即访问频次高的数据很可能在将来一段时间内仍然会被频繁访问。LFU算法需要维护每个对象的访问频次计数，相对于LRU算法来说更加复杂。LFU算法在面对热点数据的场景下表现较好，但在某些场景下可能存在”频次突变”的问题，即频次高的数据突然不再被访问，但因为频次计数较高而长时间无法被淘汰。
在实际应用中，我们可以根据具体的场景和需求选择合适的缓存淘汰策略，或者结合两种算法进行混合使用，以达到更好的缓存性能。
146. LRU 缓存 中等
下面用javascript代码演示一下LRU缓存：
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
|
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get (key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
return -1;
}
put (key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey);
}
this.cache.set(key, value);
}
}
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));
cache.put(3, 3);
console.log(cache.get(2));
console.log(cache.get(3));
cache.put(4, 4);
console.log(cache.get(1));
console.log(cache.get(3));
console.log(cache.get(4));
|
这段代码的技巧就在于使用了ES6的Map和迭代器的功能。Map 的遍历顺序就是插入顺序，使用Map.prototype.keys()：返回键名的遍历器。然后我们使用迭代器的 next() 方法获取数据结构的第一个成员,也就是最旧的。然后通过 value 属性来获取它的值。拿到最旧的key就可以删除它，最后重新设置key。（Map具有LRU特性）
460. LFU 缓存 困难
javascript代码实现LFU：
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
|
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.frequency = new Map();
this.minFrequency = 0;
}
get(key) {
if (this.cache.has(key)) {
const { value, freq } = this.cache.get(key);
this.updateFrequency(key, freq);
return value;
}
return -1;
}
put(key, value) {
if (this.capacity === 0) return;
if (this.cache.has(key)) {
const { freq } = this.cache.get(key);
this.cache.set(key, { value, freq });
this.updateFrequency(key, freq);
} else {
if (this.cache.size >= this.capacity) {
const leastFreq = this.frequency.get(this.minFrequency);
const deleteKey = leastFreq.keys().next().value;
leastFreq.delete(deleteKey);
this.cache.delete(deleteKey);
}
this.cache.set(key,{value,freq: 1});
if (!this.frequency.has(1)) {
this.frequency.set(1,new Set())
}
this.frequency.get(1).add(key);
this.minFrequency = 1;
}
}
updateFrequency(key, freq) {
const freqList = this.frequency.get(freq);
freqList.delete(key);
if (freq === this.minFrequency && freqList.size === 0) {
this.minFrequency++;
}
if (!this.frequency.has(freq + 1)) {
this.frequency.set(freq + 1, new Set());
}
this.frequency.get(freq + 1).add(key);
this.cache.get(key).freq = freq + 1;
}
}
const cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));
cache.put(3, 3);
console.log(cache.get(2));
console.log(cache.get(3));
cache.put(4, 4);
console.log(cache.get(2));
console.log(cache.get(3));
console.log(cache.get(4));
|
同样这里使用了 Set 数据结构的 LRU 特性，在 frequency 对应的 Map 里面放在着每种访问次数对应的 key 组成的 Set。也就是说，访问次数相同的元素所对应的 key 存放在同一个 Set 中。这里要注意的就是新增元素时，设置访问次数为1的 Set为空,并且添加访问该元素的 key，同时设置最小访问次数为1。如果某个元素它之前的访问次数为最小访问次数，而且没有其他元素与该元素的访问次数相同，同时更新最小访问次数和该元素的访问次数，也就是该元素的访问次数 + 1，并且设置对应的 Set 数据结构为空，把当前访问的 key 添加进去。
go代码演示LRU缓存：
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
| package main
import "fmt"
type LRUCache struct {
size int
capacity int
cache map[int]*DoubleLinkNode
head, tail *DoubleLinkNode
}
type DoubleLinkNode struct {
key, value int
prev, next *DoubleLinkNode
}
func initDoubleLinkNode(key, value int) *DoubleLinkNode {
return &DoubleLinkNode{
key: key,
value: value,
}
}
func Constructor(capacity int) LRUCache {
l := LRUCache{
capacity: capacity,
cache: map[int]*DoubleLinkNode{},
head: initDoubleLinkNode(0, 0),
tail: initDoubleLinkNode(0, 0),
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}
func (l *LRUCache) Get(key int) int {
if _, ok := l.cache[key]; !ok {
return -1
}
node := l.cache[key]
l.moveToHead(node)
return node.value
}
func (l *LRUCache) Put(key, value int) {
if _, ok := l.cache[key]; !ok {
node := initDoubleLinkNode(key, value)
l.cache[key] = node
l.addToHead(node)
l.size++
if l.size > l.capacity {
removed := l.removeTail()
delete(l.cache, removed.key)
l.size--
}
} else {
node := l.cache[key]
node.value = value
l.moveToHead(node)
}
}
func (l *LRUCache) addToHead(node *DoubleLinkNode) {
node.prev = l.head
node.next = l.head.next
l.head.next.prev = node
l.head.next = node
}
func (l *LRUCache) removeNode(node *DoubleLinkNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (l *LRUCache) moveToHead(node *DoubleLinkNode) {
l.removeNode(node)
l.addToHead(node)
}
func (l *LRUCache) removeTail() *DoubleLinkNode {
node := l.tail.prev
l.removeNode(node)
return node
}
func main() {
cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
fmt.Println(cache.Get(1))
cache.Put(3, 3)
fmt.Println(cache.Get(2))
cache.Put(4, 4)
fmt.Println(cache.Get(1))
fmt.Println(cache.Get(3))
fmt.Println(cache.Get(4))
}
|
代码使用了双向链表 + map实现了LRU数据结构。代码中采用了首尾虚拟节点，访问到的节点移动到头部，超出容量时删除尾部的节点。
go代码实现LFU数据结构：
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
| package main
import "fmt"
type LFUCache struct {
size int
capacity int
minFreq int
cache map[int]*Node
freq map[int]*DLinkedList
}
type Node struct {
key int
value int
freq int
prev, next *Node
}
type DLinkedList struct {
head, tail *Node
}
func Constructor(capacity int) LFUCache {
return LFUCache{
capacity: capacity,
cache: make(map[int]*Node),
freq: make(map[int]*DLinkedList),
}
}
func InitDLinkedList() *DLinkedList {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return &DLinkedList{
head: head,
tail: tail,
}
}
func (d *DLinkedList) AddToHead(node *Node) {
node.prev = d.head
node.next = d.head.next
d.head.next.prev = node
d.head.next = node
}
func (d *DLinkedList) Remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
node.prev = nil
node.next = nil
}
func (d *DLinkedList) RemoveTail() *Node {
if d.IsEmpty() {
return nil
}
last := d.tail.prev
d.Remove(last)
return last
}
func (d *DLinkedList) IsEmpty() bool {
return d.head.next == d.tail
}
func (l *LFUCache) Get(key int) int {
if node, ok := l.cache[key]; ok {
l.addFreq(node)
return node.value
}
return -1
}
func (l *LFUCache) Put(key, value int) {
if l.capacity == 0 {
return
}
if node, ok := l.cache[key]; ok {
node.value = value
l.addFreq(node)
} else {
if l.size >= l.capacity {
node := l.freq[l.minFreq].RemoveTail()
delete(l.cache, node.key)
l.size--
}
node := &Node{key: key, value: value, freq: 1}
l.cache[key] = node
if l.freq[1] == nil {
l.freq[1] = InitDLinkedList()
}
l.freq[1].AddToHead(node)
l.minFreq = 1
l.size++
}
}
func (l *LFUCache) addFreq(node *Node) {
n := node.freq
l.freq[n].Remove(node)
if l.minFreq == n && l.freq[n].IsEmpty() {
l.minFreq++
delete(l.freq, n)
}
node.freq++
if l.freq[node.freq] == nil {
l.freq[node.freq] = InitDLinkedList()
}
l.freq[node.freq].AddToHead(node)
}
func main() {
cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)
fmt.Println(cache.Get(1))
cache.Put(3, 3)
fmt.Println(cache.Get(2))
fmt.Println(cache.Get(3))
cache.Put(4, 4)
fmt.Println(cache.Get(1))
fmt.Println(cache.Get(3))
fmt.Println(cache.Get(4))
}
|
cache存储对应的数据节点，但是可能会出现节点访问次数相同的情况。对应访问次数相同的节点，我们把放在一个双向链表中，然后根据LRU最近最少使用，超过容量的时候删除双向链表尾部的节点。拿到节点的key,之后就能从map中删除储存的节点了。