缓存淘汰算法 LFU

LFU

LFU全称是最不经常使用算法(Least Frequently Used),LFU算法的基本思想和所有的缓存算法一样,一定时间内被访问最少的页,在将来被访问到的几率也是最小的。

相比于LRU,LFU更加注重使用的频率 LRU其实可以看做频率为1的LFU

和LRU不同的是,LFU是根据频率排序的,当我们插入的时候,一般会把新插入的放到链表的尾部,因为新插入的一定是没出现过的,频率都会是1,所以会放在最后。

所以LFU的插入顺序如下:

  1. 如果A没有出现过,那么就会放在双向链表的最后,依次类推,就会是Z、Y...C、B、A的顺序放到频率为1的链表中。
  2. 当我们新插入A、B、C那么A、B、C就会到频率2的链表中
  3. 如果再次插入A、B那么A、B就会在频率为3中。C依旧在2中
  4. 如果此时已经插满,新插入一个的话,我们会把最后一个D移除,并插入6

代码

定义一个LFU的结构体

type LFU struct{
    len int
    cap int
    minFreq int
    itemMap map[string]*list.Element
    freqMap map[int]*list.List
}

我们使用LFU算法的话,我们插入元素就需要带上频率了

func initItem(k string,a any,f int) item {
    return item{
        key:k,
        value:v,
        freq:f,
    }
}

如果我们获取某个元素,那么这个元素如果存在,就会对这个元素频率进行加1

func(c *LFU) Get(key string)any{
    if e,ok:=c.itemMap[key];ok{
        c.increaseFreq(e)
        obj:=e.Value.(item)
        return obj.value
    }
    return nil
}

增加频率

func(c *LFU)increaseFreq(e *list.Element){
    obj:=e.Value.(item)
    oldLost:=c.freqMap[obj.freq]
    oldLost.Remove(e)
    if c.minFreq==obj.freq && oldLost.Len() == 0{
        c.minFreq++
    }
    c.insertMap(obj)
}

插入key到LFU缓存中

  1. 如果存在就对频率加1
  2. 如果不存在就准备插入
  3. 如果溢出了,就把最少频率的删除
  4. 如果没有溢出,那么就放到最后
func(c *LFU)Put(key string,value any){
    if e,ok:=c.itemMap[key];ok{
        obj:=e.Value.(item)
        obj.value = value
        c.increaseFreq(e)
    }else{
        obj:=initItem(key,value,1)
        if c.len == c.cap{
            c.eliminate()
            c.len--
        }
        c.insertMap(obj)
        c.minFreq = 1
        c.len++
    }
    }
}

插入一个新的

func(c *LFU)insertMap(obj item){
    l,ok:=c.freqMap[obj.freq]
    if !ok{
        l = list.New()
        c.freqMap[obj.freq]=1
    }
    e:=l.PushFront(obj)
    c.itemMap[obj.key] = e
}

找到频率最少的链表,并且删除

func(c *LFU) eliminate(){
    l:=c.freqMap[c.minFreq]
    e:=l.Back()
    obj:=e.Value.(item)
    l.Remove(e)
    delete(c.itemMap,obj.key)
}

以上就是说有lfu的算法实现了

总的来说、LRU更偏向时间、LFU更偏向频率。我个人觉得LRU也是频率为1的特殊LFU、这也是另一种思考了,不过这两者还是有很大区别的。

Last modification:May 28, 2024
如果觉得我的文章对你有用,请收藏本站