页面置换算法-LFU
LFU(Least Frequently Used),表示最近使用次数最少来进行淘汰,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。其相关也有好几种不同的LFU算法,主要有 LFU*、LFU- Aging、LFU*-Aging、 Window-LFU等。
LFU中的每条数据都需要记录一个访问次数,所有的数据按照访问次数排序,当缓存存满时在插入数据满,删除数据则删除访问次数最少的那一条。
其主要思路:
① 新加入数据加入队尾,引用计数记为1
②队列中的数据被访问后,引用计数加1,重新排序
③当需要淘汰数据时,淘汰队列最末端数据
一般情况下,LFU效率要优于LRU,且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录,一旦数据访问模式改变,LFU需要更长时间来适用新的访问模式,即:LFU存在历史数据影响将来数据的“缓存污染”效用。
复杂度
需要维护一个队列记录所有数据的访问记录,每个数据都需要维护引用计数。
代价
需要记录所有数据的访问记录,内存消耗较高;需要基于引用计数排序,性能消耗较高。
其实现如下:
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
class LFU {
private Map<Integer, Node> values;
private Map<Integer, Set<Integer>> freqs;
private int minFreq = 1;
private int cap;
private int count = 0;
public LFU(int capacity) {
values = new HashMap<>();
freqs = new HashMap<>();
cap = capacity;
freqs.put(1, new LinkedHashSet<>());
}
public int get(int key) {
if (!values.containsKey(key)) {
return -1;
}
Node n = values.get(key);
freqs.get(n.freq).remove(key);
n.freq++;
if (!freqs.containsKey(n.freq)) {
freqs.put(n.freq, new LinkedHashSet<>());
}
freqs.get(n.freq).add(key);
if (n.freq - 1 == minFreq && freqs.get(n.freq - 1).size() == 0) {
minFreq = n.freq;
}
return n.val;
}
public void put(int key, int value) {
if (cap == 0) {
return;
}
if (values.containsKey(key)) {
values.get(key).val = value;
get(key);
return;
}
if (count == cap) {
count--;
int minKey = freqs.get(minFreq).iterator().next();
freqs.get(minFreq).remove(minKey);
values.remove(minKey);
}
Node n = new Node(key, value);
values.put(key, n);
minFreq = 1;
freqs.get(1).add(key);
count++;
}
private static class Node {
int key, val, freq;
Node (int k, int v) {
key = k;
val = v;
freq = 1;
}
}
}
还有一种实现方式不建议使用,其本事是使用时间以及引用次数按照LFU规则进行排序,先按照次数排序,在按照时间排序,如果次数相同,则根据时间进行排序,但有时,由于程序运行速度过快,导致两个数据块在时间上保持一致,因此就不能排列出两者谁先谁后,代码如下,大家可以参考下:
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class LFUCache {
private Integer capacity;
private Map<Integer,Integer> map;
private Map<Integer,HitRate> countMap;
public LFUCache(int capacity) {
map=new HashMap(capacity);
countMap=new HashMap<>(capacity);
this.capacity=capacity;
}
public int get(int key) {
Integer temp=map.get(key);
System.out.println("key is "+key+" :" + temp);
if(temp == null) return -1;
HitRate hitRate=countMap.get(key);
System.out.println("countMap key is "+hitRate);
hitRate.count+=1;
System.out.println(hitRate.lasttime+"aa");
hitRate.lasttime=System.currentTimeMillis()+1;
System.out.println(hitRate.lasttime);
countMap.put(key,hitRate);
return temp;
}
public void put(int key, int value) {
if(capacity==0)return;
Integer values=map.get(key);
HitRate hitRate=null;
if(values==null){
if(map.size()==capacity){
removeElement();
}
hitRate=new HitRate(key,1,System.currentTimeMillis());
}else {
hitRate=countMap.get(key);
hitRate.count+=1;
hitRate.lasttime=System.currentTimeMillis();
}
map.put(key,value);
countMap.put(key,hitRate);
}
public void removeElement(){
HitRate hitRate=Collections.min(countMap.values());
countMap.remove(hitRate.key);
map.remove(hitRate.key);
}
class HitRate implements Comparable<HitRate>{
private int key;
private int count;
private long lasttime;
public HitRate(int key,int count,long lasttime){
this.key=key;
this.count=count;
this.lasttime=lasttime;
}
public int compareTo(HitRate hitRate) {
int temp = this.count - hitRate.count;
return temp != 0 ? temp : Long.compare(this.lasttime, hitRate.lasttime);
}
}
public static void main(String[] args) throws InterruptedException {
/**
* ["LFUCache","put","put","get","get","put","get","get","get"]
* [[2],[2,1],[3,2],[3],[2],[4,3],[2],[3],[4]]
*/
LFUCache lfuCache=new LFUCache(2);
lfuCache.put(2,1);
Thread.sleep(1000);
lfuCache.put(3,2);
Thread.sleep(1000);
System.out.println( lfuCache.get(3));
Thread.sleep(1000);
System.out.println(lfuCache.get(2));
lfuCache.put(4,3);
Thread.sleep(1000);
System.out.println(lfuCache.get(2));
Thread.sleep(1000);
System.out.println(lfuCache.get(3));
Thread.sleep(1000);
System.out.println(lfuCache.get(4));
}
}
关于其他几种算法简单提一下,笔者反正也没有用到过:
1.LFU*:LFU*数据缓存实现和LFU一样,不同的地方在于淘汰数据时,LFU*只淘汰引用计数为1的数据,且如果所有引用计数 为1的数据大小之和都没有新加入的数据那么大,则不淘汰数据,新的数据也不缓存。其复杂度也相对较低,只需要维 护引用计数是一的数据块。和LFU类似,但由于其不淘汰引用计数大于1的数据,则一旦访问模式改变,LFU*无法缓 存新的数据,因此这个算法的应用场景比较有限。
2.LFU-Aging:其核心思想是“除了访问次数外,还要考虑访问时间”,他是通过平均引用计数来考虑了时间问题,而不是直接去记 录时间,这样做的主要原因是解决LFU缓存污染的问题。LFU-Aging在LFU的基础上,增加了一个最大平均引用计数。 当当前缓存中的数据“引用计数平均值”达到或者超过“最大平均引用计数”时,则将所有数据的引用计数都减少。减少的 方法有多种,可以直接减为原来的一半,也可以减去固定的值等。LFU-Aging的效率和LFU类似,当访问模式改变时, LFU-Aging能够更快的适用新的数据访问模式,效率要高。但是相对LFU引入了平均引用计数提升了复杂度。其代价和 LFU类似,当平均引用次数超过指定阈值(Aging)后,需要遍历访问列表。
3.LFU*-Aging:LFU-Aging与LFU*合成体,其优点就是不需要基于引用计数去排序
4.Window-LFU:Windows-LFU是LFU的一个改进版,差别在于Window-LFU并不记录所有数据的访问历史,而只是记录过去一 段时间内的访问历史,这就是Window的由来,基于这个原因,传统的LFU又被称为“Perfect-LFU”。与LFU的实现基本 相同,差别在于不需要记录所有数据的历史访问数据,而只记录过去一段时间内的访问历史。
1)记录了过去W个访问记录;
2)需要淘汰时,将W个访问记录按照LFU规则排序淘汰
Window-LFU的命中率和LFU类似,但Window-LFU会根据数据的访问模式而变化,能够更快的适应新的数据访问模 式,”缓存污染“问题不严重。其需要一个维护队列,记录数据的访问流历史,需要排序。Window-LFU只记录一部分的访 问历史记录,不需要记录所有的数据访问历史,因此内存消耗和排序消耗都比LFU要低。
对比
对比点 |
对比 |
命中率 |
Window-LFU/LFU-Aging > LFU*-Aging > LFU > LFU* |
复杂度 |
LFU-Aging > LFU> LFU*-Aging >Window-LFU > LFU* |
代价 |
LFU-Aging > LFU > Window-LFU > LFU*-Aging > LFU* |
上一篇: LRU-最少使用页面置换算法
下一篇: LRU缓存机制算法实现