目錄

常見(jiàn)的緩存算法

LRU緩存

LRU Cache具備的操作：

LRU的c++實(shí)現(xiàn)

雙鏈表節(jié)點(diǎn)的定義：

指定容量大小

刪除操作

插入操作

獲取操作

插入新節(jié)點(diǎn)

LRU完整C++代碼實(shí)現(xiàn)

LRU和LFU的區(qū)別

---

?

原文鏈接：?https://github.com/cpselvis，https://www.cnblogs.com/cpselvis/p/6272096.html；

對(duì)于web開(kāi)發(fā)而言，緩存必不可少，也是提高性能最常用的方式。無(wú)論是瀏覽器緩存(如果是chrome瀏覽器，可以通過(guò)chrome:😕/cache查看)，還是服務(wù)端的緩存(通過(guò)memcached或者redis等內(nèi)存數(shù)據(jù)庫(kù))。緩存不僅可以加速用戶的訪問(wèn)，同時(shí)也可以降低服務(wù)器的負(fù)載和壓力。那么，了解常見(jiàn)的緩存淘汰算法的策略和原理就顯得特別重要。

常見(jiàn)的緩存算法

• LRU (Least recently used) 最近最少使用，如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高。
• LFU (Least frequently used) 最不經(jīng)常使用，如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)使用次數(shù)很少，那么在將來(lái)一段時(shí)間內(nèi)被使用的可能性也很小。
• FIFO (Fist in first out) 先進(jìn)先出， 如果一個(gè)數(shù)據(jù)最先進(jìn)入緩存中，則應(yīng)該最早淘汰掉。

LRU緩存

像瀏覽器的緩存策略、memcached的緩存策略都是使用LRU這個(gè)算法，LRU算法會(huì)將近期最不會(huì)訪問(wèn)的數(shù)據(jù)淘汰掉。LRU如此流行的原因是實(shí)現(xiàn)比較簡(jiǎn)單，而且對(duì)于實(shí)際問(wèn)題也很實(shí)用，良好的運(yùn)行時(shí)性能，命中率較高。下面談?wù)勅绾螌?shí)現(xiàn)LRU緩存：

• 新數(shù)據(jù)插入到鏈表頭部
• 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問(wèn)），則將數(shù)據(jù)移到鏈表頭部
• 當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄

LRU Cache具備的操作：

• set(key,value)：如果key在hashmap中存在，則先重置對(duì)應(yīng)的value值，然后獲取對(duì)應(yīng)的節(jié)點(diǎn)cur，將cur節(jié)點(diǎn)從鏈表刪除，并移動(dòng)到鏈表的頭部；若果key在hashmap不存在，則新建一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)放到鏈表的頭部。當(dāng)Cache存滿的時(shí)候，將鏈表最后一個(gè)節(jié)點(diǎn)刪除即可。
• get(key)：如果key在hashmap中存在，則把對(duì)應(yīng)的節(jié)點(diǎn)放到鏈表頭部，并返回對(duì)應(yīng)的value值；如果不存在，則返回-1。

LRU的c++實(shí)現(xiàn)

LRU實(shí)現(xiàn)采用雙向鏈表 + Map 來(lái)進(jìn)行實(shí)現(xiàn)。這里采用雙向鏈表的原因是：如果采用普通的單鏈表，則刪除節(jié)點(diǎn)的時(shí)候需要從表頭開(kāi)始遍歷查找，效率為O(n)，采用雙向鏈表可以直接改變節(jié)點(diǎn)的前驅(qū)的指針指向進(jìn)行刪除達(dá)到O(1)的效率。使用Map來(lái)保存節(jié)點(diǎn)的key、value值便于能在O(logN)的時(shí)間查找元素,對(duì)應(yīng)get操作。

雙鏈表節(jié)點(diǎn)的定義：

