type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Mar 24, 2024 01:53 AM
Parent item
领域
LFU 是 Least Frequently Used 的缩写，即最不经常最少使用，按照使用频率排序。也是一种常用的页面置换算法，选择访问计数器最小的页面予以淘汰。
缓存中每个页面带一个访问计数器。
根据 LFU 的策略，每访问一次都要更新访问计数器。当插入 B 的时候，发现缓存中有 B，所以增加访问计数器的计数，并把 B 移动到访问计数器从大到小排序的地方。再插入 D，同理先更新计数器，再移动到它排序以后的位置。当插入 F 的时候，缓存中不存在 F，所以淘汰计数器最小的页面的页面，所以淘汰 A 页面。此时 F 排在最下面，计数为 1。
这里有一个比 LRU 特别的地方。如果淘汰的页面访问次数有多个相同的访问次数，选择最靠尾部的。
LFU 更新和插入新页面可以发生在链表中任意位置，删除页面都发生在表尾。
LFU的性能要求和数据结构
LFU 和LRU一样，额外地，需要记录访问次数，所以每个结点除了存储 key，value，需要再多存储 frequency 访问次数。
同时需要对频次进行判断。根据LFU 的工作原理，会发现它只关心最小频次。其他频次之间的顺序并不关心，所以不需要排序。
用一个 min 变量保存最小频次，淘汰时读取这个最小值能找到要删除的结点。
相同频次按照先后顺序排列，这个需求还是用双向链表实现，双向链表插入的顺序体现了结点的先后顺序。相同频次对应一个双向链表，可能有多个相同频次，所以可能有多个双向链表。
用一个 map 维护访问频次和双向链表的对应关系。删除最小频次时，通过 min 找到最小频次，然后再这个 map 中找到这个频次对应的双向链表，在双向链表中找到最旧的那个结点删除。这就解决了 LFU 删除操作。
LFU 的更新操作和 LRU 类似，也需要用一个 map 保存 key 和双向链表结点的映射关系。这个双向链表结点中存储的是 key-value-frequency 三个元素的元组。这样通过结点中的 key 和 frequency 可以反过来删除 map 中的 key。
查询数据
注意代码中的min++， 是因为当前被查询的节点是唯一的频次最小节点，那么本次被查询后， 最小的频次会加1。
插入数据
3种情况：
- 已存在：更新已存在的数据
- 不存在：缓存满了， 需要删除最小频次的最老节点
- 不存在：缓存没有满， 直接插入
优化
利用 Priority Queue 维护一个最小堆，堆顶是访问次数最小的元素。map 中的 value 存储的是优先队列中结点。
堆节点定义如下：
count 值用来决定哪个是最老的元素，类似一个操作时间戳。index 值用来 re-heapify 调整堆的。
在 Less() 方法中，frequency 从小到大排序，frequency 相同的，按 count 从小到大排序。按照优先队列建堆规则，可以得到，frequency 最小的在堆顶，相同的 frequency，count 最小的越靠近堆顶。
在 Swap() 方法中，记得要更新 index 值。在 Push() 方法中，插入时队列的长度即是该元素的 index 值，此处也要记得更新 index 值。update() 方法调用 Fix() 函数。Fix() 函数比先 Remove() 再 Push() 一个新的值，花销要小。所以此处调用 Fix() 函数，这个操作的时间复杂度是 O(log n)。