LRU算法四种实现方式介绍

小恐龙 等级 329 0 0

LRU全称是Least Recently Used,即最近最久未使用的意思。

LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

实现LRU

1. 用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。

2.利用一个链表来实现,每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据丢弃。

3. 利用链表和hashmap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

对于第一种方法, 需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。对于第二种方法,链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。

实现方案

使用LinkedHashMap实现

 LinkedHashMap底层就是用的HashMap加双链表实现的,而且本身已经实现了按照访问顺序的存储。此外,LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数,方法默认是直接返回false,不会移除元素,所以需要重写该方法。即当缓存满后就移除最不常用的数。
public class LRU<K,V> {

  private static final float hashLoadFactory = 0.75f;
  private LinkedHashMap<K,V> map;
  private int cacheSize;

  public LRU(int cacheSize) {
    this.cacheSize = cacheSize;
    int capacity = (int)Math.ceil(cacheSize / hashLoadFactory) + 1;
    map = new LinkedHashMap<K,V>(capacity, hashLoadFactory, true){
      private static final long serialVersionUID = 1;

      @Override
      protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > LRU.this.cacheSize;
      }
    };
  }

  public synchronized V get(K key) {
    return map.get(key);
  }

  public synchronized void put(K key, V value) {
    map.put(key, value);
  }

  public synchronized void clear() {
    map.clear();
  }

  public synchronized int usedSize() {
    return map.size();
  }

  public void print() {
    for (Map.Entry<K, V> entry : map.entrySet()) {
      System.out.print(entry.getValue() + "--");
    }
    System.out.println();
  }
}

当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

扩展

1.LRU-K

LRU-K中的K代表最近使用的次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。

LRU算法四种实现方式介绍

数据第一次被访问时,加入到历史访问列表,如果书籍在访问历史列表中没有达到K次访问,则按照一定的规则(FIFO,LRU)淘汰;当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列中删除,将数据移到缓存队列中,并缓存数据,缓存队列重新按照时间排序;缓存数据队列中被再次访问后,重新排序,需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即“淘汰倒数K次访问离现在最久的数据”。

LRU-K具有LRU的优点,同时还能避免LRU的缺点,实际应用中LRU-2是综合最优的选择。由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象,因此内存消耗会比LRU要多。

2.two queue

Two queues(以下使用2Q代替)算法类似于LRU-2,不同点在于2Q将LRU-2算法中的访问历史队列(注意这不是缓存数据的)改为一个FIFO缓存队列,即:2Q算法有两个缓存队列,一个是FIFO队列,一个是LRU队列。 当数据第一次访问时,2Q算法将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据。

LRU算法四种实现方式介绍

新访问的数据插入到FIFO队列中,如果数据在FIFO队列中一直没有被再次访问,则最终按照FIFO规则淘汰;如果数据在FIFO队列中再次被访问到,则将数据移到LRU队列头部,如果数据在LRU队列中再次被访问,则将数据移动LRU队列头部,LRU队列淘汰末尾的数据。

3.Multi Queue(MQ)

  MQ算法根据访问频率将数据划分为多个队列,不同的队列具有不同的访问优先级,其核心思想是:优先缓存访问次数多的数据。 详细的算法结构图如下,Q0,Q1....Qk代表不同的优先级队列,Q-history代表从缓存中淘汰数据,但记录了数据的索引和引用次数的队列:

LRU算法四种实现方式介绍

新插入的数据放入Q0,每个队列按照LRU进行管理,当数据的访问次数达到一定次数,需要提升优先级时,将数据从当前队列中删除,加入到高一级队列的头部;为了防止高优先级数据永远不会被淘汰,当数据在指定的时间里没有被访问时,需要降低优先级,将数据从当前队列删除,加入到低一级的队列头部;需要淘汰数据时,从最低一级队列开始按照LRU淘汰,每个队列淘汰数据时,将数据从缓存中删除,将数据索引加入Q-history头部。如果数据在Q-history中被重新访问,则重新计算其优先级,移到目标队列头部。 Q-history按照LRU淘汰数据的索引。

MQ需要维护多个队列,且需要维护每个数据的访问时间,复杂度比LRU高。

LRU算法对比

对比点

对比

命中率

LRU-2 > MQ(2) > 2Q > LRU

复杂度

LRU-2 > MQ(2) > 2Q > LRU

代价

LRU-2  > MQ(2) > 2Q > LRU

本文转自 https://blog.csdn.net/elricboa/article/details/78847305,如有侵权,请联系删除。

收藏
评论区

相关推荐

