LFU是一个著名的缓存算法,实现LFU中的set
和 get
样例:
capacity = 3
set(2,2) set(1,1) get(2) >> 2 get(1) >> 1 get(2) >> 2 set(3,3) set(4,4) get(3) >> -1 get(2) >> 2 get(1) >> 1 get(4) >> 4
我们来看看LFU的百度解释:
LFU(least frequently used (LFU) page-replacement algorithm)。即最不经常使用页置换算法,要求在页置换时置换引用计数最小的页,因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多,但以后就不再使用,这类页将会长时间留在内存中,因此可以将引用计数寄存器定时右移一位,形成指数衰减的平均使用次数。
也就是有一下几点:
1.cache由键值对组成《key,map》,由于hashmap里面key(相当于数组的下标)是唯一的。
2.所有的get操作,我们都是直接查看是否存在,如果不存在这个key,直接返回-1.如果存在这个key,那么更新访问的时间(访问时间来确定哪一个更久没有被访问了),同时访问次数增加。
3.我们用两个属性来保存每一个键值对的状态,一个是调用的次数,一个是最近调用的时间。
4.在set的时候,如果存在这个key,使用次数直接加一次,更新使用的时间,更新成最新的value;否则,创建一个新的键值对,赋予value,调用时间,在这里顺便判断是否容量为0,为0则不进行任何操作。如果容量还没有使用完,则直接插入,如果已经满了,那么我们要移除一个最不常使用而且最久没有使用的,再进行插入。
5.移除的原则:找到使用次数最少的,如果有相同使用次数的,那么直接删除掉使用次数最少的里面最久没有使用的那个。
6.使用的时间属性:set的时候更新,get的时候也要更新。
7.调用次数更新:get和set的时候,只要存在就会加一次。
代码如下:
public class LFUCache { private Mapcache = null; private int capacity = 0; private int used = 0; public LFUCache(int capacity) { //评论区指正:hashmap初始化要用2*capacity,否则当数组量很大时,当使用量超过0.75*capacity,hashmap会resize // 影响性能,最后导致lintcode报超时,谢谢 cache = new HashMap(capacity*2, 0.75f); this.capacity = capacity; } public int get(int key) { Node node = cache.get(String.valueOf(key)); if (node == null) { return -1; } node.useCount++; node.lastGetTime = System.nanoTime(); return node.value; } public void set(int key, int value) { Node n = cache.get(String.valueOf(key)); if (n != null) { n.useCount ++; n.lastGetTime = System.nanoTime(); n.value = value; return; }else{ Node node = new Node(); node.value = value; node.useCount = 0; node.lastGetTime = System.nanoTime(); if(this.capacity == 0)return; if (used < this.capacity) { used ++; cache.put(String.valueOf(key), node); } else { removeLast(); cache.put(String.valueOf(key), node); } } } // 淘汰最少使用的缓存 private void removeLast() { int minCount = Integer.MAX_VALUE; long getTime = System.nanoTime(); String t = null; Iteratorit = cache.keySet().iterator(); while(it.hasNext()){ String key = it.next(); Node node = cache.get(key); if(node.useCount < minCount || (node.useCount == minCount && node.lastGetTime < getTime)){ t = key; minCount = node.useCount; getTime = node.lastGetTime; } } cache.remove(t); } public class Node { public int value; public int useCount; public long lastGetTime; } }
如果有所帮助,脸皮厚求个赞~
此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~
技术之路不在一时,山高水长,纵使缓慢,驰而不息。
公众号:秦怀杂货店