LRU算法四种实现方式介绍

小恐龙 等级 708 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,如有侵权,请联系删除。

收藏
评论区

相关推荐

CSS块级元素与行内元素
**CSS块级元素与行内元素** **行内元素与块状元素** 1、块级元素:可以设置 width, height属性。 行内元素:设置width和height无效,其宽度随其元素的内容(文字或者图片等)的宽度而变化。 可以通过line-height设置行高(行高和height是不同的东西)。 2、块级元素:可以设置margin和padd
Java容器解析系列(17) LruCache详解
在之前讲[`LinkedHashMap`](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.cnblogs.com%2Fjamesvoid%2Fp%2F9919075.html)的时候,我们说起可以用来实现`LRU(least recent used)`算法,接下来我看一下其中的一个
HTML5中新增的布局标签
1.1.1   盒子模型层次 盒子模型的层次遵循以下顺序: 内容+padding à 边框 à background-image à background-color à margin![](https://oscimg.oschina.net/oscnet/722909c8dcfd273c73b0c6534e20f8d9bd4.gif) ![](ht
.clear 万能清除浮动
html body div.clear, html body span.clear { background: none; border: 0; clear: both; display: block; float: none;
QQ空间说说生成器
index.html <html> <head> <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no"> <style> body { margin: 0; padding:
MySQL特异功能之:Impossible WHERE noticed after reading const tables
<div class="htmledit\_views"> <div class="bct fc05 fc11 nbw-blog ztag" style="line-height:28px;font-size:16px;margin:15px 0px;padding:5px 0px;overflow:hidden;font-family:'Hiragino
ASMSupport4.6 生成位运算符
<p>在java中我们经常用到为运算符,我们假设有如下代码:</p> <div id="scid:9D7513F9-C04C-4721-824A-2B34F0212519:ecfdbd3b-8e28-40d7-9bd2-694f2e31c53a" class="wlWriterEditableSmartContent" style="float: none;
ASMSupport教程4.10 instanceof操作符生成
<p>instanceof是判断对象是否是某种类型的,我们可以看下下面的代码:</p> <div id="scid:9D7513F9-C04C-4721-824A-2B34F0212519:4f2d1c23-092c-4b0f-888f-8ada43241043" class="wlWriterEditableSmartContent" style="flo
ASMSupport教程4.2
<h2>4.2 生成Return操作</h2> <p>这一节我们将讲述如何生成return操作,我们将生成如下代码:</p> <div style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; display: inline; float: none; pa
AngularJS 学习笔记——路由配置(ngRoute)
<!DOCTYPE html> <html lang="en" ng-app="App"> <head> <meta charset="UTF-8"> <title>AngularJS 路由-参数,模块配置,布局模板</title> <style>
Arcgis api for javascript学习笔记
**Ⅰ. 在3.X版本中,设置Map对象的 "maxScale" 和 "minScale" 属性** -------------------------------------------------- <!DOCTYPE html> <html> <head> <style type="text/css">
Boost(1.69.0) windows入门(译)
<head> <title>缩进2字符</title> <style type="text/css"> .yindent, .yblock{ padding: 1em 1em 0 1em; margin-right:0; } .yindent{ margin:0.7em 2em; border:medium outset; } .yblock{ margin
Flutter之Padding
1 、Padding介绍 ------------ Padding用来为子元素添加填充,也就是指定子元素与容器边界的距离,作用基本上与Android中ViewGroup的padding属性差不多 const Padding({ Key key, @required this.padding, W
JS通过ajax + 多列布局 + 自动加载来实现瀑布流效果
Ajax ---- > * 说明:本文效果是无限加载的,意思就是你一直滚动就会一直加载图片出现,通过鼠标滚动距离来判断的,所以不是说的那种加载一次就停了的那种,那种demo下次我会再做一次 > css部分用的是html5+css3的新属性,图片会自动添加到每行的最顶端上去,而不是用js去判断。去除了一些js计算的麻烦。 **css部分:**