【缓存算法】之LFU算法golang简单实现_golang lfu

前言：

缓存算法，一般有LFU和LRU、FIFO等；
LFU：（Least Frequently Used）从字面可以理解，根据历史访问频率来淘汰数据，核心思想就是“如果数据过去被访问多次，那么将来被访问的频率也就越高”；
LRU：（Least Recently Used） 最近最少使用，根据历史访问记录来淘汰数据，“如果数据最近被访问过，那么将来访问的几率也就会很高”。
FIFO:（First In First Out） 先进先出，类似于队列，如果一个数据先进入缓存中，则应该先被淘汰，可以理解为，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。

那么今天谈一下LRU算法的实现：
LRU相当于把数据按照时间排序，这个需求可以是使用栈，或者链表实现，使用链表的话，删除和插入的时间复杂度要小一些，如果从链表头部插入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的数据就是旧数据，我们进行淘汰的时候，只需要把尾部的元素删除就可以了。

实现逻辑可以参考：https://mp.weixin.qq.com/s/oXv03m1J8TwtHwMJEZ1ApQ
代码如下：

package main
import (
	"log"
	"sync"
)

type LFU struct {
	Cap int
	KeyToValue map[int]int
	KeyToFreq  map[int]int
	FreqToKeysMap map[int][]int
	MinFreq int
}

var G_LFU *LFU
var lock *sync.Mutex = new(sync.Mutex)
func NewLFU(cap int)*LFU{
	if G_LFU == nil{
		lock.Lock()
		defer lock.Unlock()
		if G_LFU == nil{
			return &LFU{Cap:cap,KeyToValue:make(map[int]int),
				KeyToFreq:make(map[int]int),
				FreqToKeysMap:make(map[int][]int)}
		}
	}
	return G_LFU
}

/*
todo : 从valueMap 中查找相应的键值对 如果存在，也需要更新下key对应的频率 （使用Map + 栈的结构） 推荐使用map + 链表的结构
 */
func (self *LFU)get(key int)int{
	//1.从value map 中获取
	v,ok := self.KeyToValue[key]
	if !ok{
		return -1
	}

	//2.需要跟新FreqMap
	self.increaseFreq(key)

	return v
}

func (self *LFU)put(key,val int)int{
	if self.Cap <= 0{
		return -1
	}
	//分为两种情况  key 不存在， 存在
	//key 存在， 需要更新freqMap
	if _,exist := self.KeyToValue[key];exist{
		//更新最新的值
		self.KeyToValue[key] = val
		//更新频率
		self.increaseFreq(key)
		return  0
	}
	//todo 如果不存在  需要判断容量是不是满了？
	//如果容量满了 需要根据最小的minFreq，找到对应的key（列表） 删除里面的key
	if len(self.KeyToValue) >= self.Cap{
		// full
		self.removeMinFreq(self.MinFreq)

	}
	//如果容量未满 valueMap里面新加一个key,并且加入到freqMap key=1 对应的列表中
	//同时更新最小的minFreq = 1
	//更新 KV
	self.KeyToValue[key] = val

	//更新 KF
	self.KeyToFreq[key] = 1

	self.MinFreq = 1
	//使用 map + 栈来是实现
	self.FreqToKeysMap[self.MinFreq]  = append(self.FreqToKeysMap[self.MinFreq],key)
	return 0
}

/*
增加key对应的频率
*/
func (self *LFU)increaseFreq(key int ){
	//todo 根据key 获取 freq
	freq,_ := self.KeyToFreq[key]
	//更新 KF
	self.KeyToFreq[key] = freq + 1

	//todo  移除 freqtokeys 建议用链表删除(下面代码使用栈实现)
	for k,v := range self.FreqToKeysMap[freq]{
		if key == v {
			self.FreqToKeysMap[freq] = append(self.FreqToKeysMap[freq][0:k],self.FreqToKeysMap[freq][k+1:]...)
		}
	}
	//todo 将 key 加入到freq+1 对应的列表中
	self.FreqToKeysMap[freq+1] = append(self.FreqToKeysMap[freq+1],key)

	//需要判断freqToKeys的列表，如果空了，需要移除这个freq
	if len(self.FreqToKeysMap[freq]) == 0{
		delete(self.FreqToKeysMap,freq)
		//如果这个freq是 minFreq 需要更新一下minFreq
		if freq == self.MinFreq{
			self.MinFreq++
		}
	}
}

/*todo 从最小频率对应的数组中，删除最初加入的key
*/
func (self *LFU)removeMinFreq(minFreq int){
	//获取要删除的key
	var delKey int
	if len(self.FreqToKeysMap) > 0{
		//删除栈顶
		delKey = self.FreqToKeysMap[minFreq][0]
		self.FreqToKeysMap[minFreq] = self.FreqToKeysMap[minFreq][:len(self.FreqToKeysMap[minFreq])-1]
	}
	//删除 KV 表
	delete(self.KeyToValue,delKey)

	//更新 KF表
	delete(self.KeyToFreq,delKey)
}

func main() {

	cache := NewLFU(2)
	cache.put(1,10)
	cache.put(2,20)

	log.Printf("key = 1;value = %d",cache.get(1))
	log.Printf("key = 2;value = %d",cache.get(2))
	//2020/08/07 10:39:47 key = 1;value = 10
	//2020/08/07 10:39:47 key = 2;value = 20

	//todo 容量已满 所以会删除 key = 1
	cache.put(3,30)

	log.Printf("key = 1;value = %d",cache.get(1))
	//2020/08/07 10:39:47 key = 1;value = -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

主要是：在新增key的时候，需要考虑key是否存在，如果存在了，那么容量是否大于初始化时候设定的cap，如果大于cap了，那么就需要删除旧的key.可以参考下图的流程图实现：