您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

LRU算法到底是怎么一回事?

时间:2020-07-07 10:41:52  来源:  作者:

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

简单描述一下在《操作系统》这本书里面对于LRU算法的解说。

假定系统为某进程分配了3个物理块,进程运行时的页面走向为 7 0 1 2 0 3 0 4,开始时3个物理块均为空,那么LRU 算法是如下工作的:

LRU算法到底是怎么一回事?

 

这就是最基本的LRU的磁盘调度逻辑,该算法运用领域比较广泛比如redis内存淘汰策略等等,该算法也是面试中面试官常常用来考验面试者代码能力和对LRU算法的正确理解。

以下我主要以为双向链表+HashMap的方式手撕一个时间复杂度为O(1)的LRU算法。

JAVA中,其实LinkedHashMap已经实现了LRU缓存淘汰算法,需要在构造方法第三个参数传入true( accessOrder = true;),表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private int capacity;

    LRULinkedHashMap(int capacity) {
        //true是表示按照访问时间排序,
        super(capacity, 0.75f, true);
        //传入指定的缓存最大容量
        this.capacity = capacity;
    }

    /**
     * 实现LRU的关键方法,如果map里面的元素个数大于了缓存最大容量,则删除链表的顶端元素
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

算法设计思路

  • 访问某个节点时,将其从原来的位置删除,并重新插入到链表头部。
  • 这样就能保证链表尾部存储的就是最近最久未使用的节点,当节点数量大于缓存最大空间时就淘汰链表尾部的节点。
  • 为了使删除操作时间复杂度为 O(1),就不能采用遍历的方式找到某个节点。
  • HashMap 存储着 Key 到节点的映射,通过 Key 就能以 O(1) 的时间得到节点,然后再以 O(1) 的时间将其从双向队列中删除。
LRU算法到底是怎么一回事?

 

一.构建双向链表Node节点

    /**
     * 定义双向链表其中K为Map中的K 降低查找时间复杂度
     */
    class Node {
        K k;
        V v;
        Node pre;
        Node next;

        Node(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }

二.定义变量

//定义缓存大小
private int size;
// 存储K和Node节点的映射 Node中会存放KV
private HashMap<K, Node> map;
private Node head;
private Node tail;

三.初始化结构体

XLRUCache(int size) {
    this.size = size;
    map = new HashMap<>();
}

四.添加元素

/**
 * 添加元素
 * 1.元素存在,将元素移动到队尾
 * 2.不存在,判断链表是否满。
 * 如果满,则删除队首(head)元素,新元素放入队尾元素
 * 如果不满,放入队尾(tail)元素
 */
public void put(K key, V value) {
    Node node = map.get(key);
    if (node != null) {
        //更新值
        node.v = value;
        moveNodeToTail(node);
    } else {
        Node newNode = new Node(key, value);
        //链表满,需要删除首节点
        if (map.size() == size) {
            Node delHead = removeHead();
            map.remove(delHead.k);
        }
        addLast(newNode);
        map.put(key, newNode);
    }
}
  • 移动元素到链表尾部
 public void moveNodeToTail(Node node) {
        if (tail == node) {
            return;
        }
      // 头节点直接置空
        if (head == node) {   // 备注一
            head = node.next;
            head.pre = null; 
        } else {              // 备注一
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
     // 备注三
        node.pre = tail; 
        node.next = null;
        tail.next = node;
        tail = node;
    }
  • 看备注一&备注三如下图
LRU算法到底是怎么一回事?

 

  • 看备注二&备注三如下图
LRU算法到底是怎么一回事?

 

  • 删除头节点
 public Node removeHead() {
       // 空链表
        if (head == null) {
            return null;
        }
        Node res = head;
       // 只有一个节点
        if (head == tail) {
            head = null;
            tail = null;
        } else {
        // 多个节点
            head = res.next;
            head.pre = null;
            res.next = null;
        }
        return res;
  }

map.remove(delHead.k): 删除Map中的Kv映射关系

  • 添加新节点
   public void addLast(Node newNode) {
       // 添加节点为空节点直接返回
        if (newNode == null) {
            return;
        }
       // 如果链表为空则直接添加
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            // 不为空则尾部添加
            tail.next = newNode;
            newNode.pre = tail;
            tail = newNode;
        }
    }

如果链表为空则将该元素设置成表头元素同时也是表尾元素。

五.获取元素

public V get(K key) {
    Node node = map.get(key);
    if (node != null) {
        moveNodeToTail(node);
        return node.v;
    }
    return null;
}

调度访问后的节点需要移动到链表尾部。

完整代码

import java.util.HashMap;

/**
 * @Auther: Xianglei
 * @Company:
 * @Date: 2020/6/27 14:52
 * @Version 1.0
 */
public class XLRUCache<K, V> {
    private int size;
    // 存储K和Node节点的映射 Node中会存放KV
    private HashMap<K, Node> map;
    private Node head;
    private Node tail;

    XLRUCache(int size) {
        this.size = size;
        map = new HashMap<>();
    }

    /**
     * 添加元素
     * 1.元素存在,将元素移动到队尾
     * 2.不存在,判断链表是否满。
     * 如果满,则删除队首元素,放入队尾元素,删除更新哈希表
     * 如果不满,放入队尾元素,更新哈希表
     */
    public void put(K key, V value) {
        Node node = map.get(key);
        if (node != null) {
            //更新值
            node.v = value;
            moveNodeToTail(node);
        } else {
            Node newNode = new Node(key, value);
            //链表满,需要删除首节点
            if (map.size() == size) {
                Node delHead = removeHead();
                map.remove(delHead.k);
            }
            addLast(newNode);
            map.put(key, newNode);
        }
    }

    public V get(K key) {
        Node node = map.get(key);
        if (node != null) {
            moveNodeToTail(node);
            return node.v;
        }
        return null;
    }

    public void addLast(Node newNode) {
        if (newNode == null) {
            return;
        }
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.pre = tail;
            tail = newNode;
        }
    }

    public void moveNodeToTail(Node node) {
        if (tail == node) {
            return;
        }
        if (head == node) {
            head = node.next;
            head.pre = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        node.pre = tail;
        node.next = null;
        tail.next = node;
        tail = node;
    }

    public Node removeHead() {
        if (head == null) {
            return null;
        }
        Node res = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = res.next;
            head.pre = null;
            res.next = null;
        }
        return res;
    }

    /**
     * 定义双向链表
     */
    class Node {
        K k;
        V v;
        Node pre;
        Node next;

        Node(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
}

测试

LRU算法到底是怎么一回事?

 

至此,你应该已经掌握 LRU 算i法的思想和实现过程了,这里面最重要的一点是理清楚双向链表和HasMap的映射关系以及节点移动操作。自此,你知道为什么用双向链表了吗?


更多精彩好文尽在: Java编程之道



Tags:LRU算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1 什么是LRULRU(Least recently used)最近最少使用,它的核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。因此 LRU 算法会根据数据的历史访问记录来进行排序,如...【详细内容】
2020-11-09  Tags: LRU算法  点击:(139)  评论:(0)  加入收藏
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。...【详细内容】
2020-07-07  Tags: LRU算法  点击:(66)  评论:(0)  加入收藏
LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。LRU算法的表现 新数据插...【详细内容】
2019-08-03  Tags: LRU算法  点击:(287)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条