LRU (Least recently used，最近最少使用 ) 和 LFU (Least frequently used，最不經(jīng)常使用)是兩種經(jīng)典的cache管理算法库车。其主要差別在于其核心思想：
- LRU：如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高
- LFU：如果數(shù)據(jù)在最近一段時間內(nèi)訪問次數(shù)越少，那么將來被訪問的幾率也越低
LRU和LFU具備的操作主要是：get and put.
-
get(key)- 返回key對應(yīng)的值寒随，如果key不存在，則返回-1 -
put(key, value)- 如果key存在則將其對應(yīng)的值設(shè)置為value帮坚，如果key不存在妻往，則插入新的節(jié)點。如果cache已經(jīng)滿了试和，則需要以某種準(zhǔn)則（滿足某種函數(shù)f(x)）去除cache中已存在的節(jié)點讯泣。
這一數(shù)據(jù)結(jié)構(gòu)的核心在于當(dāng)存儲空間滿了要插入新的節(jié)點時，以何種規(guī)則（即所謂的f(x)）丟棄相應(yīng)的節(jié)點灰署。在設(shè)計LRU 和 LFU時的主要差別也在于此判帮。
LRU的設(shè)計與實現(xiàn)
為了快速找到最早更新的節(jié)點，可選的數(shù)據(jù)結(jié)構(gòu)有：queue溉箕，heap晦墙，linked list。由于題目又要求快速訪問指定節(jié)點肴茄，并且在訪問之后要更新它的時間順序晌畅，queue和heap不太適用。因此考慮使用linked list寡痰，這里我們選用double linked list抗楔，簡化節(jié)點的刪除操作棋凳，實現(xiàn)O(1)的刪除效率。并用hash table以便實現(xiàn)O(logn)時間隨機訪問節(jié)點连躏。
首先是雙鏈表的節(jié)點定義：
struct Node{
Node *pre;
Node *next;
int key;
int val;
Node(int k,int v):key(k),val(v),pre(NULL),next(NULL){}
};
使用map將key與相應(yīng)的節(jié)點對應(yīng)起來剩岳，實現(xiàn)以O(shè)(logn)時間隨機訪問linked list中的相應(yīng)節(jié)點，并進行刪除更新等相關(guān)操作入热。另外在構(gòu)造函數(shù)中還需指定capacity的大信淖亍：
class LRUCache {
public：
LRUCache(int capacity) {
capacity_ = capacity;
head = NULL;
tail = NULL;
keyToNode.clear();
}
private:
int capacity_;
Node *head;//頭節(jié)點
Node *tail;//尾節(jié)點
unordered_map<int,Node*> keyToNode;//key與節(jié)點Node的map
};
下面設(shè)計輔助函數(shù)。由于我們將節(jié)點按照使用的時間順序插入double linked list當(dāng)中勺良，所以頭節(jié)點是最少最近使用的節(jié)點绰播，而尾節(jié)點是最近使用的節(jié)點。因此首先設(shè)計三個函數(shù)：刪除頭節(jié)點：removeHead()以及插入新節(jié)點：insertToEnd(int k, int v)尚困，以及更新已存在節(jié)點在雙鏈表中的順序：moveToEnd(int key)蠢箩。
void insertToEnd(int k, int v){
//if full or already exist, return
if(isFull()||keyToNode.count(k)!=0) return;
Node *nd = new Node(k,v);
keyToNode[k] = nd;
//if head = tail = NULL
if(!head){
head = tail = nd;
}
else{
tail->next = nd;
nd->pre = tail;
tail = tail->next;
}
}
void removeHead(){
//if head not exist
if(!head) return;
keyToNode.erase(head->key);
Node *tmp = head;
if(head == tail)//if only one node
{
head = tail = NULL;
}
else{
head = head->next;
head->pre = NULL;
}
delete tmp;
}
void moveToEnd(int key){
//if key not exist or already in the end
if(keyToNode.count(key) == 0|| keyToNode[key] == tail) return;
Node *nd = keyToNode[key];
if(nd == head)//if at the front
{
head = head->next;
head->pre = NULL;
}
else{
nd->pre->next = nd->next;
nd->next->pre = nd->pre;
}
tail->next = nd;
nd->pre = tail;
nd->next = NULL;
tail = tail->next;
}
get(int key)函數(shù)的設(shè)計比較簡單，直接查找map中key值是否存在事甜，如果不存在返回-1谬泌，反之，更新節(jié)點位置到鏈表尾端并返回其值即可讳侨。
int get(int key) {
if(keyToNode.count(key) == 0) return -1;
//如果存在呵萨，將節(jié)點更新到鏈表尾端
moveToEnd(key);
return keyToNode[key]->val;
}
put(int key, int value)分為以下情況：1.如果節(jié)點存在，只需要更新節(jié)點的值并更新節(jié)點在鏈表中的位置(moveToEnd)即可跨跨。這里我們使用get函數(shù)判斷節(jié)點是否存在潮峦，則可以省略moveToEnd操作。2.如果節(jié)點不存在勇婴，則插入節(jié)點前需要判斷是否溢出忱嘹，如果溢出，則先將頭節(jié)點刪除再在尾節(jié)點插入新節(jié)點即可耕渴。
void put(int key, int value) {
//if already exist, update value
if(get(key)!=-1){
keyToNode[key]->val = value;
return;
}
//if not exist, insert
if(isFull()) removeHead();
insertToEnd(key,value);
}
代碼清單： https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/LeetCode/LRUCache.hpp
以上即是LRU詳解與C++實現(xiàn)拘悦，LFU的詳解與實現(xiàn)將在下一篇文章介紹，敬請期待橱脸。
