LFU算法
洪笳淏 Lv4
 2021-09-22 13:00:00      

LFU算法介绍

LFU缓存机制

  LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。对比于在LRU算法中介绍的LRU 缓存淘汰算法，LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久没被使用的数据。LRU 算法的核心数据结构是使用哈希链表 LinkedHashMap，首先借助链表的有序性使得链表元素维持插入顺序，同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。

  而 LFU 算法相当于是把数据按照访问频次进行排序，这个需求恐怕没有那么简单，而且还有一种情况，如果多个数据拥有相同的访问频次，我们就得删除最早插入的那个数据。也就是说 LFU 算法是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。

算法描述

  要求你写一个类，接受一个 capacity 参数，实现 get 和 put 方法：

1
2
3
4
5
6
7
type LFUCache struct {}

func Constructor(capacity int) LFUCache {} // 构造容量为 capacity 的缓存

func (this *LFUCache) Get(key int) int {}  // 在缓存中查询 key

func (this *LFUCache) Put(key int, val int) {} // 将 key 和 val 存入缓存

Get(key) 方法会去缓存中查询键 key，如果 key 存在，则返回 key 对应的 val，否则返回 -1。

Put(key, value) 方法插入或修改缓存。如果 key 已存在，则将它对应的值改为 val；如果 key 不存在，则插入键值对 (key, val)。

  当缓存达到容量 capacity 时，则应该在插入新的键值对之前，删除使用频次（后文用 freq 表示）最低的键值对。如果 freq 最低的键值对有多个，则删除其中最旧的那个。

思路分析

  首先我们需要理解LFU算法执行过程的几个事实：

  1. 调用Get(key int)方法时，要返回key对应的val。
  2. 只要用到Get或Put方法访问一次某个key，该key的freq就要加一。
  3. 如果在容量满了的时候插入，则需要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。

  现在我们来逐一解决:

  1. 调用Get(key int)方法时，要返回key对应的val。

  使用一个 HashMap 存储 key 到 val 的映射，就可以快速计算 get(key)。

1
keyToVal := make(map[int]int)
  1. 只要用到Get或Put方法访问一次某个key，该key的freq就要加一。

  使用一个 HashMap 存储 key 到 freq 的映射，就可以快速操作 key 对应的 freq。

1
keyToFreq := make(map[int]int)
  1. 如果在容量满了的时候插入，则需要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。

  这个需求应该是 LFU 算法的核心，所以我们分开说。

  • 首先，肯定是需要 freq 到 key 的映射，用来找到 freq 最小的 key。
  • 将 freq 最小的 key 删除，那你就得快速得到当前所有 key 最小的 freq 是多少。想要时间复杂度 O(1) 的话，肯定不能遍历一遍去找，那就用一个变量 minFreq 来记录当前最小的 freq 吧。
  • 可能有多个 key 拥有相同的 freq，所以 freq 对 key 是一对多的关系，即一个 freq 对应一个 key 的列表。
  • 希望 freq 对应的 key 的列表是存在时序的，便于快速查找并删除最旧的 key。
  • 希望能够快速删除 key 列表中的任何一个 **key**，因为如果频次为 freq 的某个 key 被访问，那么它的频次就会变成 freq+1，就应该从 freq 对应的 key 列表中删除，加到 freq+1 对应的 key 的列表中。
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
freqToKeys := make(map[int]*LinkedHashSet)
minFreq := 0

type node struct {
    key		int
    prev	*node
    next	*node
}

type DoubleList struct {
    head	*node
    tail	*node
    size	int
}

func constructorDL() *DoubleList {
    dh := &node{
        key		:	0,
    }
    dt := &node {
        key		:	0,
    }
    dh.next,dt.prev = dt,dh
    return &DoubleList{
        head	:	dh,
        tail	:	dt,
        size	:	0,
    }
}

type LinkedHashSet struct {
    hashMap		map[int]*node
    doubleList	*DoubleList    
}

func constructorLH() *LinkedHashSet {
    m := make(map[int]*node)
    dl := constructorDL()
    return &LinkedHashSet{
        hashMap		:	m,
        doubleList	:	dl,
    }
}

  LinkedHashSet 顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 O(1) 时间内访问或删除其中的元素，又可以保持插入的时序。

