hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

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,本群旨在打造无培训广告、无闲谈扯皮、无注水斗图的纯技术交流群,群里天天会分享有代价的题目和进修材料,迎接列位随时到场~     

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
LFU的基本原理与完成

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282284.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>