因為LRU設計效率太低被pass了

語言: CN / TW / HK

前言

首發公眾號:bigsai 轉載請放置作者和原文(本文)鏈接

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

最近有個小夥伴跟我訴苦,説他沒面到LRU,他説他很久前知道有被問過LRU的但是心想自己應該不會遇到,所以暫時就沒準備。

奈何不巧,這還就真的考到了!他此刻的心情,可以用一張圖來證明:

image-20211130123133587

他説他最終踉踉蹌蹌的寫了一個效率不是很高的LRU,面試官看着不是很滿意……後來果真GG了。

防止日後再碰到這個坑,今天和大家一起把這個坑踩了,這道題我自身剛開始也是用較為普通的方法,但是好的方法雖然不是很難但是想了真的很久才想到,雖然花了太多時間不太值,總算是自己想出來了,將這個過程給大家分享一下(只從算法的角度,不從操作系統的角度)。

image-20211130123511746

理解LRU

設計一個LRU,你得知道什麼是LRU吧?

LRU,英文全稱為Least Recently Used,翻譯過來就是最近最久未使用算法,是一種常用的頁面置換算法

説起頁面置換算法,這就是跟OS關係比較大的了,我們都知道內存的速度比較快,但是內存的容量是非常有限的,不可能給所有頁面裝到內存中,所以就需要一個策略將常用的頁面預放到內存中。

但是吧,誰也不知道進程下次會訪問哪個內存,並不能很有效的知道(我們在當前並沒有預測未來的功能),所以有些頁面置換算法只是理想化但是沒法真實實現的(沒錯就是最佳置換算法(Optimal)),然後常見必回的算法就是FIFO(先進先出)和LRU(最近最久未使用)。

LRU理解不難,就是維護一個有固定大小的容器,核心就是get()和put()兩個操作。

721C7F42599E9496187614A66595A973

我們先看一下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]]

這個過程如下:

image-20211206001714674

大家容易忽略的細節有:

  • 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) 兩個操作都需要枚舉列表線性複雜度,效率屬實有點拉胯,肯定不行,這樣的代碼我就不寫了。

image-20211206003958399

哈希初優化

從上面的分析來看,我們已經可以很自信的將LRU寫出來了,不過現在要考慮的是一個優化的事情。

如果説我們將程序中引入哈希表,那麼肯定會有一些優化的。用哈希表存儲key-value,查詢是否存在的操作都能優化為O(1),但是刪除或者插入或者更新位置的複雜度可能還是O(n),我們一起分析一下:

最久未使用一定是一個有序的序列來儲存,要麼是順序表(數組)要麼是鏈表,如果是數組實現的ArrayList存儲最久未使用這個序列。

如果是ArrayList進行刪除最久未使用(第一個)key-value,新的key被命中變成最新被使用(先刪除然後插入末尾)操作都是O(n)。

同理如果是LinkedList的一些操作大部分也是O(n)的,像刪除第一個元素這個是因為數據結構原因O(1)。

你發現自己的優化空間其實非常非常小,但是確實還是有進步的,只是被卡住不知道雙O(1)的操作究竟怎麼優化,這裏面我把這個版本代碼放出來,大家可以參考一下(如果面試問到實在不會可以這麼寫)

```java 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的刪除插入還是很高效的。

image-20211206165457619

在上面這種情況,我們希望的就是能夠快速刪除List中任意一個元素,並且效率很高,如果藉助哈希只能最多定位到,但是無法刪除啊!該怎麼辦呢?

哈希+雙鏈表啊!

我們將key-val的數據存到一個Node類中,然後每個Node知道左右節點,在插入鏈表的時候直接存入Map中,這樣Map在查詢的時候可以直接返回該節點,雙鏈表知道左右節點可以直接將該節點在雙鏈表中刪除。

當然,為了效率,這裏實現的雙鏈錶帶頭結點(頭指針指向一個空節點防止刪除等異常情況)和尾指針。

image-20211206174203634

對於這個情況,你需要能夠手寫鏈表和雙鏈表啦,雙鏈表的增刪改查已經寫過清清楚楚,小夥伴們不要擔心,這裏我已經整理好啦:

單鏈表:https://mp.weixin.qq.com/s/Cq98GmXt61-2wFj4WWezSg

雙鏈表:https://mp.weixin.qq.com/s/h6s7lXt5G3JdkBZTi01G3A

也就是你可以通過HashMap直接得到在雙鏈表中對應的Node,然後根據前後節點關係刪除,期間要考慮的一些null、尾指針刪除等等特殊情況即可。

具體實現的代碼為:

```java 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也差不多是這種數據結構!幾行解決,但是一般面試官可能不會認同,還是會希望大家能夠手寫一個雙鏈表的。

```java class LRUCache extends LinkedHashMap{ 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 ,定期分享,歡迎一起打卡力扣、學習交流!