LRUCacheの設計とC++の実現

1.LRUCacheの概要
去年中興の筆記試験のLRUCache Missの回数に基づいて、今日LeetCodeをしてまたLRUCacheを設計することがあって、1日の時間を使って研究します.
LRUはLeast Recently Usedの略で、最近最も少ない使用を意味し、Cache置換アルゴリズムである.Cacheとは?狭義のCacheとは、CPUとホストメモリとの間に位置する高速RAMを指し、通常はシステムホストメモリのようにDRAM技術を使用するのではなく、高価だが高速なSRAM技術を使用する.広義のCacheとは、データ伝送速度の差を調整するために、速度差が大きい2つのハードウェアの間に位置する構造を指す.CPUとホストメモリの間にCacheがあるほか、メモリとハードディスクの間にもCacheがあり、ハードディスクとネットワークの間にも何らかの意味でのCacheがある.インターネット一時フォルダやネットワークコンテンツキャッシュなどと呼ばれる.
Cacheの容量は限られているので、Cacheの容量が切れた後、新しいコンテンツが追加される必要がある場合は、既存のコンテンツの一部を選択して捨て、新しいコンテンツを再生するための空間を空ける必要があります.LRU Cacheの置き換えの原則は、最近最も少ない内容を置き換えることです.実は、LRUは最も長く使われていないほうがイメージ的です.このアルゴリズムが置き換えるたびに、しばらく使われていない内容が一番長いからです.
2.LRUCacheのデザイン
2.1概要
LRUの典型的な実装は、 + を使用し、双方向チェーンテーブルはデータノードを格納し、ハッシュの目的は、チェーンデータ構造の線形ルックアップ複雑度O(n)をO(1)に低減することである.
また、ハッシュについては、STLではhash_mapが実装されているが、C++規格には含まれていないが、unordered_mapが推奨される.
最近最も使用されている置換原則を分析すると、以下の結論が得られます.
双方向チェーンテーブルはデータ構造として、管理を容易にするためにヘッダノードとテールノードを設定し、あるノードがアクセスされると、チェーンテーブルの前にどの位置にあっても、そのノードのアクセス時間が最新のアクセス時間となり、ヘッダノードの後に挿入する必要がある.同様に、cacheがいっぱいになったら、cacheの内容を置き換える必要があります.エンドノードに近づくほど、アクセス時間が早くなり、つまり最も長くアクセスされていないことを説明するには、エンドノードの前のノードを削除する必要があります.
2.2インタフェース
LRUCacheには主に2つのインタフェースがあります.

void Put(K key , T data);
T Get(K key);

2つのインタフェースは4つの状況を議論する必要がある:1.Get関数keyアクセスに成功し(cache hitと呼ばれる)、dataを直接返します.2.Get関数、keyアクセスに失敗しました(cache missと称する)LeetCodeは直接-1を返すことを要求し、ここでcache missの回数を計算するにはput関数を呼び出す必要がある.3.Put関数、cacheがいっぱいになったら末尾ノードを削除し、新しいノードをヘッダに挿入する.4.Put関数、cacheがいっぱいになっていなければ、ヘッダに直接挿入する.
2.3実装
少し複雑な方法は、テンプレートでカプセル化することです.lru.h

//lru.h
#ifndef __LRU_H__
#define __LRU_H__
#include 
#include //C++11 
//#include //The STL has hash_map,not standard
#include 
using namespace std;

template <typename K,typename T>
struct Node{
    K key;
    T data;
    Node*prev,*next;
};

template <typename K,typename T>
class LRUCache{
public:
    LRUCache(size_t size);
    ~LRUCache();
    void Put(K key,T data);
    T Get(K key);
    int getCount(){return count;}//cache miss count
private:
    void attach(Node *node);//      
    void detach(Node *node);//       

    int count;//cache miss count
    unordered_map* >hashmap_;//hash 
    vector< Node* >free_entries_;//    cache    ，     pool
    Node*head_,*tail_;//      
    Node*entries_;//  cache    
};

template <typename K,typename T>
LRUCache::LRUCache(size_t size)//construct
{
    count=0;
    entries_ = new Node[size];
    for(int i=0;inew Node;
     tail_ = new Node;
     head_->prev = NULL;
     head_->next = tail_;
     tail_->prev = head_;
     tail_->next = NULL;
}
template <typename K,typename T>
LRUCache::~LRUCache()//destruct
{
    delete head_;
    delete tail_;
    delete[] entries_;
}

template <typename K,typename T>
void LRUCache::Put(K key,T data)
{
    Node*node = hashmap_[key];
    if(NULL!=node)//cache hit
    {
        detach(node);
        node->key=key;
        node->data=data;
        attach(node);
    }
    else//update
    {
        if(free_entries_.empty())//cache full
        {
            node=tail_->prev;
            detach(node);
            hashmap_.erase(node->key);        
        }
        else//  
        {
            node = free_entries_.back();
            free_entries_.pop_back();
        }
        //     
        node->key=key;
        node->data=data;
        hashmap_[key]=node;
        attach(node);
    }
}
template <typename K,typename T>
T LRUCache::Get(K key)
{
    Node *node = hashmap_[key];
    if(NULL!=node)//cache hit
    {
        detach(node);
        attach(node);
        return node->data;
    }
    else//cache miss
    {
        ++count;
        Put(key,T());
    //  return T();
    }
}

template <typename K,typename T>
void LRUCache::attach(Node *node)
{
    node->next=head_->next;
    head_->next=node;
    node->next->prev=node;
    node->prev=head_;
}

template <typename K,typename T>
void LRUCache::detach(Node *node)
{
    node->prev->next=node->next;
    node->next->prev=node->prev;
}

#endif

main.cpp
ここではcache miss countを使用して正確性を検証します.

//main.cpp

#include "lru.h"
#include 
int main()
{
#if 0
    int size=3;
    int num=16;
    vector<int>pages={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0};
    LRUCache<int,int>lru(size);
    for(int i = 0;i < num; ++i)
    {
        lru.Get(pages[i]);
    }
    cout<//11
#endif
    int size =2;
    int num=9;
    vector<int>pages={2,3,1,3,2,1,4,3,2 };
    LRUCache<int,int>lru(size);
    for(int i = 0;i < num; ++i)
    {
        lru.Get(pages[i]);
    }
    cout<//8
    return 0;
}

Makefile

PROGS=main
CLEANFILES = core core.* *.core *.o temp.* *.out typescript* \
        *.lc *.lh *.bsdi *.sparc *.uw

all :${PROGS}


CXXFLAGS+=-g  -std=c++11

main: main.o
    ${CXX} ${CXXFLAGS} -o $@ $^
    @rm *.o
clean:
    rm -f ${PROGS} ${CLEANFILES}

3.参考
1.http://www.hawstein.com/posts/lru-cache-impl.html 2.http://stackoverflow.com/questions/5908581/is-hash-map-part-of-the-stl