什麼是 LRU 算法
LRU 是一種緩存淘汰策略。計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新的內容騰位置。但是要刪除哪些內容呢？我們肯定希望刪掉那些沒有用的緩存，而把有用的數據繼續留在緩存中，方便之後繼續使用。LRU 的全稱是 Least Recently Used，也就是說我們認為最近使用過的數據應該是有用的，很久都沒用過的數據應該是無用的，緩存滿了就優先刪除那些很久沒有用過的數據。
LRU 算法的特點
首先是緩存的大小是有限的。每次從緩存當中獲取數據的時候，如果獲取成功會將數據移動到最頭部。同時新添加的元素也是在頭部。當緩存大小達到上限之後，添加元素時會刪除最久未使用的元素，也就是鍊表的最後一個元素，然後將新的元素插入在鍊表頭。
LRU 的應用場景
LRU 算法可以用來管理我們的緩存數據。控制我們的緩存大小，用較少的緩存空間達到更高的緩存數據。舉例來說我們可以將一些不容易發生變化的數據且頭部效應表中的數據加入到緩存當中。
編碼實現
結構定義
#include <stdio.h>#include <stdlib.h>#include <string.h>// 默認容量#define N 10// 表示這個鍊表的長度信息int len = 0;//當前鍊表的元素個數信息int count = 0;typedefstruct Node{ /* data */char *key; char *value; struct Node *next; struct Node *prev;} Node;// 鍊表的頭節點和尾節點struct Node *head;struct Node *tail;// 函數預聲明// 創建節點Node *createNode(char *key, char *value);// 插入節點到頭部void insertHead(Node *node);// 移除尾部節點void removeTail();// 添加節點操作void add(char *key, char *value);// 刪除鍊表中的一個節點Node *deleteNode(Node *node);// 獲取指定key的值char *get(char *key);// 銷毀數據void destory();插入操作
// 獲取一個元素void add(char *key, char *value){ Node *node = createNode(key, value); //第一個元素if (head == NULL) { insertHead(node); return; } //判斷整個鍊表中是否存在整個元素 Node *now = deleteNode(node); // 如果找到了元素 將元素移動至末尾 結束方法if (now != NULL) { // 設置新的值 now->value = value; insertHead(now); return; } // 此時鍊表中是不存在這個元素// 判斷鍊表的長度if (count >= len) { removeTail(); } // 將新元素添加至末尾 insertHead(node); return;}獲取操作
char *get(char *key){ if (key == NULL) { return NULL; } // 尋找元素 Node *node = createNode(key, NULL); Node *now = deleteNode(node); // 釋放空間free(node); // 元素存在if (now != NULL) { //將元素調整到末尾 insertHead(now); return now->value; } return NULL;}基本操作函數
// 創建一個節點Node *createNode(char *key, char *value){ Node *node = (Node *)malloc(sizeof(Node)); node->key = key; node->value = value; node->prev = node->next = NULL; return node;}// 將節點插入到頭節點部分void insertHead(Node *node){ // 元素為空時if (head == NULL) { tail = head = node; count++; return; } node->next = head; head->prev = node; // 移動鍊表的末尾指針 head = node; // 計數 count++;}// 移除void removeTail(){ //移除最久未使用的那個元素 Node *now = tail; if (now != NULL) { // 獲取前一個節點 Node *p = now->prev; if (p != NULL) { // 斷開當前節點 同時移動尾節點 p->next = NULL; tail = p; } else { head = tail = NULL; } // 當前節點置空 now->prev = now->next = NULL; // 元素減少 count--; // 釋放空間free(now); }}// 鍊表中刪除一個節點 刪除成功返回被刪除節點Node *deleteNode(Node *node){ Node *now = head; while (now != NULL) { // 存在節點if (strcmp(now->key, node->key) == 0) { // 獲取前後節點 Node *p = now->prev; Node *n = now->next; // 更新指向if (n != NULL) { n->prev = p; } else { tail = p; } if (p != NULL) { p->next = n; } else { head = n; } //當前節點置空 now->prev = NULL; now->next = NULL; count--; break; } now = now->next; } return now;}// 銷毀數據void destory(){ Node *node = head; while (node != NULL) { Node *n = node; free(n); node = node->next; } len = 0; count = 0; head = tail = NULL;}// 從頭節點開始列印整個鍊表void printLink(){ Node *now = head; while (now != NULL) { printf("[key=%s,value=%s]", now->key, now->value); now = now->next; } printf("\n");}最後的測試函數
int main(){ init(5); add("1", "1"); add("2", "2"); printLink(); char *res = get("1"); printLink(); printf("value=%s\n", res); add("3", "3"); add("4", "4"); add("5", "5"); add("6", "6"); printLink(); res = get("1"); printLink(); destory(); return0;}// 輸出結果：/*[key=2,value=2][key=1,value=1][key=1,value=1][key=2,value=2]value=1[key=6,value=6][key=5,value=5][key=4,value=4][key=3,value=3][key=1,value=1][key=1,value=1][key=6,value=6][key=5,value=5][key=4,value=4][key=3,value=3]*/以上就是一個鍊表實現 LRU 算法的大體代碼。已將代碼上傳至https://gitlab.com/BitLegend/c-data-structure.git
感謝你能看到這裡，歡迎關注我的公眾號：BitLegend,我們下期見！