关于 lru 和 lfu算法的简单实现

关于 lru 和 lfu的简单实现前言一、最近最久未使用LRU二、最不经常使用(LFU)后记参考前言lru和lfu是两种经典的内存淘汰算法前者是淘汰最近最久未使用的空间后者是淘汰最不经常使用。乍一听感觉差不多其实还是有些区别的。lru 关注的是时间先后优先淘汰时间范围内最不经常用的空间。 lfu 关注的是已使用的次数优先淘汰那些使用次数最少的空间。在实际的应用中lru 要使用的多些因为对于大部分情况最近用到的未来用到的概率比较大。 lfu 主要是应对lru 无法应对 那些以前的热点数据但是由于某些原因最近不常用而被淘汰的场景。说的好不如做得好。 下面对照 leecode 的两个题实现了两个简易版本。一、最近最久未使用LRULRU代码如下packagemainimportcontainer/listtypeLRUCacheNodestruct{KeyintValueint}typeLRUCachestruct{LRUMapmap[int]*list.Element ValueList*list.List Capacityint}funcConstructor(capacityint)LRUCache{returnLRUCache{LRUMap:make(map[int]*list.Element),ValueList:list.New(),Capacity:capacity,}}func(this*LRUCache)getNode(keyint)*LRUCacheNode{elem,ok:this.LRUMap[key]if!ok{returnnil}// visit key, move to front of listthis.ValueList.MoveToFront(elem)elemNode:elem.Value.(*LRUCacheNode)returnelemNode}func(this*LRUCache)Get(keyint)int{node:this.getNode(key)ifnodenil{return-1}returnnode.Value}func(this*LRUCache)Put(keyint,valueint){node:this.getNode(key)ifnode!nil{node.Valuevaluereturn}// if full, delete the Least Recently Used nodeiflen(this.LRUMap)this.Capacity{backElem:this.ValueList.Back()this.ValueList.Remove(backElem)backNode:backElem.Value.(*LRUCacheNode)delete(this.LRUMap,backNode.Key)}newNode:LRUCacheNode{Key:key,Value:value,}newElem:this.ValueList.PushFront(newNode)this.LRUMap[key]newElemreturn}O(1)的平均时间复杂度get 操作要维护一个 map. 同时在淘汰元素的时候要按照时间维度因此额外需要维护一个类似先进先出的list 来充当时间维度把最近访问的放到前面后面就是最久未使用的。在实际应用中如果数据量不大的话还可以直接把数据和对应的时间戳绑定在一起通过按照时间戳排序来获取最近的和最老的元素。二、最不经常使用(LFU)LFU代码如下packagemainimport(container/listfmtsortstrings)typeLFUCachestruct{ValueMapmap[int]*list.Element FreMapmap[int]*list.List CapacityintMinFreint}typeLFUListNodestruct{KeyintValueintCurFreint}funcConstructor(capacityint)LFUCache{returnLFUCache{ValueMap:make(map[int]*list.Element),FreMap:make(map[int]*list.List),Capacity:capacity,MinFre:0,}}// get node from lfu cachefunc(this*LFUCache)getNode(keyint)*LFUListNode{elem,ok:this.ValueMap[key]if!ok{returnnil}lfuListNode,_:elem.Value.(*LFUListNode)curFre:lfuListNode.CurFre curList,ok:this.FreMap[curFre]if!ok{panic(not found)}curList.Remove(elem)newElem:this.addNodeToNextFre(lfuListNode)// node: must set the newElem because elem is not equal to newElemthis.ValueMap[key]newElem// update min Fre curList is empty after moveifcurList.Len()0curFrethis.MinFre{this.updateMinFre()}returnlfuListNode}func(this*LFUCache)updateMinFre(){this.MinFre}func(this*LFUCache)addNodeToNextFre(lfuListNode*LFUListNode)*list.Element{lfuListNode.CurFrenextFreList,ok:this.FreMap[lfuListNode.CurFre]if!ok{nextFreListlist.New()this.FreMap[lfuListNode.CurFre]nextFreList}// add to the front of next minFreMap listnextFreList.PushFront(lfuListNode)returnnextFreList.Front()}func(this*LFUCache)addNewElem(keyint,valueint){newLFUNode:LFUListNode{Key:key,Value:value,// new elem Fre is 1CurFre:1,}_,ok:this.FreMap[newLFUNode.CurFre]if!ok{this.FreMap[newLFUNode.CurFre]list.New()}this.FreMap[newLFUNode.CurFre].PushFront(newLFUNode)newElem:this.FreMap[newLFUNode.CurFre].Front()this.ValueMap[key]newElem}func(this*LFUCache)Get(keyint)int{lfuListNode:this.getNode(key)iflfuListNodenil{return-1}returnlfuListNode.Value}func(this*LFUCache)Put(keyint,valueint){lfuNode:this.getNode(key)iflfuNode!nil{lfuNode.Valuevaluereturn}// already full, delete one elemiflen(this.ValueMap)this.Capacity{minFreList,minFreOk:this.FreMap[this.MinFre]if!minFreOk{panic(not found)}exitElem:minFreList.Back()lfuNode:exitElem.Value.(*LFUListNode)minFreList.Remove(exitElem)delete(this.ValueMap,lfuNode.Key)}this.addNewElem(key,value)// min fre is 1, because we add a new elemthis.MinFre1return}与上面 lru 类似O(1)的复杂度get 操作用 map维护。 淘汰的逻辑要稍微复杂些因为要记住每个 key 对应的使用频率可以使用一个 map frequency对应的list因为同一个频率会有多个 key。 同时还要维护一个最小频率因为在删除的时候要优先从最小频率对应的那个 list 中删除最后一个元素。后记区分比对就是知识。 两种算法放在一起的看的话可以发现有意思的一点其实从某种程度上说 lru 可以看成是 lfu 的特例它不考虑频率因素所有的元素更新变动都在一个 list中。参考【1】LRU【2】LFU