教程集 > Golang编程 > golang教程 > 正文【缓存算法】之LFU算法golang简单实现

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

发布时间：2021-12-19 编辑：jiaochengji.com

教程集为您提供【缓存算法】之LFU算法golang简单实现等资源，欢迎您收藏本站，我们将为您提供最新的【缓存算法】之LFU算法golang简单实现资源

缓存算法，一般有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
代码如下：

<pre><code class="lang-go hljs">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 } </code></pre>

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

<blockquote class="layui-elem-quote" style="width: 100%;overflow:hidden"> 作者： u014779917
链接： https://blog.csdn.net/u014779917/article/details/107857521
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
</blockquote>

到此这篇关于“【缓存算法】之LFU算法golang简单实现”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
SpringMVC整合EhCache实现对象缓存的详解
 【缓存算法】之LFU算法golang简单实现
 数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
 Golang 一致性Hash算法实现
 Go从入门到精通系列视频之go编程语言密码学哈希算法
 使用 PHP 实现 LRU 缓存淘汰算法
 php页面缓存的例子(减经cpu与mysql负担)
MySQL新手入门教程:mysql优化入门
 Golang缓存生态
 谈谈一致性哈希算法及其 Golang 实现（含负载均衡算法概述）

上一篇：5分钟入门golang module 下一篇：Windows10 golang gRPC环境搭建

[关闭]

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

最近更新

浏览排行