LRUアルゴリズムC++実装

1832 ワード

全体的な考え方:ループキューは同時にノードのカウントを使用してノードの新旧情報をマークし、新しいノードが追加された場合、最も古いノードを空にし、新しいノードを追加します.具体的に絵を描いたほうが分かりやすいです.

#include 
#include 
#include 
#include 
using namespace std;

static const int LEN = 5;

int main(){
    vector vires(LEN,-1);//    
    vector vi(LEN,-1);//    
    deque empty;//                
    map mii,miires;//mii  vi      ，miires      vires    
    for(int i=0;i>itp){
        if(mii.count(vi[ict])){//    ，           
            --mii[vi[ict]];
            if(mii[vi[ict]]==0){
                empty.push_back(miires[vi[ict]]);
                mii.erase(mii.find(vi[ict]));
            }
        }
        vi[ict]=itp;//             
        mii[itp]+=1;
        ++ict;
        ict%=LEN;
        if(miires.count(itp)){
            auto atp = empty.begin();
            for(;atp!=empty.end();++atp){
                if(*atp==miires[itp]) break;
            }
            if(*atp == miires[itp]) empty.erase(atp);
        }
        else{//          ，     
            if(vires[empty.front()]!=-1) miires.erase(miires.find(vires[empty.front()]));
            vires[empty.front()]=itp;
            miires[itp]=empty.front();
            empty.pop_front();
            //print
            for(auto ieh:vires){
                if(ieh!=-1)
                    cout<

結果は次のとおりです.

1 2 3 4 5 6 5 4 3 1 7 9 1 2 3 5 6 9 4 2 1
1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
6 2 3 4 5 
6 1 3 4 5 
7 1 3 4 5 
7 1 3 4 9 
7 1 3 2 9 
5 1 3 2 9 
5 1 3 2 6 
5 9 3 2 6 
5 9 3 4 6 
5 9 2 4 6 
1 9 2 4 6

この実装では配列内で要素を検索する必要がある場合があり,効率が悪いのはここで,時間的複雑度O(1)の挿入と削除が必要であればhashMap+双方向チェーンテーブルを用いることである.

C++のincludeの使い方

HoudiniでStringとUTF8を行き来しよう。