struct CacheNode {int key; // 鍵int value; // 值CacheNode *pre, *next; // 節(jié)點(diǎn)的前驅(qū)、后繼指針CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {} };

指定容量大小

對(duì)于LRUCache這個(gè)類(lèi)而言，構(gòu)造函數(shù)需要指定容量大小

LRUCache(int capacity) {size = capacity; // 容量head = NULL; // 鏈表頭指針tail = NULL; // 鏈表尾指針 }

刪除操作

雙鏈表的節(jié)點(diǎn)刪除操作：

void remove(CacheNode *node) {if (node -> pre != NULL){node -> pre -> next = node -> next;}else{head = node -> next;}if (node -> next != NULL){node -> next -> pre = node -> pre;}else{tail = node -> pre;} }

插入操作

將節(jié)點(diǎn)插入到頭部的操作：

void setHead(CacheNode *node) {node -> next = head;node -> pre = NULL;if (head != NULL){head -> pre = node;}head = node;if (tail == NULL){tail = head;} }

獲取操作

get(key)操作的實(shí)現(xiàn)比較簡(jiǎn)單，直接通過(guò)判斷Map是否含有key值即可，如果查找到key，則返回對(duì)應(yīng)的value，否則返回-1;

int get(int key) {map<int, CacheNode *>::iterator it = mp.find(key);if (it != mp.end()){CacheNode *node = it -> second;remove(node);setHead(node);return node -> value;}else{return -1;} }

插入新節(jié)點(diǎn)

set(key, value)操作需要分情況判斷。如果當(dāng)前的key值對(duì)應(yīng)的節(jié)點(diǎn)已經(jīng)存在，則將這個(gè)節(jié)點(diǎn)取出來(lái)，并且刪除節(jié)點(diǎn)所處的原有的位置，并在頭部插入該節(jié)點(diǎn)；如果節(jié)點(diǎn)不存在節(jié)點(diǎn)中，這個(gè)時(shí)候需要在鏈表的頭部插入新節(jié)點(diǎn)，插入新節(jié)點(diǎn)可能導(dǎo)致容量溢出，如果出現(xiàn)溢出的情況，則需要?jiǎng)h除鏈表尾部的節(jié)點(diǎn)。

void set(int key, int value) {map<int, CacheNode *>::iterator it = mp.find(key);if (it != mp.end()){CacheNode *node = it -> second;node -> value = value;remove(node);setHead(node);}else{CacheNode *newNode = new CacheNode(key, value);if (mp.size() >= size){map<int, CacheNode *>::iterator iter = mp.find(tail -> key);remove(tail);mp.erase(iter);}setHead(newNode);mp[key] = newNode;} }

至此，LRU算法的實(shí)現(xiàn)操作就完成了。

LRU完整C++代碼實(shí)現(xiàn)

/*** System design: LRU cache (least recently used).** cpselvis(cpselvis@gmail.com)* Oct 8th, 2016*/ #include<iostream> #include<map>using namespace std;/*** Definition of cachelist node, it's double linked list node.*/ struct CacheNode {int key;int value;CacheNode *pre, *next;CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {} };class LRUCache{ private:int size; // Maximum of cachelist size.CacheNode *head, *tail;map<int, CacheNode *> mp; // Use hashmap to store public:LRUCache(int capacity){size = capacity;head = NULL;tail = NULL;}int get(int key){map<int, CacheNode *>::iterator it = mp.find(key);if (it != mp.end()){CacheNode *node = it -> second;remove(node);setHead(node);return node -> value;}else{return -1;}}void set(int key, int value){map<int, CacheNode *>::iterator it = mp.find(key);if (it != mp.end()){CacheNode *node = it -> second;node -> value = value;remove(node);setHead(node);}else{CacheNode *newNode = new CacheNode(key, value);if (mp.size() >= size){map<int, CacheNode *>::iterator iter = mp.find(tail -> key);remove(tail);mp.erase(iter);}setHead(newNode);mp[key] = newNode;}}void remove(CacheNode *node){if (node -> pre != NULL){node -> pre -> next = node -> next;}else{head = node -> next;}if (node -> next != NULL){node -> next -> pre = node -> pre;}else{tail = node -> pre;}}void setHead(CacheNode *node){node -> next = head;node -> pre = NULL;if (head != NULL){head -> pre = node;}head = node;if (tail == NULL){tail = head;}} };int main(int argc, char **argv) {LRUCache *lruCache = new LRUCache(2);lruCache -> set(2, 1);lruCache -> set(1, 1);cout << lruCache -> get(2) << endl;lruCache -> set(4, 1);cout << lruCache -> get(1) << endl;cout << lruCache -> get(2) << endl; }

LRU和LFU的區(qū)別

LRU是最近最少使用頁(yè)面置換算法(Least Recently Used),也就是首先淘汰最長(zhǎng)時(shí)間未被使用的頁(yè)面!

LFU是最近最不常用頁(yè)面置換算法(Least Frequently Used),也就是淘汰一定時(shí)期內(nèi)被訪問(wèn)次數(shù)最少的頁(yè)!

比如,第二種方法的時(shí)期T為10分鐘,如果每分鐘進(jìn)行一次調(diào)頁(yè),主存塊為3,若所需頁(yè)面走向?yàn)? 1 2 1 2 3 4

注意,當(dāng)調(diào)頁(yè)面4時(shí)會(huì)發(fā)生缺頁(yè)中斷

若按LRU算法,應(yīng)換頁(yè)面1(1頁(yè)面最久未被使用) 但按LFU算法應(yīng)換頁(yè)面3(十分鐘內(nèi),頁(yè)面3只使用了一次)

可見(jiàn)LRU關(guān)鍵是看頁(yè)面最后一次被使用到發(fā)生調(diào)度的時(shí)間長(zhǎng)短,

而LFU關(guān)鍵是看一定時(shí)間段內(nèi)頁(yè)面被使用的頻率!

總結(jié)

以上是生活随笔為你收集整理的常见缓存算法和LRU与LFU的c++实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。