关于算法:高效设计一个LRU

6次阅读

共计 5608 个字符，预计需要花费 15 分钟才能阅读完成。

前言

大家好，我是 bigsai，好久不见，甚是惦记！

最近有个小伙伴跟我诉苦，说他没面到 LRU，他说他很久前晓得有被问过 LRU 的然而心想本人应该不会遇到，所以临时就没筹备。

奈何不巧，这还就真的考到了！他此刻的情绪，能够用一张图来证实：

他说他最终踉踉跄跄的写了一个效率不是很高的 LRU，面试官看着不是很称心……起初果然 GG 了。

避免日后再碰到这个坑，明天和大家一起把这个坑踩了，这道题我本身刚开始也是用较为一般的办法，然而好的办法尽管不是很难然而想了真的很久才想到，尽管花了太多工夫不太值，总算是本人想进去了，将这个过程给大家分享一下(只从算法的角度，不从操作系统的角度)。

了解 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：["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, 其余的页面置换算法无论口试还是面试也是十分高频啊，大家有空本人梳理一下哦。

首发公众号：bigsai 转载请搁置作者和原文 (本文) 链接 , 定期分享，欢送一起打卡力扣、学习交换！

正文完
算法
发表至： 算法
2021-12-09
 0
关于算法:复制带随机指针的链表
关于算法:阿里面试题如何寻找两个数组的中位数
关于算法:大实战算法与数据结构高手养成求职提升特训课
关于算法:PROG2003云计算开发

站内搜索

-「」