缓存淘汰算法 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、这也是另一种思考了，不过这两者还是有很大区别的。