建站
咨詢
售后
建站咨詢
新聞中心
C++培訓(xùn)LRU是什么，相信很多人對這個都還不是很了解!今天，小編就給大家介紹LRU Cache 的簡單 C++ 實現(xiàn)
LRU Cache是一個Cache的置換算法，含義是“最近最少使用”，把滿足“最近最少使用”的數(shù)據(jù)從Cache中剔除出去，并且保證Cache中第一個數(shù)據(jù)是最近剛剛訪問的，因為這樣的數(shù)據(jù)更有可能被接下來的程序所訪問。
LRU的應(yīng)用比較廣泛，最基礎(chǔ)的內(nèi)存頁置換中就用了，對了，這里有個概念要清楚一下，Cache不見得是CPU的高速緩存的那個Cache，這里的Cache直接翻譯為緩存，就是兩種存儲方式的速度有比較大的差別，都可以用Cache緩存數(shù)據(jù)，比如硬盤明顯比內(nèi)存慢，所以常用的數(shù)據(jù)我們可以Cache在內(nèi)存中。
LRU 基本算法描述
前提：
由于我只是簡單實現(xiàn)一下這個算法，所以數(shù)據(jù)都用int代替，下一個版本會改成模板形式的，更加通用。
要求：
只提供兩個接口，一個獲取數(shù)據(jù)getValue(key),一個寫入數(shù)據(jù)putValue(key,value)
無論是獲取還是寫入數(shù)據(jù)，當前這個數(shù)據(jù)要保持在最容易訪問的位置
緩存數(shù)量有限，最長時間沒被訪問的數(shù)據(jù)應(yīng)該置換出緩存
算法：
為了滿足上面幾個條件，實際上可以用一個雙向鏈表來實現(xiàn)，每次訪問完數(shù)據(jù)(不管是獲取還是寫入)，調(diào)整雙向鏈表的順序，把剛剛訪問的數(shù)據(jù)調(diào)整到鏈表的最前方，以后再訪問的時候速度將最快。
為了方便，提供一個頭和一個尾節(jié)點，不存具體的數(shù)，鏈表的基本形式如下面的這個簡單表述
Head <===> Node1 <===> Node2 <===> Node3 <===> Near
OK，就這么些，比較簡單，實現(xiàn)起來也不難，用c++封裝一個LRUCache類，類提供兩個方法，分別是獲取和更新，初始化類的時候傳入Cache的節(jié)點數(shù)。
先定義一個存數(shù)據(jù)的節(jié)點數(shù)據(jù)結(jié)構(gòu)
typedef struct _Node_{
int key; //鍵
int value; //數(shù)據(jù)
struct _Node_ *next; //下一個節(jié)點
struct _Node_ *pre; //上一個節(jié)點
}CacheNode;
類定義：
class LRUCache{
public:
LRUCache(int cache_size=10); //構(gòu)造函數(shù)，默認cache大小為10
~LRUCache(); //析構(gòu)函數(shù)
int getValue(int key); //獲取值
bool putValue(int key,int value); //寫入或更新值
void displayNodes(); //輔助函數(shù)，顯示所有節(jié)點
private:
int cache_size_; //cache長度
int cache_real_size_; //目前使用的長度
CacheNode *p_cache_list_head; //頭節(jié)點指針
CacheNode *p_cache_list_near; //尾節(jié)點指針
void detachNode(CacheNode *node); //分離節(jié)點
void addToFront(CacheNode *node); //將節(jié)點插入到第一個
};
類實現(xiàn)：
LRUCache::LRUCache(int cache_size)
{
cache_size_=cache_size;
cache_real_size_=0;
p_cache_list_head=new CacheNode();
p_cache_list_near=new CacheNode();
p_cache_list_head->next=p_cache_list_near;
p_cache_list_head->pre=NULL;
p_cache_list_near->pre=p_cache_list_head;
p_cache_list_near->next=NULL;
}
LRUCache::~LRUCache()
{
CacheNode *p;
p=p_cache_list_head->next;
while(p!=NULL)
{
delete p->pre;
p=p->next;
}
delete p_cache_list_near;
}
void LRUCache::detachNode(CacheNode *node)
{
node->pre->next=node->next;
node->next->pre=node->pre;
}
void LRUCache::addToFront(CacheNode *node)
{
node->next=p_cache_list_head->next;
p_cache_list_head->next->pre=node;
p_cache_list_head->next=node;
node->pre=p_cache_list_head;
}
int LRUCache::getValue(int key)
{
CacheNode *p=p_cache_list_head->next;
while(p->next!=NULL)
{
if(p->key == key) //catch node
{
detachNode(p);
addToFront(p);
return p->value;
}
p=p->next;
}
return -1;
}
bool LRUCache::putValue(int key,int value)
{
CacheNode *p=p_cache_list_head->next;
while(p->next!=NULL)
{
if(p->key == key) //catch node
{
p->value=value;
getValue(key);
return true;
}
p=p->next;
}
if(cache_real_size_ >= cache_size_)
{
cout << "free" <
p=p_cache_list_near->pre->pre;
delete p->next;
p->next=p_cache_list_near;
p_cache_list_near->pre=p;
}
p=new CacheNode();//(CacheNode *)malloc(sizeof(CacheNode));
if(p==NULL)
return false;
addToFront(p);
p->key=key;
p->value=value;
cache_real_size_++;
return true;
}
void LRUCache::displayNodes()
{
CacheNode *p=p_cache_list_head->next;
while(p->next!=NULL)
{
cout << " Key : " << p->key << " Value : " << p->value << endl;
p=p->next;
}
cout << endl;
}
說在后面的話
其實，程序還可以優(yōu)化，首先，把數(shù)據(jù)int類型換成模板形式的通用類型，另外，數(shù)據(jù)查找的時候復(fù)雜度為O(n)，可以換成hash表來存數(shù)據(jù)，鏈表只做置換處理，這樣查找添加的時候速度將快很多。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
網(wǎng)頁題目：C++教程：LRUCache的簡單C++實現(xiàn)-創(chuàng)新互聯(lián)
當前鏈接：http://fisionsoft.com.cn/article/dhgced.html