综上，我们可以写出 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
type LFUCache struct {
    keyToVal	map[int]int				// key 到 val 的映射，我们后文称为 KV 表
    keyToFreq	map[int]int				// key 到 freq 的映射，我们后文称为 KF 表
    freqToKeys	map[int]*LinkedHashSet	// freq 到 key 列表的映射，我们后文称为 FK 表
    minFreq		int						// 记录最小的频次
    cap			int						// 记录 LFU 缓存的最大容量
}

func Constructor(capacity) LFUCache {
    kv := make(map[int]int)
    kf := make(map[int]int)
    fk := make(map[int]*LinkedHashSet)
    return LFUCache{
        keyToVal	:	kv,
        keyToFreq	:	kf,
        freqToKeys	:	fk,
        minFreq		:	0,
        cap			:	capacity,
    }
}

func (this *LFUCache) Get(key int) int {}  // 在缓存中查询 key

func (this *LFUCache) Put(key int, val int) {} // 将 key 和 val 存入缓存

代码框架

实现Get(key int)方法

  逻辑很简单，返回 key 对应的 val，然后增加 key 对应的 freq：

1
2
3
4
5
6
7
func (this *LFUCache) Get(key int) int {
    if _,ok := this.keyToVal[key]; !ok {
        return -1
    }
    this.increaseFreq(key)
    return this.keyToVal[key]
}

  增加key对应的freq是LFU算法的核心，所以我们干脆抽象一个方法increaseFreq，这样Get方法就比较简洁。

实现Put(key int,val int) 方法

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
func (this *LFUCache) Put(key int, value int) {
    if this.cap <= 0 {
        return
    }
    
    if _,ok := this.keyToVal[key]; ok {  // 若key已存在，修改对应的val即可
        this.keyToVal[key] = value
        this.increaseFreq(key)
        return
    }
    
    // key不存在，需要插入
    // 容量已满的话需要淘汰一个freq最小的key
    if this.cap == len(this.keyToVal) {
        this.removeMinFreqKey()
    }
    
    // 插入key和val，对应的freq为1
    this.keyToVal[key] = value	// 插入KV表
    this.keyToFreq[key] = 1		// 插入KF表
    if _,ok := this.freqToKeys[1]; !ok {  // 如果没有freq为1的LinkedHashSet，则生成一个
        this.freqToKeys[1] = constructorLH()
    }
    this.addRecently(key,1)  // 插入新key后的freq肯定是1
    this.minFreq = 1
}

实现核心逻辑（中间抽象层）

实现removeMinFreqKey方法

1
2
3
4
5
6
7
8
9
10
11
func (this *LFUCache) removeMinFreqKey() {
    keyList := this.freqToKeys[this.minFreq].doubleList	// 获得最小freq的LinkedHashSet
    deleteKey := keyList.removeFirst()	// 删除LinkedHashSet的双链表头的元素
    delete(this.freqToKeys[this.minFreq].hashMap,deleteKey.key)		// 删除LinkedHashSet的哈希表对应元素
    
    if len(this.freqToKeys[this.minFreq].hashMap) == 0 {
        delete(this.freqToKeys,this.minFreq)
    }
    delete(this.keyToVal,deleteKey.key)		// 更新KV表
    delete(this.keyToFreq,deleteKey.key)	// 更新KF表
}

  删除某个key肯定是要同时映射三个表的，借助minFreq参数可以从FK表中找到freq最小的keyList，删除其表头元素即可，同时删除Fk表中freq最小的hashMap对应的元素。然后根据要被淘汰的deleteKey删除其余两个表中的映射关系。

  这里有个细节问题，如果keyList中只有一个元素，那么删除之后minFreq对应的key列表就为空了，也就是minFreq变量需要更新。实际上没办法快速计算minFreq，只能线性遍历FK表或者KF表来计算，这样肯定不能保证 O(1) 的时间复杂度。但是，其实这里没必要更新minFreq变量，因为你想想removeMinFreqKey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minFreq更新成 1，所以说即便这里minFreq变了，我们也不需要管它。

