LFU的基本原理与完成
2019-11-18杂谈搜奇网23°c
A+ A-媒介:之前有写过一篇关于LRU的文章链接https://www.cnblogs.com/wyq178/p/9976815.html LRU全称:Least Recently Used:近来起码运用战略,推断近来被运用的时刻,间隔如今最远的数据优先被镌汰,作为一种依据接见时刻来变动链表递次从而完成缓存镌汰的算法,它是redis采纳的镌汰算法之一。redis另有一个缓存战略叫做LFU, 那末LFU是什么呢？我们本期博客来分下一下LFU：
本篇博客的目次：
一: LRU是什么
二：LRU的完成
三：测试
四：LRU和LFU的辨别以及瑕玷
五：总结
正文
一：LRU是什么
LFU,全称是:Least Frequently Used，最不常常运用战略,在一段时刻内,数据被运用频次起码的,优先被镌汰。起码运用（LFU）是一种用于治理计算机内存的缓存算法。主假如纪录和追踪内存块的运用次数,当缓存已满而且须要更多空间时，体系将以最低内存块运用频次消灭内存.采纳LFU算法的最简朴要领是为每一个加载到缓存的块分派一个计数器。每次援用该块时，计数器将增添一。当缓存到达容量并有一个新的内存块守候插进去时，体系将搜刮计数器最低的块并将其从缓存中删除(本段摘自维基百科)
诠释:上面这个图就是一个LRU的简朴完成思绪,在链表的最先插进去元素，然后每插进去一次计数一次,接着根据次数从新排序链表，假如次数雷同的话，根据插进去时刻排序，然后从链表尾部挑选镌汰的数据~
二：LRU完成
2.1 定义Node节点
Node重要包含了key和value,由于LFU的重要完成头脑是比较接见的次数,假如在次数雷同的情况下须要比较节点的时刻,越早放入的越快 被镌汰,因而我们须要在Node节点上到场time和count的属性,离别用来纪录节点的接见的时刻和接见次数。其他的版本完成体式格局里有新加个内部类来纪录 key的count和time,然则我以为不够轻易,还得零丁保护一个map,本钱有点大。另有一点注重的是这里完成了comparable接口，覆写了compare要领，这里 的重要作用就是在排序的时刻须要用到，在compare要领内里我们起首比较节点的接见次数，在接见次数雷同的情况下比较节点的接见时刻,这里是为了 在排序要领内里经由历程比较key来挑选镌汰的key
/** * 节点 */ public static class Node implements Comparable<Node>{ //键 Object key; //值 Object value; /** * 接见时刻 */ long time; /** * 接见次数 */ int count; public Node(Object key, Object value, long time, int count) { this.key = key; this.value = value; this.time = time; this.count = count; } public Object getKey() { return key; } public void setKey(Object key) { this.key = key; } public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } public long getTime() { return time; } public void setTime(long time) { this.time = time; } public int getCount() { return count; } public void setCount(int count) { this.count = count; } @Override public int compareTo(Node o) { int compare = Integer.compare(this.count, o.count); //在数量雷同的情况下 比较时刻 if (compare==0){ return Long.compare(this.time,o.time); } return compare; } }
2.2:定义LFU类
定义LFU类,这里采纳了泛型,声清楚明了K和V,另有总容量和一个Map(caches)用来保护一切的节点。在组织要领里将size通报进去,而且建立了一个LinkedHashMap，采纳linkedHashMap的重要原因是保护key的递次
public class LFU<K,V> { /** * 总容量 */ private int capacity; /** * 一切的node节点 */ private Map<K, Node> caches; /** * 组织要领 * @param size */ public LFU(int size) { this.capacity = size; caches = new LinkedHashMap<K,Node>(size); } }
2.3: 增加元素
增加元素的逻辑主假如先从缓存中依据key猎取节点，假如猎取不到，证实是新增加的元素，然后和容量比较，大于预定容量的话，须要找出count计数最小(计数雷同的情况下,挑选时刻最久)的节点，然后移撤除谁人。假如在预定的大小以内，就新建立节点，注重这里不能运用 System.currentTimeMillis()要领，由于毫秒级别的粒度没法对插进去的时刻举行辨别,在运转比较快的情况下，只要System.nanoTime()才能够将key的插进去时刻辨别，默许设置count计数为1.假如能猎取到，示意是旧的元素，那末就用新值掩盖旧值，计数+1,设置key的time为当前纳秒时刻。末了还须要举行排序，这里能够看出插进去元素的逻辑主假如增加进入缓存,更新元素的时刻和计数~
/** * 增加元素 * @param key * @param value */ public void put(K key, V value) { Node node = caches.get(key); //假如新元素 if (node == null) { //假如凌驾元素包容量 if (caches.size() >= capacity) { //移除count计数最小的谁人key K leastKey = removeLeastCount(); caches.remove(leastKey); } //建立新节点 node = new Node(key,value,System.nanoTime(),1); caches.put(key, node); }else { //已存在的元素掩盖旧值 node.value = value; node.setCount(node.getCount()+1); node.setTime(System.nanoTime()); } sort(); }
每次put或许get元素都须要举行排序，排序的重要意义在于根据key的cout和time举行一个key递次的重组，这里的逻辑是起首将缓存map建立成一个list,然后根据Node的value举行，重组全部map。然后将本来的缓存清空，遍历这个map， 把key和value的值放进去本来的缓存中的递次就举行了重组~这里辨别于LRU的差别点在于运用了java的鸠合API，LRU的排序是举行节点挪动。而在LFU中完成比较复杂,由于put的时刻不光得比较基数另有时刻。假如不借助java的API的话，能够新保护一个节点频次链表,每次将key保留在这个节点频次链表中挪动指针，从而也间接能够完成排序~
/** * 排序 */ private void sort() { List<Map.Entry<K, Node>> list = new ArrayList<>(caches.entrySet()); Collections.sort(list, new Comparator<Map.Entry<K, Node>>() { @Override public int compare(Map.Entry<K, Node> o1, Map.Entry<K, Node> o2) { return o2.getValue().compareTo(o1.getValue()); } }); caches.clear(); for (Map.Entry<K, Node> kNodeEntry : list) { caches.put(kNodeEntry.getKey(),kNodeEntry.getValue()); } }
移除最小的元素
镌汰最小的元素这里调用了Collections.min要领，然后经由历程比较key的compare要领，找到计数最小和时刻最长的元素，直接从缓存中移除~
/** * 移除统计数或许时刻比较最小的谁人 * @return */ private K removeLeastCount() { Collection<Node> values = caches.values(); Node min = Collections.min(values); return (K)min.getKey(); }
2.4:猎取元素
猎取元素起首是从缓存map中猎取，不然返回null，在猎取到元素今后须要举行节点的更新，计数+1和革新节点的时刻，依据LFU的准绳，在当前时刻猎取到这个节点今后，这个节点就临时变成了热门节点，然则它的cout计数也有多是小于某个节点的count的，所以
此时不能将它直接挪动到链表顶，还须要举行一次排序，重组它的位置~
/** * 猎取元素 * @param key * @return */ public V get(K key){ Node node = caches.get(key); if (node!=null){ node.setCount(node.getCount()+1); node.setTime(System.nanoTime()); sort(); return (V)node.value; } return null; }
三：测试
起首声明一个LRU，然后默许的最大的大小为5，顺次put进入A、B、C、D、E、F6个元素,此时将会找到计数最小和时刻最短的元素,那末将会镌汰A(由于count值都是1)。记住get两次B元素，那末B元素的count=3,时刻更新为最新。此时B将会挪动到顶，接着在getC元素,C元素的count=2，时刻会最新，那末此时由于它的count值依旧小于B,所以它依旧在B背面，再getF元素，F元素的count=2,又由于它的时刻会最新，所以在与C雷同的计数下，F元素更新(时刻间隔如今近来)，所以链表将会挪动，F会在C的前面，再次put一次C,此时C的count=3,同时时刻为最新,那末现在C的count和B保持一致，则他们比较时刻，C显著更新，所以C将会排在B的前面，终究的递次应该是:C->B->F->E->D
public static void main(String[] args) { LFU<Integer, String> lruCache = new LFU<>(5); lruCache.put(1, "A"); lruCache.put(2, "B"); lruCache.put(3, "C"); lruCache.put(4, "D"); lruCache.put(5, "E"); lruCache.put(6, "F"); lruCache.get(2); lruCache.get(2); lruCache.get(3); lruCache.get(6);
//从新put节点3
lruCache.put(3,"C");
final Map<Integer, Node> caches = (Map<Integer, Node>) lruCache.caches; for (Map.Entry<Integer, Node> nodeEntry : caches.entrySet()) { System.out.println(nodeEntry.getValue().value); } }
运转效果：
四：LRU和LFU的辨别以及LFU的瑕玷
LRU和LFU侧重点差别，LRU重要体如今对元素的运用时刻上,而LFU重要体如今对元素的运用频次上。LFU的瑕玷是：在短时间的时刻内，对某些缓存的接见频次很高，这些缓存会马上晋升为热门数据，而保证不会镌汰，如许会驻留在体系内存内里。而现实上，这部份数据只是短暂的高频次接见，今后将会历久不接见,瞬时的高频接见将会形成这部份数据的援用频次加速，而一些新到场的缓存很轻易被疾速删除，由于它们的援用频次很低。
五：总结
本篇博客针对LFU做了一个简朴的引见，并细致引见了怎样用java来完成LFU，而且和LRU做了一个简朴的比较。针对一种缓存战略。LFU有本身的奇特运用场景，怎样完成LFU和应用LFU的特征来完成开辟历程部份功用是我们须要思索的。现实在运用中LRU的运用频次要高于LFU,不过相识这类算法也算是程序员的必备妙技。
末了: 假如对进修java有兴致能够到场群:618626589,本群旨在打造无培训广告、无闲谈扯皮、无注水斗图的纯技术交流群，群里天天会分享有代价的题目和进修材料,迎接列位随时到场～
