初めに

初めましてえれです。

修士の時ネットのワークのキャッシングについて研究していました。その際に意外とキャッシュアルゴリズムの記事が少なかったため備忘録もかねて書いていきたいと思います。

注意点として今回はvectorを使用していますが、
c++でキャッシュアルゴリズムを実装する上で使用するSTDのライブラリでLISTを使うかVECTORを使うかは自分が実現したい仕組みに即したものを選択してください。
vectorにもlistにもそれぞれ利点と欠点があります。
特に学術分野のシミュレーションで使用するのであれば演算速度が重視されるかと思うのでプログラム設計はしっかりとやってからプログラムしましょう。

コンパイラをインストールするのが面倒な方はこちらがおすすめです。
paiza.IO

stdを使用する際はリファレンスを読みましょう
stdのリファレンス

FIFO

まずは先入れ先出しのキャッシングアルゴリズムであるFIFO(First In, First Out)です。
こちらの動作は簡単でデータを入れていきキャッシュ（またはバッファ）などからあふれた場合に古いデータから削除していくアルゴリズムです。

プログラムとしてはint型のデータが100個入る配列を作り、vectorでキャッシュ（またはバッファ）を作成します。
intの配列はfor文でもよかったのですが、lfuを見越して別に作成しました。

#プログラム解説

キャッシュ容量は5としているので、下記の部分ではキャッシュ容量が溜まるまでを書いています。
出力部分が多いのでわかりずらいですが、大切な部分はv1.emplace_back(nu[i]);くらいです。

部分.cpp

 if(v1.size() <= 4){
        v1.emplace_back(nu[i]);
        cout << "==" << i+1 << "回目 ==" << endl;    
        for(auto a :v1){cout << a << " ";}
        cout << endl;
     }

次にキャッシュ容量が満タンになった状態で新しい数字がキャッシュに入る場合の動作を書いています。
vectorにはlistのようなpop_frontの関数がないのでeraseで配列の先頭（begin）を削除し値を挿入する。
この場合、vectorは可変長のため挿入してから削除してもよいが、実際に実現したい動きとは違ってしまうため削除→挿入の順にしている。

部分.cpp

 else if(v1.size() == 5){
        cout << "==" << i+1 << "回目 ==" << endl;
        cout << "削除された値：" << v1.front() << endl; 
        v1.erase(v1.begin());
        v1.emplace_back(nu[i]);
        for(auto a :v1){cout << a  << " ";}
        cout << endl;
      }

以下全文

mein.cpp

#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
int main(void){

    vector<int> v1;

    int nu[100];
    int i;

    for (i = 0; i < 100; i++ ) {
        nu[i] = i;
    }

    //配列nuに0から99の数字が挿入された
    //今回の配列サイズは5
    for (i = 0; i < 100; i++ ) {
     if(v1.size() <= 4){
        v1.emplace_back(nu[i]);
        cout << "==" << i+1 << "回目 ==" << endl;    
        for(auto a :v1){cout << a << " ";}
        cout << endl;
     }else if(v1.size() == 5){
        cout << "==" << i+1 << "回目 ==" << endl;
        cout << "削除された値：" << v1.front() << endl; 
        v1.erase(v1.begin());
        v1.emplace_back(nu[i]);
        for(auto a :v1){cout << a  << " ";}
        cout << endl;
      }
    }  
}

LRU

次に参照された回数でキャッシュ内を入れ替えるLFUを紹介する。
先にも書いた通りこのアルゴリズムはキャッシュ内のデータが参照された回数をカウントしておき
その回数でキャッシュ内を入れ替える。

今回は2度目の挿入が行われた場合に順番を入れ替え、実際に配列の中身のカウントを行うことはせず入れ替えるのみとしている。
動きの一例としては
[古→　　新]
[1 2 3 4 5]

３が来た場合、3を削除し
[1 2 4 5]

3を入れなおす
[古→　　新]
[1 2 4 5 3]
この動作を繰り返すことでLFUを実現している。

また、ランダム関数を使うことでランダムな数字が配列に格納されていく。
そうすることで、上記の動きを再現できるような環境としている。

main.cpp

#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
int main(void){

    vector<int> v1;
    int nu[100];

    int s;
    srand(time(NULL));

    for(int i = 0; i <100; i++){
        s = rand() % 10;
        nu[i] = s;
    }

    for(int i = 0; i <100; i++){

    if(v1.size() <= 4){
        v1.emplace_back(nu[i]);
        cout << "==" << i+1 << "回目" << "：来た数字：" << nu[i] << "==" << endl; 
        cout << "古      新" << endl;
        for(auto a :v1){cout << a << " ";}
        cout << endl;
    }else if(v1.size() == 5){

    for(auto it = v1.begin(); it != v1.end(); it++){
    if(*it == nu[i]){
    cout << "==" << i+1 << "回目" << "：来た数字：" << nu[i] << "==" << endl;
    cout<<"入れ替えました：" << *it << endl;
    cout << "古      新" << endl;
    v1.emplace_back(nu[i]);
    v1.erase(it);
    for(auto a :v1){cout << a  << " ";}
    cout << endl;
    break;
    }
    continue;
    }

    cout << "==" << i+1 << "回目" << "：来た数字：" << nu[i] << "==" << endl;
    cout << "削除された値：" << v1.front() << endl; 
    cout << "古      新" << endl;
    v1.erase(v1.begin());
    v1.emplace_back(nu[i]);
    for(auto a :v1){cout << a  << " ";}
    cout << endl;
    } 
    }
}

最後に

最後までお読みいただきありがとうございました。
私自身の研鑽につながるため、ご指摘や修正案などお気軽にコメントをお願い致します。

出力のコメントの多いプログラムとなってしまいましたが、アルゴリズム系は机上でやっていると頭が混乱し
振出しに戻ってしまうことが多々ありました。
そのため、自分の見やすい出力で注釈をつけることはとても大切なことだと感じています。

プログラムになれていくるとGDBなどのデバックツールを使うため、こういったコメントはつけなってきます。

今後

実際に配列の中身をカウントし都度入れ替えるLFUや最後に参照された時間でキャッシュを入れ替えるLRUなどを実装してみたいと考えている。

c++でキャッシュアルゴリズム(fifo lfu)

初めに

FIFO

LRU

最後に

今後