LRU緩存淘汰算法分析與實作

概述

記錄一下LRU緩存淘汰算法的實作。

原理

LRU（Least recently used，最近最少使用）緩存算法根據資料最近被通路的情況來進行淘汰資料，其核心思想是“如果資料最近被通路過，那麼将來被通路的幾率也更高”。

介紹

下圖中，介紹了一個緩存空間為5的緩存隊列，當通路資料的順序是:1,2,3,4,5,6,7,6,4,0時空間中資料的變化過程。

可以發現:

1. 當緩存空間未滿時，資料一直往新的空間寫；
2. 當緩存滿，并且緩存中沒有需要通路的資料時，最先進入緩存的資料被淘汰掉；

3. 當緩存滿，并且緩存中有需要通路的資料時，做了一個資料交換，把通路的資料拿出來，其餘資料往下壓，最後把通路的資料放到頂部

   在這裡，可能有疑問，就是把“資料交換”于“資料完全新增和删除”有什麼差別呢？答案是性能，前者是移動指針，後者是更新整個記憶體空間，後者所花費的系統開銷遠比前者大得多。

實作

看了算法的介紹，我們想到的資料結構就是連結清單了。

• 雙向連結清單的資料結構

/**
     * 雙向連結清單資料結構
     */
    private class NodePair{
        NodePair frontNode;
        NodePair postNode;
        int data;
    }           

• 逆序查找連結清單

/**
     * 根據資料逆序查找連結清單中是否有此節點，有，則把該點提出來，放到current的位置
     * 當比對到的時候，傳回true
     * @param data
     */
    public boolean searchNode(int data){
        boolean flag = false;
        NodePair tempNode = current;
        //不比對，即沒找到，則繼續查找
        while(tempNode.frontNode != null || tempNode.data != data){
            tempNode = tempNode.frontNode;
        }
        //這個判讀表示比對到了
        if(tempNode.data == data){
            tempNode.frontNode.postNode = tempNode.postNode;
            tempNode.postNode.frontNode = tempNode.frontNode;
            current = tempNode;
            flag = true;
        }
        
        return flag;
    }           

• 空間滿了，并且緩存中沒有待通路的資料，删除最下面的節點，再新增一個節點，相當于重新指派最下面的節點，如圖

  

紅線表示，head将要指向倒數第二個點了，即，倒數第二個點要變成現在最底下的點了。

/**
     * 給head節點重新指派操作
     * 實作細節是：
     * 0.倒數第二個點（head的下一個點）的frontNode引用指向null
     * 1.給head所指節點重新指派
     * 2.current節點的frontNode引用指向head
     * 3.把current節點指向head
     * 4.把head指向head的下一個節點（即，倒數第二個點）
     */
    public void resetHeadNode(int data){
        NodePair secondNode = head.postNode;
        
        head.postNode.frontNode = null;
        
        head.data = data;
        head.frontNode = current;
        head.postNode = null;
        
        current.postNode = head;
        
        current = head;
        
        head = secondNode;
    }           

• 緩存滿了，查找緩存中是否有待通路資料，有的話，同時把有的資料放到current指針所指位置。

/**
     * 根據資料逆序查找連結清單中是否有此節點，有，則把該點提出來，放到current的位置
     * 當比對到的時候，傳回true
     * @param data
     */
    public boolean searchNode(int data){
        boolean flag = false;
        NodePair tempNode = current;
        //不比對，即沒找到，則繼續查找
        while(tempNode.frontNode != null || tempNode.data != data){
            tempNode = tempNode.frontNode;
        }
        //這個判讀表示比對到了
        if(tempNode.data == data){
            tempNode.frontNode.postNode = tempNode.postNode;
            tempNode.postNode.frontNode = tempNode.frontNode;
            current = tempNode;
            flag = true;
        }
        
        return flag;
    }           

• 新增節點

/**
     * 往LRU緩存中插入資料
     * @param data
     */
    public void addNode(int data){
        //緩存未滿，不需要删除，直接插入
        if(length <= size){
            NodePair tempNode = new NodePair();
            tempNode.frontNode = current;
            tempNode.postNode = null;
            tempNode.data = data;
            current = tempNode;
            length++;
        }
        //緩存滿了，查找緩存中有沒有資料
        else{
            if(!searchNode(data)){
                //緩存中沒有，需要給head節點重新指派
                resetHeadNode(data);
            }
        }
    }           

LRU算法的缺點

如果有幾個不符合“如果資料最近被通路過，那麼将來被通路的幾率也更高”的規律時，會破壞緩存，導緻性能下降。

總結

寫算法時，通過畫圖，寫步驟，先産生一個清晰的思路，然後一步步去做實作剛才思考的步驟。