当前位置: 百姓购彩 > 公司简介 >

一次倒在 LRU 上的经历

时间:2022-04-15 08:46来源:百姓购彩 点击:

本文转载自微信公众号「bigsai」,作者大赛  。转载本文请联系bigsai公众号。

前言

大家好,我是bigsai,好久不见,甚是想念!

最近有个小伙伴跟我诉苦,说他没面到LRU,他说他很久前知道有被问过LRU的但是心想自己应该不会遇到,所以暂时就没准备。

奈何不巧,这还就真的考到了!他此刻的心情,可以用一张图来证明:

他说他最终踉踉跄跄的写了一个效率不是很高的LRU,面试官看着不是很满意要求写一个O(1)复杂度的LRU……后来果真GG了,后来发现这是力扣146的一道原题。

防止日后再碰到这个坑,今天和大家一起把这个坑踩了,这道题我自身刚开始也是用较为普通的方法,但是好的方法虽然不是很难但是想了真的很久才想到,虽然花了太多时间不太值,总算是自己想出来了,将这个过程给大家分享一下(只从算法的角度,不从操作系统的角度)。

理解LRU

设计一个LRU,你得知道什么是LRU吧?

LRU,英文全称为Least Recently Used,翻译过来就是最近最久未使用算法,是一种常用的页面置换算法。

说起页面置换算法,这就是跟OS关系比较大的了,我们都知道内存的速度比较快,但是内存的容量是非常有限的,不可能给所有页面装到内存中,所以就需要一个策略将常用的页面预放到内存中。

但是吧,谁也不知道进程下次会访问哪个内存,并不能很有效的知道(我们在当前并没有预测未来的功能),所以有些页面置换算法只是理想化但是没法真实实现的(没错就是最佳置换算法(Optimal)),然后常见必回的算法就是FIFO(先进先出)和LRU(最近最久未使用)。

LRU理解不难,就是维护一个有固定大小的容器,核心就是get()和put()两个操作。

我们先看一下LRU会有的两个操作:

初始化:LRUCache(int capacity) ,以正整数作为容量 capacity 初始化 LRU 缓存。

查询:get(int key),从自己的设计的数据结构中查找是否有当前key对应的value,如果有那么返回对应值并且要将key更新记录为最近使用,如果没有返回-1。

插入/更新:put(int key,int value),可能是插入一个key-value,也可能是更新一个key-value,如果容器中已经存才这个key-value那么只需要更新对应value值,并且标记成最新。如果容器不存在这个值,那么要考虑容器是否满了,如果满了要先删除最久未使用的那对key-value。

这里的流程可以给大家举个例子,例如

容量大小为2:

容量大小为2: [ "put",  "put", "get", "put","get", "put","get","get","get"] [ [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1],  [3], [4]] 

这个过程如下:

大家容易忽略的细节有:

put()存在更新的操作,例如put(3,3),put(3,4)会更新key为3的操作。 get()可能查询不到,但是查询到也会更新最久未使用的顺序。 如果容器未使用满,那么put可能更新可能插入,但是不会删除;如果容器满了并且put插入,就要考虑删除最久未使用的key-value了。

对于上面的这么一个规则,我们该如何处理呢?

如果单单用一个List类似的列表,可以顺序存储键值对,在List前面的(0下标为前)我们认为它是比较久的,在List后我们认为它是比较新的。我们考虑下各种操作可能会这样设计:

如果来get操作:

遍历List一个个比对,查看是否有该key的键值对,如果有直接返回对应key的value,如果没有那么返回-1.

如果来put操作:

遍历List,如果有该key的键值对,那么果断删除这个key-value,最后在末尾统一插入该键值对。

如果没有对应的key并且List容器已经到达最满了,那么果断删除第一个位置的key-value。

用List可能需要两个(一个存key一个存value),或者一个存Node节点(key,value为属性)的List,考虑下这个时间复杂度:

put操作:O(n),get操作:O(n) 两个操作都需要枚举列表线性复杂度,效率属实有点拉胯,肯定不行,这样的代码我就不写了。

哈希初优化

从上面的分析来看,我们已经可以很自信的将LRU写出来了,不过现在要考虑的是一个优化的事情。

如果说我们将程序中引入哈希表,那么肯定会有一些优化的。用哈希表存储key-value,查询是否存在的操作都能优化为O(1),但是删除或者插入或者更新位置的复杂度可能还是O(n),我们一起分析一下:

最久未使用一定是一个有序的序列来储存,要么是顺序表(数组)要么是链表,如果是数组实现的ArrayList存储最久未使用这个序列。

如果是ArrayList进行删除最久未使用(第一个)key-value,新的key被命中变成最新被使用(先删除然后插入末尾)操作都是O(n)。

同理如果是LinkedList的一些操作大部分也是O(n)的,像删除第一个元素这个是因为数据结构原因O(1)。

你发现自己的优化空间其实非常非常小,但是确实还是有进步的,只是被卡住不知道双O(1)的操作究竟怎么优化,这里面我把这个版本代码放出来,大家可以参考一下(如果面试问到实在不会可以这么写)

class LRUCache {      Map<Integer,Integer>map=new HashMap<>();     List<Integer>list=new ArrayList<>();     int maxSize;     public  LRUCache(int capacity) {         maxSize=capacity;     }      public int get(int key) {         if(!map.containsKey(key))//不存在返回-1             return -1;         int val=map.get(key);         put(key,val);//要更新位置 变成最新 很重要!         return val;     }      public void put(int key, int value) {         //如果key存在,直接更新即可         if (map.containsKey(key)) {             list.remove((Integer) key);             list.add(key);         } else {//如果不存在 要插入到最后,但是如果容量满了需要删除第一个(最久)             if (!map.containsKey(key)) {                 if (list.size() == maxSize) {                     map.remove(list.get(0));                     list.remove(0);                 }                 list.add(key);             }         }         map.put(key, value);     } } 
哈希+双链表

上面我们已经知道用哈希能够直接查到有木有这个元素,但是苦于删除!用List都很费力。

更详细的说,是苦于List的删除操作,Map的删除插入还是很高效的。

在上面这种情况,我们希望的就是能够快速删除List中任意一个元素,并且效率很高,如果借助哈希只能最多定位到,但是无法删除啊!该怎么办呢?

哈希+双链表啊!

我们将key-val的数据存到一个Node类中,然后每个Node知道左右节点,在插入链表的时候直接存入Map中,这样Map在查询的时候可以直接返回该节点,双链表知道左右节点可以直接将该节点在双链表中删除。

当然,为了效率,这里实现的双链表带头结点(头指针指向一个空节点防止删除等异常情况)和尾指针。

对于这个情况,你需要能够手写链表和双链表啦,双链表的增删改查已经写过清清楚楚,小伙伴们不要担心,这里我已经整理好啦:

单链表:https://mp.weixin.qq.com/s/Cq98GmXt61-2wFj4WWezSg

双链表:https://mp.weixin.qq.com/s/h6s7lXt5G3JdkBZTi01G3A

也就是你可以通过HashMap直接得到在双链表中对应的Node,然后根据前后节点关系删除,期间要考虑的一些null、尾指针删除等等特殊情况即可。

具体实现的代码为:

class LRUCache {     class Node {         int key;         int value;         Node pre;         Node next;          public Node() {         }          public Node( int key,int value) {             this.key = key;             this.value=value;         }     }     class DoubleList{         private Node head;// 头节点         private Node tail;// 尾节点         private int length;         public DoubleList() {             head = new Node(-1,-1);             tail = head;             length = 0;         }         void add(Node teamNode)// 默认尾节点插入         {             tail.next = teamNode;             teamNode.pre=tail;             tail = teamNode;             length++;         }         void deleteFirst(){             if(head.next==null)                 return;             if(head.next==tail)//如果删除的那个刚好是tail  注意啦 tail指针前面移动                 tail=head;             head.next=head.next.next;              if(head.next!=null)                 head.next.pre=head;             length--;         }         void deleteNode(Node team){              team.pre.next=team.next;             if(team.next!=null)                 team.next.pre=team.pre;             if(team==tail)                 tail=tail.pre;            team.pre=null;            team.next=null;             length--;         }         public String toString() {             Node team = head.next;             String vaString = "len:"+length+" ";             while (team != null) {                 vaString +="key:"+team.key+" val:"+ team.value + " ";                 team = team.next;             }             return vaString;         }     }     Map<Integer,Node> map=new HashMap<>();     DoubleList doubleList;//存储顺序     int maxSize;     LinkedList<Integer>list2=new LinkedList<>();      public   LRUCache(int capacity) {         doubleList=new DoubleList();         maxSize=capacity;     }     public  void print(){         System.out.print("maplen:"+map.keySet().size()+" ");         for(Integer in:map.keySet()){             System.out.print("key:"+in+" val:"+map.get(in).value+" ");         }         System.out.print("              ");         System.out.println("listLen:"+doubleList.length+" "+doubleList.toString()+" maxSize:"+maxSize);     }      public int get(int key) {         int val;         if(!map.containsKey(key))             return  -1;         val=map.get(key).value;         Node team=map.get(key);         doubleList.deleteNode(team);         doubleList.add(team);         return  val;     }      public void put(int key, int value) {         if(map.containsKey(key)){// 已经有这个key 不考虑长短直接删除然后更新            Node deleteNode=map.get(key);             doubleList.deleteNode(deleteNode);         }         else if(doubleList.length==maxSize){//不包含并且长度小于             Node first=doubleList.head.next;             map.remove(first.key);             doubleList.deleteFirst();         }        Node node=new Node(key,value);         doubleList.add(node);         map.put(key,node);      } } 

就这样,一个get和put都是O(1)复杂度的LRU写出来啦!

尾声

后来看了题解,才发现,Java中的LinkedHashMap也差不多是这种数据结构!几行解决,但是一般面试官可能不会认同,还是会希望大家能够手写一个双链表的。

class LRUCache extends LinkedHashMap<Integer, Integer>{     private int capacity;      public LRUCache(int capacity) {         super(capacity, 0.75F, true);         this.capacity = capacity;     }      public int get(int key) {         return super.getOrDefault(key, -1);     }      public void put(int key, int value) {         super.put(key, value);     }      @Override     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {         return size() > capacity;      } }//这个来源官方题解 给大家分享一下 

}//这个来源官方题解 给大家分享一下

哈希+双链表虽然在未看题解的情况想出来,但是真的花了挺久才想到这个点,以前见得确实比较少,高效手写LRU到今天算是真真正正的完全掌握啦!

不过除了LRU,其他的页面置换算法无论笔试还是面试也是非常高频啊,大家有空自己梳理一下哦。

 

除了算法水平真的很强的,不然大部分人其实不可能当场想到一些比较巧妙的方法,所以面对笔试最好的诀窍还是多刷力扣。

 

------分隔线----------------------------
栏目列表
推荐内容
百姓购彩平台,百姓购彩官网,百姓购彩网址,百姓购彩下载,百姓购彩app,百姓购彩开户,百姓购彩投注,百姓购彩购彩,百姓购彩注册,百姓购彩登录,百姓购彩邀请码,百姓购彩技巧,百姓购彩手机版,百姓购彩靠谱吗,百姓购彩走势图,百姓购彩开奖结果