实现increaseFreq方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (this *LFUCache) increaseFreq(key int) {
    freq := this.keyToFreq[key]
    this.keyToFreq[key] = freq+1	// 更新KF表
    // 将key从freq对应的列表和哈希表中删除
    this.freqToKeys[freq].doubleList.remove(this.freqToKeys[freq].hashMap[key])
    delete(this.freqToKeys[freq].hashMap,key)
    if len(this.freqToKeys[freq].hashMap) == 0 { // 如果 freq 对应的列表空了，移除这个 freq
        delete(this.freqToKeys,freq)
        if freq == this.minFreq {  // 如果这个 freq 恰好是 minFreq，更新 minFreq
            this.minFreq++
        }
    }
    // 将key加入到freq+1对应的列表和哈希表中
    if _,ok := this.freqToKeys[freq+1]; !ok {
        this.freqToKeys[freq+1] = constructorLH()
    }
    this.addRecently(key,freq+1)
}

实现addRecently方法

1
2
3
4
5
6
7
func (this *LFUCache) addRecently(key int, freq int) {
    x := &node{
        key		:	key,
    }
    this.freqToKeys[freq].doubleList.addLast(x)
    this.freqToKeys[freq].hashMap[key] = x
}

  在插入新的节点时，需要修改FK表的哈希表和双链表。

对底层数据结构进行操作

  该层的主要作用是对我们实现的LinkedHashSet结构封装一些通用操作，用以满足FK表的更新和删除操作，主要包含以下几个方法：

  1. 删除DoubleList中某一节点的方法remove(x *node)。
  2. 删除DoubleList中表首元素的方法removeFirst()。
  3. 在DoubleList中表尾部增加新元素的addLast()。

实现remove方法

1
2
3
4
func (dl *DoubleList) remove(x *node) {
    x.prev.next = x.next
    x.next.prev = x.prev
}

实现removeFirst方法

1
2
3
4
5
6
7
8
func (dl *DoubleList) removeFirst() *node {
    if dl.head.next == dl.tail {
        return nil
    }
    first := dl.head.next
    dl.remove(first)
    return first
}

实现addLast方法

1
2
3
4
5
6
func (dl *DoubleList) addLast(x *node) {
    x.prev = dl.tail.prev
    x.next = dl.tail
    dl.tail.prev.next = x
    dl.tail.prev = x
}

总体算法

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
// ###############基础数据结构###################
type node struct {
    key		int
    prev	*node
    next	*node
}

// 双端链表
type DoubleList struct {
    head	*node
    tail	*node
    size	int
}

// 初始化双端链表
func constructorDL() *DoubleList {
    dh := &node{
        key		:	0,
    }
    dt := &node {
        key		:	0,
    }
    dh.next,dt.prev = dt,dh
    return &DoubleList{
        head	:	dh,
        tail	:	dt,
        size	:	0,
    }
}

// 构造LinkedHashSet作为freqToKeys表
type LinkedHashSet struct {
    hashMap		map[int]*node
    doubleList	*DoubleList    
}

// 初始化LinkedHashSet
func constructorLH() *LinkedHashSet {
    m := make(map[int]*node)
    dl := constructorDL()
    return &LinkedHashSet{
        hashMap		:	m,
        doubleList	:	dl,
    }
}

// ##############底层方法（用于直接操作数据结构）####################

// 删除双端链表中的某一节点
func (dl *DoubleList) remove(x *node) {
    x.prev.next = x.next
    x.next.prev = x.prev
} 

// 删除双端链表表头元素
func (dl *DoubleList) removeFirst() *node {
    if dl.head.next == dl.tail {
        return nil
    }
    first := dl.head.next
    dl.remove(first)
    return first
}

// 在双端链表尾部添加新元素
func (dl *DoubleList) addLast(x *node) {
    x.prev = dl.tail.prev
    x.next = dl.tail
    dl.tail.prev.next = x
    dl.tail.prev = x
} 