6 手写Java LinkedHashMap 核心源码
概述 LinkedHashMap是Java中常用的数据结构之一,安卓中的LruCache缓存,底层使用的就是LinkedHashMap,LRU(Least Recently Used)算法,即最近最少使用算法,核心思想就是当缓存满时,会优先淘汰那些近期最少使用的缓存对象 LruCache的缓存算法 LruCache采用的缓存算法为LRU(Least Re
python时间模块的使用 white_study
前言: 在开发中经常会与时间打交道,如:获取事件戳,时间戳的格式化等,这里简要记录一下python操作时间的方法。 python中常见的处理时间的模块: time:处理时间的模块,如获取时间戳,格式化日期等 datetime:date和time的结合体,处理日期和时间 calendar:日历相关的模块,如:处理年历/月历 tim
css深入研究
学习方法推荐 问题学习法:带着问题去学习,有利于集中注意力,目的明确,这既是有意学习的要求,也是发现学习的必要条件。心理学家把注意分为无意注意与有意注意两种。有意注意要求预先有自觉的目的,必要时需经过意志努力,主动地对一定的事物发生注意。它表明人的心理活动的主体性和积极性。问题学习法就是强调有意注意有关解决问题的信息,使学习有了明确的指向性,从而提高学习
js 时间处理
时间戳转formdate格式 13 || 16 位 javascript function timeStampToFormdate(timestamp) { if (timestamp) { return ' } var date timestamp.toString(
LRU算法四种实现方式介绍
LRU全称是Least Recently Used,即最近最久未使用的意思。 LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。
mysql 基础学习笔记
<section id"nice" datatool"mdnice编辑器" datawebsite"https://www.mdnice.com" style"fontsize: 16px; padding: 0 10px; wordspacing: 0px; wordbreak: breakword; wordwrap: break
[前端必知 ]HTTP or TCP/IP 基础
<section id"nice" datatool"mdnice编辑器" datawebsite"https://www.mdnice.com" style"fontsize: 16px; padding: 0 10px; wordspacing: 0px; wordbreak: breakword; wordwrap: break
多人协作必备技能Git
<section id"nice" datatool"mdnice编辑器" datawebsite"https://www.mdnice.com" style"fontsize: 16px; color: black; padding: 0 10px; lineheight: 1.6; wordspacing: 0px; lettersp
全栈进阶:Nginx基本功能及其原理
<div class"output_wrapper" id"output_wrapper_id" style"fontsize: 16px; color: rgb(62, 62, 62); lineheight: 1.6; wordspacing: 0px; letterspacing: 0px; fontfamily: 'Helvetica
2021前端技术面试必备Vue:(一)基础快速学习篇
由于疫情的影响,相信很多小伙伴都在家里待着。中小公司由于运营困难会出现裁员, 我们也面临着 '失业',你是否感到了焦虑.最近做了个调研: '现在的你找到工作了吗 ?<br/1.大部分的回复: 求职平台都是 ‘已回复’,然后没有下文,你遇到了吗?<br/2.各个公司对技术的要求增高<br/3.有人说开始搞副业<br/ 在我来看,这一年已经过去了四分
2021前端技术面试必备Vue:(二)组件篇
上一章已经更新了Vue基础,那么本章将更新Vue中最重要的概念组件,会介绍到组件的使用,组件传值,插槽的使用,插槽的分类。 当第一章基础掌握差不多了,然后再学习了组件的开发,那么你就可以开发简单的Vue项目,路由文章还没有更新,学习完Router后,就可以开发实战项目了。<section id"nice" datatool"mdnice编
2021前端技术面试必备Vue:(三)Router篇
<section id"nice" datatool"mdnice编辑器" datawebsite"https://www.mdnice.com" style"padding: 0 10px; wordspacing: 0px; wordwrap: breakword; textalign: left; fontfamily: Opti
2021前端技术面试必备Vue:(四)Vuex状态管理
前三章陆续已经更新了Vue基本使用 和Vue Router的基本使用,如果你读了前三篇文章的话,并且掌握差不多,那么你现在可以开发简单的应用了,例如Blog,电商网站........唯一不足的是,随着你的业务需求不断增加,页面中的状态数据也不断庞大,维护起来就特别困难了,Vue 提供了一种状态管理 解决办法 Vuex,它的思想和React 的R
Webpack 打包资源篇
<section datatools"新媒体排版" dataid"13439" datastyletype"9" style"visibility: visible;"<p style"maxwidth: 100%; visibility: visible;"<br mpafromtpl"t" style"visibility
低开销获取时间戳
前言在前面文章中提了一句关于时间戳获取性能的问题 获取操作系统时间,在Java中直接调用 System.currentTimeMillis(); 就可以,但在Cobar中如果这么获取时间,就会导致性能损耗非常严重(怎么解决?去Cobar的github仓库上看看代码吧)。这个话题展开具体说说,我们在Java中获取时间戳的方法是System.currentTim