LFU算法例子(LFU替换算法)

LRU与LFU

LFU的push遇到重复元素不删除key，只是get更新key之后对value进行覆盖。

mapint,pairint,listpairint,int::iteratorKeyFreq 用iterator指向FreqList的List中的一个节点。

在数据访问符合正态分布时，相比于LRU算法，LFU算法的缓存命中率会高一些。

(1)LFU的复杂度要比LRU更高一些。

(2)需要维护数据的访问频次，每次访问都需要更新。

(3)早期的数据相比于后期的数据更容易被缓存下来，导致后期的数据很难被缓存。

(4)新加入缓存的数据很容易被剔除，像是缓存的末端发生“抖动”。

[求助]LFU页面置换算法

least frequently used (LFU)，要求在页置换时置换引用计数最小的页。

3，2，1

0进入时，缺页。置换最近最小的1。内存：3，2，0

3，2

4进入时，缺页。置换最近最小的0。内存：3，2，4

3，2

1进入时，缺页。置换最近最小的4。内存：3，2，1

0进入时，缺页。置换最近最小的1。内存：3，2，0

4进入时，缺页。置换最近最小的0。内存：3，2，4

LFU缓存策略算法实现

LFU（Least Frequently Used），最近最少使用策略，也就是说在一段时间内，数据被使用频次最少的，优先被淘汰。

它是一种用于管理计算机内存的缓存算法，采用LFU算法的最简单方法是为每个加载到缓存的块分配一个计数器。每次引用该块时，计数器将增加一。当缓存达到容量并有一个新的内存块等待插入时，系统将搜索计数器最低的块并将其从缓存中删除。

我们可以在链表的开始插入元素，然后每插入一次计数一次，接着按照次数重新排序链表，如果次数相同的话，按照插入时间排序，然后从链表尾部选择淘汰的数据，这是一个最简单的LFU实现的思路。

这里实现了comparable接口，覆写了compare方法，这里 的主要作用就是在排序的时候需要用到，在compare方法里面我们首先比较节点的访问次数，在访问次数相同的情况下比较节点的访问时间，这里是为了 在排序方法里面通过比较key来选择淘汰的key。

这里采用linkedHashMap的主要原因是维护key的顺序。

添加元素的逻辑主要是先从缓存中根据key获取节点，如果获取不到，证明是新添加的元素，然后和容量比较，大于预定容量的话，需要找出count计数最小(计数相同的情况下，选择时间最久)的节点，然后移除掉那个。

我们知道内存淘汰算法，常见的除了LFU还有LRU,LRU和LFU侧重点不同，LRU主要体现在对元素的使用时间上，而LFU主要体现在对元素的使用频次上。

LFU的缺陷是：在短期的时间内，对某些缓存的访问频次很高，这些缓存会立刻晋升为热点数据，而保证不会淘汰，这样会驻留在系统内存里面。而实际上，这部分数据只是短暂的高频率访问，之后将会长期不访问，瞬时的高频访问将会造成这部分数据的引用频率加快，而一些新加入的缓存很容易被快速删除，因为它们的引用频率很低。

我们要根据业务场景选择合适的内存淘汰策略。

参考资料：