// ###############LFU类的实现##################
type LFUCache struct {
    keyToVal	map[int]int				// key 到 val 的映射，我们后文称为 KV 表
    keyToFreq	map[int]int				// key 到 freq 的映射，我们后文称为 KF 表
    freqToKeys	map[int]*LinkedHashSet	// freq 到 key 列表的映射，我们后文称为 FK 表
    minFreq		int						// 记录最小的频次
    cap			int						// 记录 LFU 缓存的最大容量
}

// 初始化LFU类，加载KV表、KF表以及FK表，设置最小频率树minFreq
func Constructor(capacity int) LFUCache {
    kv := make(map[int]int)
    kf := make(map[int]int)
    fk := make(map[int]*LinkedHashSet)
    return LFUCache{
        keyToVal	:	kv,
        keyToFreq	:	kf,
        freqToKeys	:	fk,
        minFreq		:	0,
        cap			:	capacity,
    }
}

// Get方法
func (this *LFUCache) Get(key int) int {
    if _,ok := this.keyToVal[key]; !ok {
        return -1
    }
    this.increaseFreq(key)
    return this.keyToVal[key]
}

// Put方法
func (this *LFUCache) Put(key int, value int)  {
    if this.cap <= 0 {
        return
    }
    
    if _,ok := this.keyToVal[key]; ok {  // 若key已存在，修改对应的val即可
        this.keyToVal[key] = value
        this.increaseFreq(key)
        return
    }
    
    // key不存在，需要插入
    // 容量已满的话需要淘汰一个freq最小的key
    if this.cap <= len(this.keyToVal) {
        this.removeMinFreqKey()
    }
    
    // 插入key和val，对应的freq为1
    this.keyToVal[key] = value	// 插入KV表
    this.keyToFreq[key] = 1		// 插入KF表
    if _,ok := this.freqToKeys[1]; !ok {  // 如果没有freq为1的LinkedHashSet，则生成一个
        this.freqToKeys[1] = constructorLH()
    }
    this.addRecently(key,1)  // 插入新key后的freq肯定是1
    this.minFreq = 1
}

// ################中间抽象层####################

// 删除使用频率最低节点
func (this *LFUCache) removeMinFreqKey() {
    keyList := this.freqToKeys[this.minFreq].doubleList	// 获得最小freq的LinkedHashSet
    deleteKey := keyList.removeFirst()	// 删除LinkedHashSet的双链表头的元素
    delete(this.freqToKeys[this.minFreq].hashMap,deleteKey.key)		// 删除LinkedHashSet的哈希表对应元素
    
    if len(this.freqToKeys[this.minFreq].hashMap) == 0 {
        delete(this.freqToKeys,this.minFreq)
    }
    delete(this.keyToVal,deleteKey.key)		// 更新KV表
    delete(this.keyToFreq,deleteKey.key)	// 更新KF表
}

// 增加某一节点的使用频数
func (this *LFUCache) increaseFreq(key int) {
    freq := this.keyToFreq[key]
    this.keyToFreq[key] = freq+1	// 更新KF表
    // 将key从freq对应的列表和哈希表中删除
    this.freqToKeys[freq].doubleList.remove(this.freqToKeys[freq].hashMap[key])
    delete(this.freqToKeys[freq].hashMap,key)
    if len(this.freqToKeys[freq].hashMap) == 0 { // 如果 freq 对应的列表空了，移除这个 freq
        delete(this.freqToKeys,freq)
        if freq == this.minFreq {  // 如果这个 freq 恰好是 minFreq，更新 minFreq
            this.minFreq++
        }
    }
    // 将key加入到freq+1对应的列表和哈希表中
    if _,ok := this.freqToKeys[freq+1]; !ok {
        this.freqToKeys[freq+1] = constructorLH()
    }
    this.addRecently(key,freq+1)
} 

// 对最近使用的节点的处理
func (this *LFUCache) addRecently(key int, freq int) {
    x := &node{
        key		:	key,
    }
    this.freqToKeys[freq].doubleList.addLast(x)
    this.freqToKeys[freq].hashMap[key] = x
}
  • Post title：LFU算法
  • Post author：洪笳淏
  • Create time：2021-09-22 13:00:00
  • Post link：https://jiahaohong1997.github.io/2021/09/22/LFU算法/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments