LRU算法 -- 連結清單 完整實作

LRU算法(Least Recently Used) 算是我們經常遇到的一種淘汰算法，其中記憶體管理子產品進行記憶體頁回收時有用到，針對不經常使用的記憶體頁，LRU淘汰政策能夠将該記憶體頁回收給作業系統。

屬于 我們作業系統設計中的 時間局部性原理，最長時間未被通路的資料優先淘汰，當記憶體中已存在的資料再次被通路時，則進行熱度的提升。

本文為了鞏固資料結構相關知識，特 使用連結清單資料結構方式完整實作LRU連結清單的功能。關于資料結構和算法相關的學習導圖可以借鑒​​資料結構和算法導圖​​

實作算法思路：

LRU 功能的實作:

1. 已有連結清單中存在 待插入元素，則将該元素在連結清單中删除，并頭插法到連結清單頭節點

2. 已有連結清單中不存在 待插入元素：

a. 若 LRU 容量已滿，則删除尾元素，頭插目前元素

b. 若 LRU 容量未滿，則直接頭插法目前元素

以上實作 使用其他的線性表資料結構（棧、隊列、數組）均能夠實作，連結清單的實作方式如下：

#include <iostream>

using namespace std;

typedef int DataType;

/*節點類*/
class Node{
    public:
    DataType val;
    Node *next;
};

class List{
private:
    int maxSize;
    int length;
    Node *head;

public:
    List();
    List(int size);
    ~List();
    
    void insertElementBegin(DataType x); //頭插法建立連結清單
    bool findElement(DataType x);        //查找連結清單中是否存在元素x,存在則傳回true，不存在則傳回false
    void deleteElementEnd();             //删除連結清單的最後一個節點
    bool deleteElem(DataType x);         //删除連結清單中值為x的節點，删除成功則傳回true,不存在則傳回false
    bool isEmpty();                      //判斷連結清單是否為空，是則傳回true,否則傳回false
    bool isFull();                       //判斷連結清單是否滿，是則傳回true,否則傳回false
    void printAll();                     //列印連結清單中的元素，連結清單長度，LRU長度
    
    void * findElemOptim(DataType x);       //針對此應用的優化，查找,傳回指定元素的前一個節點的指針
    void deleteElemOptim(void * node);     //針對此應用的優化，删除
};

List::List(){
    head = new Node;
    head -> next = NULL;
    this -> length = 0;
    this -> maxSize = 10;
}

List::List(int size) {
    head = new Node;
    head -> next = NULL;
    this -> length = 0;
    this -> maxSize = size;
}

List::~List() {
    Node* p, *tmp;
    p = head;
    while(p -> next) {
        tmp = p -> next;
        p -> next = p -> next -> next;
        delete tmp;
    }
    delete head;
    this -> head = NULL;
    this -> length = 0;
}

void List::insertElementBegin(DataType x) {
    Node *p = new Node;
    p -> val = x;
    
    p -> next = head -> next;
    head -> next = p;
    
    this -> length ++;
}

bool List::findElement(DataType x) {
    Node *p = head;
    
    while(p -> next != NULL) {
        if(p -> val == x) {
            return true;
        }
        p = p -> next;
    }
    
    return false;
}

void List::deleteElementEnd() {
    if(head -> next == NULL) {
        return;
    }
    
    Node *tmp;
    Node *p = head;
    while(p -> next != NULL && p -> next -> next != NULL) {
        p = p -> next;
    }
    
    tmp = p -> next;
    p -> next = tmp -> next;
    this -> length --;
    
    delete tmp;
}

bool List::deleteElem(DataType x) {
    Node *p = head;
    Node *tmp;
    while(p -> next != NULL) {
        if(p -> next -> val == x) {
            tmp = p -> next;
            p -> next = tmp -> next;
            
            delete tmp;
            this -> length --;
            
            return true;
        }
        p = p -> next;
    }
    
    return false;
}

bool List::isEmpty() {
    return this -> length == 0 ? true:false;
}

bool List::isFull() {
    return this -> length == maxSize ? true:false;
}

void List::printAll() {
    Node *p;
    p = head;
    
    cout << "lru list length :" << this -> length << endl;
    cout << "lru list maxSize :" << this -> maxSize << endl;
    cout << "lru list val:" << endl;
    
    while(p -> next != NULL) {
        p = p -> next;
        cout << p -> val << " ";
    }
    
    cout << endl;
}

void * List::findElemOptim(DataType x) {
    Node *p = head;
    while(p -> next != NULL) {
        if(p -> next -> val == x) {
            return (void *)p;
        }
        p = p -> next;
    }
    
    return NULL;
}

void List::deleteElemOptim(void *node) {
    Node *p, *tmp;
    p = (Node*)node;
    
    tmp = p -> next;
    p -> next = tmp -> next;
    delete tmp;
    
    this -> length --;
}

int main() {
    cout << "test LRU:" << endl;
    
    List list(10);
    int num = 0;
    while(1) {
        cout << "please enter a number, 99999 = exit" << endl;
        cin >> num;
        
        if(num == 9999) {
            break;
        }
        
        /*
        LRU 功能的實作:
        1. 已有連結清單中存在 待插入元素，則将該元素在連結清單中删除，并頭插法到連結清單頭節點
        2. 已有連結清單中不存在 待插入元素：
           a. 若 LRU 容量已滿，則删除尾元素，頭插目前元素
           b. 若 LRU 容量未滿，則直接頭插法目前元素           
        */
        Node *node = (Node*)list.findElemOptim(num);
        if(node != NULL) {
            list.deleteElemOptim(node);
            list.insertElementBegin(num);
        } else {
            if(list.isFull()) {
                list.deleteElementEnd();
                list.insertElementBegin(num);
            } else {
                list.insertElementBegin(num);
            }
        }
        
        list.printAll();
    }
    
    return 0;
}      

test LRU:
please enter a number, 99999 = exit
2
lru list length :1
lru list maxSize :10
lru list val:
2 
please enter a number, 99999 = exit
3
lru list length :2
lru list maxSize :10
lru list val:
3 2 
please enter a number, 99999 = exit
4
lru list length :3
lru list maxSize :10
lru list val:
4 3 2
...
...
...
please enter a number, 99999 = exit #輸入了34，此時LRU容量已滿，則删除尾元素，頭插入34
34
lru list length :10
lru list maxSize :10
lru list val:
34 23 12 11 1 8 7 3 2 6 
please enter a number, 99999 = exit #輸入23，提升23的熱度
23
lru list length :10
lru list maxSize :10
lru list val:
23 34 12 11 1 8 7 3 2 6 
please enter a number, 99999 = exit #輸入2，提升2的熱度
2
lru list length :10
lru list maxSize :10
lru list val:
2 23 34 12 11 1 8 7 3 6 
please enter a number, 99999 = exit
9999