algorithm
貪欲技術の応用

備考

チケットオートマット

最初の単純な例：

1、2、5、10および20という値のコインを交換するチケットオートマットがあります。交換のディスペンスは、正しい値が出されるまで一連のコインドロップと見ることができます。ディスペンスは、そのコインカウントがその価値に対して最小であるときに最適であると言います。

してみましょうMで[1,50]チケットの価格もTとPで[1,50]お金の誰かが支払っTで、 P >= M 。 D=PM 。我々は、差としてステップの利益定義D及びDc有するcコインこのステップでオート分配します。

交換のための欲張りテクニックは、以下の擬似アルゴリズムアプローチです。

ステップ1： D > 20で20コインを分配し、 D = D - 20
ステップ2： D > 10は10コインを分配し、 D = D - 10と設定する。
ステップ3： D > 5は5コインを分配し、 D = D - 5
ステップ4： D > 2で2コインを分配し、 D = D - 2
ステップ5： D > 1は1コインを分配し、 D = D - 1

その後、すべてのコインの合計は明らかにDに等しい。その欲張りなアルゴリズムは 、各ステップの後とステップの各反復の後に利益が最大化されるためです。より大きな利益をもたらす別のコインを分配することはできません。

プログラムとしてのチケットオートマット（C ++）：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// read some coin values, sort them descending,
// purge copies and guaratee the 1 coin is in it
std::vector<unsigned int> readInCoinValues();

int main()
{
    std::vector<unsigned int> coinValues;   // Array of coin values ascending    
    int ticketPrice;                        // M in example
    int paidMoney;                          // P in example

    // generate coin values
    coinValues = readInCoinValues();
    
    cout << "ticket price: ";
    cin >> ticketPrice;
    
    cout << "money paid: ";
    cin >> paidMoney;
    
    if(paidMoney <= ticketPrice)
    {
        cout << "No exchange money" << endl;
        return 1;
    }
    
    int diffValue = paidMoney - ticketPrice;
    
    // Here starts greedy

    // we save how many coins we have to give out
    std::vector<unsigned int> coinCount;
    
    for(auto coinValue  = coinValues.begin();
             coinValue != coinValues.end(); ++coinValue)
    {
        int countCoins = 0;
        
        while (diffValue >= *coinValue)
        {
            diffValue -= *coinValue;
            countCoins++;
        }
        
        coinCount.push_back(countCoins);
    }
    
    // print out result
    cout << "the difference " << paidMoney - ticketPrice 
         << " is paid with: " << endl;
    
    for(unsigned int i=0; i < coinValues.size(); ++i)
    {
        if(coinCount[i] > 0)
            cout << coinCount[i] << " coins with value " 
                 << coinValues[i] << endl;
    }
    
    return 0;
}

std::vector<unsigned int> readInCoinValues()
{
    // coin values
    std::vector<unsigned int> coinValues;
    
    // make sure 1 is in vectore
    coinValues.push_back(1);

    // read in coin values (attention: error handling is omitted)
    while(true)
    {
        int coinValue;
        
        cout << "Coin value (<1 to stop): ";
        cin >> coinValue;
        
        if(coinValue > 0)
            coinValues.push_back(coinValue);
        
        else
            break;
    }
    
    // sort values
    sort(coinValues.begin(), coinValues.end(), std::greater<int>());
    
    // erase copies of same value
    auto last = std::unique(coinValues.begin(), coinValues.end());
    coinValues.erase(last, coinValues.end());
    
    // print array
    cout << "Coin values: ";
    
    for(auto i : coinValues)
        cout << i << " ";
    
    cout << endl;
    
    return coinValues;
}

この例を単純にするための入力チェックがあることに注意してください。 1つの出力例：

Coin value (<1 to stop): 2
Coin value (<1 to stop): 4
Coin value (<1 to stop): 7
Coin value (<1 to stop): 9
Coin value (<1 to stop): 14
Coin value (<1 to stop): 4
Coin value (<1 to stop): 0
Coin values: 14 9 7 4 2 1 
ticket price: 34
money paid: 67
the difference 33 is paid with: 
2 coins with value 14
1 coins with value 4
1 coins with value 1

1がコインの値に入っている限り、アルゴリズムは終了します。理由は次のとおりです。

• Dはすべてのステップで厳密に減少する
• Dは決して>0ではなく、同時に最小コイン1より小さい

しかしアルゴリズムには2つの落とし穴があります：

1. C最大のコイン値とする。ランタイムは、 Dの表現がlog Dビットのみを使用し、ランタイムがD/Cにおいて少なくとも線形であるため、 D/Cが多項式である限り、多項式のみである。
2. すべてのステップで、アルゴリズムは局所最適を選択します。しかし、これはアルゴリズムがグローバルな最適解を（より多くの情報を参照してください見つかったと言うことは十分ではありませんここかのブックにKorteのとVygen ）。

簡単な例：コインは1,3,4 、 D=6です。最適解は明らかに価値3 2つのコインですが、欲張りは最初のステップで4を選ぶので、ステップ2と3で1を選択しなければなりません。それで、それは最適な差別を与えません。この例に対する可能な最適アルゴリズムは、 動的プログラミングに基づいている 。

インターバルスケジューリング

ジョブJ={a,b,c,d,e,f,g} 。 j in Jをsj開始よりも仕事にし、 fjで終了させる。 2つのジョブが重複しない場合は互換性があります。例としての写真： 目標は、相互に互換性のあるジョブの最大サブセットを見つけることです。この問題には、いくつかの貪欲なアプローチがあります。

1. 最も早い開始時間 ： sj昇順でジョブを検討する
2. 最も早い終了時刻 ： fj昇順でジョブを検討する
3. 最短間隔 ： fj-sj昇順にジョブを検討する
4. 最も少ない競合 ：各ジョブjについて、競合するジョブの数cj

問題は今、どちらのアプローチが本当に成功しているかです。 早い開始時間は間違いなく、ここに反例がある 最短間隔は最適ではない実際に最適化された競合はほとんどありませんが、ここではこのアプローチの問題点があります。 私たちは一番早く仕上げる 。擬似コードは静かです。

1. 終了時刻別にジョブをソートすると、 f1<=f2<=...<=fn
2. A空集合とする
3. jがAセットA=A+{j}内A すべてのジョブと互換性がある場合、 j=1 n 、
4. Aは相互に互換性のあるジョブの最大サブセットです

またはC ++プログラムとして：

#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>

const int jobCnt = 10;

// Job start times
const int startTimes[] = { 2, 3, 1, 4, 3, 2, 6, 7, 8, 9};

// Job end times
const int endTimes[]   = { 4, 4, 3, 5, 5, 5, 8, 9, 9, 10};

using namespace std;

int main()
{
    vector<pair<int,int>> jobs;
    
    for(int i=0; i<jobCnt; ++i)
        jobs.push_back(make_pair(startTimes[i], endTimes[i]));
    
    // step 1: sort
    sort(jobs.begin(), jobs.end(),[](pair<int,int> p1, pair<int,int> p2) 
                                     { return p1.second < p2.second; });
    
    // step 2: empty set A
    vector<int> A;
    
    // step 3:
    for(int i=0; i<jobCnt; ++i)
    {
        auto job = jobs[i];
        bool isCompatible = true;
        
        for(auto jobIndex : A)
        {
            // test whether the actual job and the job from A are incompatible
            if(job.second >= jobs[jobIndex].first &&
               job.first  <= jobs[jobIndex].second)
            {
                isCompatible = false;
                break;
            }
        }
    
        if(isCompatible)
            A.push_back(i);
    }
    
    //step 4: print A
    cout << "Compatible: ";
    
    for(auto i : A)
        cout << "(" << jobs[i].first << "," << jobs[i].second << ") ";
    cout << endl;
    
    return 0;
}

この例の出力は次のとおりです。 Compatible: (1,3) (4,5) (6,8) (9,10)

アルゴリズムの実装は明らかにΘ（n ^ 2）である。 Θ（n log n）の実装があり、関心のある読者は以下のように読むことができます（Javaの例）。

今、インターバルスケジューリング問題のための貪欲なアルゴリズムがありますが、最適ですか？

命題：欲張りアルゴリズムは最も早い終了時間が最適です。

証明：（ 矛盾によって）

グリーディが最適ではなく、 i1,i2,...,ikがグリーディによって選択されたジョブの集合を表すものと仮定する。 j1,j2,...,jmを、 r 可能な最大値に対してi1=j1,i2=j2,...,ir=jrである最適解のジョブの集合とする。

ジョブi(r+1)存在し、 j(r+1) （最も早い終了）の前に終了する。しかし、よりは、 j1,j2,...,jr,i(r+1),j(r+2),...,jmも最適解とすべてのためkにおいて[1,(r+1)] jk=ik 。 rの最大性に対する矛盾でr 。これで証明が終わります。

この第2の例は、通常、可能性のある欲張り戦略が多数存在することを示していますが、すべてのインスタンスで最適解を見つけ出す可能性もあります。

以下は、Θ（n log n）で実行されるJavaプログラムです。

import java.util.Arrays;
import java.util.Comparator;

class Job
{
    int start, finish, profit;

    Job(int start, int finish, int profit)
    {
        this.start = start;
        this.finish = finish;
        this.profit = profit;
    }
}


class JobComparator implements Comparator<Job>
{
    public int compare(Job a, Job b)
    {
        return a.finish < b.finish ? -1 : a.finish == b.finish ? 0 : 1;
    }
}

public class WeightedIntervalScheduling
{
    static public int binarySearch(Job jobs[], int index)
    {
        int lo = 0, hi = index - 1;

        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            if (jobs[mid].finish <= jobs[index].start)
            {
                if (jobs[mid + 1].finish <= jobs[index].start)
                    lo = mid + 1;
                else
                    return mid;
            }
            else
                hi = mid - 1;
        }

        return -1;
    }

    static public int schedule(Job jobs[])
    {
        Arrays.sort(jobs, new JobComparator());

        int n = jobs.length;
        int table[] = new int[n];
        table[0] = jobs[0].profit;

        for (int i=1; i<n; i++)
        {
            int inclProf = jobs[i].profit;
            int l = binarySearch(jobs, i);
            if (l != -1)
                inclProf += table[l];

            table[i] = Math.max(inclProf, table[i-1]);
        }

        return table[n-1];
    }

    public static void main(String[] args)
    {
        Job jobs[] = {new Job(1, 2, 50), new Job(3, 5, 20),
                    new Job(6, 19, 100), new Job(2, 100, 200)};

        System.out.println("Optimal profit is " + schedule(jobs));
    }
}

予想される出力は次のとおりです。

Optimal profit is 250

遅れの最小化

遅れを最小限にする問題は数多くあります。ここでは、一度に1つのジョブしか処理できない単一のリソースがあります。ジョブjは、 tj単位の処理時間を必要とし、時間dj起因する。 jが時刻sjで始まる場合、時刻fj=sj+tj 。すべてのjについてL=max{0,fj-dh}遅延L=max{0,fj-dh}を定義する。目標は、 最大遅れ Lを最小にすることである。

解L=7は明らかに最適ではない。いくつかの貪欲な戦略を見てみましょう：

1. 最短処理時間 ：処理時間jの昇順にジョブをスケジュールする
2. 最も早い締め切り1日目 ：期限dj昇順にジョブをスケジュールする
3. 最小スラック ：スラックdj-tj昇順にジョブをスケジュールする

その最短の処理時間が最初に最適ではないことがわかりやすいのは良いカウンターの例です

最小のスタックソリューションには類似の問題があります

最後の戦略が有効に見えるので、擬似コードから始めます。

1. 期限までにnジョブをソートすると、 d1<=d2<=...<=dn
2. t=0設定する
3. j=1 n
   • ジョブjを区間[t,t+tj]割り当てる
   • set sj=t 、 fj=t+tj
   • t=t+tj設定する
4. 戻り間隔[s1,f1],[s2,f2],...,[sn,fn]

そして、C ++の実装として：

#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>

const int jobCnt = 10;

// Job start times
const int processTimes[] = { 2, 3, 1, 4, 3, 2, 3, 5, 2, 1};

// Job end times
const int dueTimes[]     = { 4, 7, 9, 13, 8, 17, 9, 11, 22, 25};

using namespace std;

int main()
{
    vector<pair<int,int>> jobs;
    
    for(int i=0; i<jobCnt; ++i)
        jobs.push_back(make_pair(processTimes[i], dueTimes[i]));
    
    // step 1: sort
    sort(jobs.begin(), jobs.end(),[](pair<int,int> p1, pair<int,int> p2)
                                    { return p1.second < p2.second; });
    
    // step 2: set t=0
    int t = 0;
    
    // step 3:
    vector<pair<int,int>> jobIntervals;
    
    for(int i=0; i<jobCnt; ++i)
    {
        jobIntervals.push_back(make_pair(t,t+jobs[i].first));
        t += jobs[i].first;
    }
            
    //step 4: print intervals
    cout << "Intervals:\n" << endl;
    
    int lateness = 0;
    
    for(int i=0; i<jobCnt; ++i)
    {
        auto pair = jobIntervals[i];
        
        lateness = max(lateness, pair.second-jobs[i].second);

        cout << "(" << pair.first << "," << pair.second << ") "
             << "Lateness: " << pair.second-jobs[i].second << std::endl;
    }
    
    cout << "\nmaximal lateness is " << lateness << endl;
    
    return 0;
}

このプログラムの出力は次のとおりです。

Intervals:

(0,2)   Lateness:-2
(2,5)   Lateness:-2
(5,8)   Lateness: 0
(8,9)   Lateness: 0
(9,12)  Lateness: 3
(12,17) Lateness: 6
(17,21) Lateness: 8
(21,23) Lateness: 6
(23,25) Lateness: 3
(25,26) Lateness: 1

maximal lateness is 8

アルゴリズムの実行時間は明らかにΘ（n log n）である。なぜなら、ソートはこのアルゴリズムの支配的な操作であるからである。今、それが最適であることを示す必要があります。明らかに、最適スケジュールにはアイドル時間がありません。 最も早い締め切りの最初のスケジュールにはアイドル時間もありません。

d1<=d2<=...<=dnとなるようにジョブに番号が付けられていると仮定しd1<=d2<=...<=dn 。スケジュールの逆転は、ジョブiとj対であるので、 i<jが、jはi前にスケジュールされる。その定義のために、 最も早い締め切りの最初のスケジュールには反転がありません。もちろん、スケジュールに逆転がある場合は、連続してスケジュールされた逆ジョブのペアを持つスケジュールがあります。

命題： 2つの隣接して反転したジョブを入れ替えると、逆転の数が1つ減り、最大の遅さは増加しません 。

証明： Lスワップ前の遅れとし、その後の遅さをMする。隣接する2つのジョブを交換すると、他のジョブをその位置から移動させないので、すべてのk != i,jに対してLk=Mkとなる。

明らかに、仕事iが先に予定されていたので、 Mi<=Liです。ジョブjが遅い場合は、定義から次のようになります。

                         Mj = fi-dj    (definition)
                           <= fi-di    (since i and j are exchanged)
                           <= Li

これは、スワップ後の遅れが以前よりも小さいか等しいことを意味します。これで証明が終わります。

命題： 最も早い期限の最初のスケジュールSが最適です。

証明：（ 矛盾によって）

可能な限り少ない逆数で S*が最適スケジュールであると仮定します。 S*にアイドル時間がないと仮定できます。 S*に反転がない場合、 S=S*となります。 S*が反転を有する場合、それは隣接する反転を有するよりもむしろ。最後の命題は、遅れを増やさずに逆転の数を減らして隣接する逆転を入れ替えることができると述べている。これはS*の定義と矛盾する。

最短レイテンシ問題とそれに関連する最小限のメイパン問題を最小限に抑える問題は、最小限のスケジュールについての質問には現実世界で多くのアプリケーションがあります。しかし、通常、マシンは1台だけではなく、多くの人が同じタスクを異なる速度で処理します。これらの問題はNP完結を非常に速くします。

私たちが手作業ですべてのタスクとデータを手に入れているオフラインの問題ではなく、実行中にタスクが表示されるオンラインの変種を見ても、別の興味深い質問が発生します。

オフラインキャッシュ

キャッシングの問題は、有限空間の限界から生じる。私たちのキャッシュCはkページあると仮定します。今、私たちは、一連の処理したいm彼らはprocessed.Ofもちろん場合される前に、キャッシュに置かれていなければならない項目の要求m<=k後、私たちはただ、キャッシュ内のすべての要素を入れて、それが動作しますが、通常はm>>k 。

リクエストはキャッシュヒットで、アイテムがすでにキャッシュに入っている場合、それ以外の場合はキャッシュミスと呼ばれます。その場合、キャッシュがいっぱいであると仮定して、要求されたアイテムをキャッシュに持ち込み、別のアイテムを追い出す必要があります。目標は、退去の回数を最小限に抑える退去スケジュールです。

この問題のための数多くの貪欲な戦略があり、いくつかを見てみましょう：

1. 先入れ先出し（FIFO） ：最も古いページが追い出されます
2. 最後に、先入れ先出し（LIFO） ：最新のページが追い出される
3. 直近の直近のアウト（LRU） ：最も最近のアクセスが最も早い
4. 最低限頻繁に要求された（LFU） ：最も頻繁に要求されなかったページを削除する
5. 最長前方距離（LFD） ：将来最も遠くまで要求されないキャッシュ内のページを退去させる。

重要：以下の例では、2つ以上のページを追い出すことができる場合、最小の索引を持つページを退去させます。

例（FIFO）

キャッシュ・サイズがあるとするk=3初期キャッシュ・a,b,cおよび要求a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c ：

16の要求による13のキャッシュミスが最適とは言えないので、別の戦略で同じ例を試すことができます。

例（LFD）

キャッシュ・サイズがあるとするk=3初期キャッシュ・a,b,cおよび要求a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c ：

8回のキャッシュミスはずっと良くなります。

セルフテスト ：LIFO、LFU、RFUのサンプルを行い、何が起こっているかを見てください。

次の例のprogramm（C ++で書かれています）は、2つの部分で構成されています。

スケルトンはアプリケーションであり、選択された貪欲戦略に依存する問題を解決します。

#include <iostream>
#include <memory>

using namespace std;

const int cacheSize     = 3;
const int requestLength = 16;

const char request[]    = {'a','a','d','e','b','b','a','c','f','d','e','a','f','b','e','c'};
char cache[]            = {'a','b','c'};

// for reset
char originalCache[]    = {'a','b','c'};


class Strategy {

public:
    Strategy(std::string name) : strategyName(name) {}
    virtual ~Strategy() = default;

    // calculate which cache place should be used
    virtual int apply(int requestIndex)                                      = 0;

    // updates information the strategy needs
    virtual void update(int cachePlace, int requestIndex, bool cacheMiss)    = 0;

    const std::string strategyName;
};

bool updateCache(int requestIndex, Strategy* strategy)
{
    // calculate where to put request
    int cachePlace = strategy->apply(requestIndex);

    // proof whether its a cache hit or a cache miss
    bool isMiss = request[requestIndex] != cache[cachePlace];

    // update strategy (for example recount distances)
    strategy->update(cachePlace, requestIndex, isMiss);

    // write to cache
    cache[cachePlace] = request[requestIndex];

    return isMiss;
}

int main()
{
    Strategy* selectedStrategy[] = { new FIFO, new LIFO, new LRU, new LFU, new LFD };

    for (int strat=0; strat < 5; ++strat)
    {
        // reset cache
        for (int i=0; i < cacheSize; ++i) cache[i] = originalCache[i];

        cout <<"\nStrategy: " << selectedStrategy[strat]->strategyName << endl;

        cout << "\nCache initial: (";
        for (int i=0; i < cacheSize-1; ++i) cout << cache[i] << ",";
        cout << cache[cacheSize-1] << ")\n\n";

        cout << "Request\t";
        for (int i=0; i < cacheSize; ++i) cout << "cache " << i << "\t";
        cout << "cache miss" << endl;

        int cntMisses = 0;

        for(int i=0; i<requestLength; ++i)
        {
            bool isMiss = updateCache(i, selectedStrategy[strat]);
            if (isMiss) ++cntMisses;

            cout << "  " << request[i] << "\t";
            for (int l=0; l < cacheSize; ++l) cout << "  " << cache[l] << "\t";
            cout << (isMiss ? "x" : "") << endl;
        }

        cout<< "\nTotal cache misses: " << cntMisses << endl;
    }

    for(int i=0; i<5; ++i) delete selectedStrategy[i];
}

基本的な考え方は簡単です：リクエストごとに私は2つのコールを2つ持っています：

1. 適用 ：戦略は呼び出し元にどのページを使用するかを伝える必要があります
2. update ：呼び出し元が場所を使用した後、戦略が失敗したかどうかを戦略に伝えます。その後、戦略はその内部データを更新することができる。戦略LFUは 、例えばキャッシュページのヒット頻度を更新しなければならないが、 LFD戦略はキャッシュページの距離を再計算しなければならない。

次に、5つの戦略の実装例を見てみましょう。

FIFO

class FIFO : public Strategy {
public:
    FIFO() : Strategy("FIFO")
    {
        for (int i=0; i<cacheSize; ++i) age[i] = 0;
    }

    int apply(int requestIndex) override
    {
        int oldest = 0;

        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            else if(age[i] > age[oldest])
                oldest = i;
        }

        return oldest;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {
        // nothing changed we dont need to update the ages
        if(!cacheMiss)
            return;

        // all old pages get older, the new one get 0
        for(int i=0; i<cacheSize; ++i)
        {
            if(i != cachePos)
                age[i]++;

            else
                age[i] = 0;
        }
    }

private:
    int age[cacheSize];
};

FIFOは、ページがキャッシュ内のどのくらいの長さの情報を必要とするだけです（もちろん、他のページと比較して）。だから唯一行うべきことは、ミスを待ってから、ページを作ることです。ページは古いものではありません。上記の例の場合、プログラムのソリューションは次のとおりです。

Strategy: FIFO

Cache initial: (a,b,c)

Request    cache 0    cache 1    cache 2    cache miss
  a          a          b          c    
  a          a          b          c    
  d          d          b          c          x
  e          d          e          c          x
  b          d          e          b          x
  b          d          e          b    
  a          a          e          b          x
  c          a          c          b          x
  f          a          c          f          x
  d          d          c          f          x
  e          d          e          f          x
  a          d          e          a          x
  f          f          e          a          x
  b          f          b          a          x
  e          f          b          e          x
  c          c          b          e          x

Total cache misses: 13

Thatsは上の解と正確です。

LIFO

class LIFO : public Strategy {
public:
    LIFO() : Strategy("LIFO")
    {
        for (int i=0; i<cacheSize; ++i) age[i] = 0;
    }

    int apply(int requestIndex) override
    {
        int newest = 0;

        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            else if(age[i] < age[newest])
                newest = i;
        }

        return newest;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {
        // nothing changed we dont need to update the ages
        if(!cacheMiss)
            return;

        // all old pages get older, the new one get 0
        for(int i=0; i<cacheSize; ++i)
        {
            if(i != cachePos)
                age[i]++;

            else
                age[i] = 0;
        }
    }

private:
    int age[cacheSize];
};

LIFOの実装は、 FIFOとほぼ同じですが、最古のページではなく、最も若いものを追い出します。プログラムの結果は次のとおりです。

Strategy: LIFO

Cache initial: (a,b,c)

Request    cache 0    cache 1    cache 2    cache miss
  a          a          b          c    
  a          a          b          c    
  d          d          b          c          x
  e          e          b          c          x
  b          e          b          c    
  b          e          b          c    
  a          a          b          c          x
  c          a          b          c    
  f          f          b          c          x
  d          d          b          c          x
  e          e          b          c          x
  a          a          b          c          x
  f          f          b          c          x
  b          f          b          c    
  e          e          b          c          x
  c          e          b          c    

Total cache misses: 9

LRU

class LRU : public Strategy {
public:
    LRU() : Strategy("LRU")
    {
        for (int i=0; i<cacheSize; ++i) age[i] = 0;
    }

    // here oldest mean not used the longest
    int apply(int requestIndex) override
    {
        int oldest = 0;

        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            else if(age[i] > age[oldest])
                oldest = i;
        }

        return oldest;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {
        // all old pages get older, the used one get 0
        for(int i=0; i<cacheSize; ++i)
        {
            if(i != cachePos)
                age[i]++;

            else
                age[i] = 0;
        }
    }

private:
    int age[cacheSize];
};

LRUの場合、戦略はキャッシュページのものとは独立していますが、その唯一の関心は最後の使用です。プログラムの結果は次のとおりです。

Strategy: LRU

Cache initial: (a,b,c)

Request    cache 0    cache 1    cache 2    cache miss
  a          a          b          c    
  a          a          b          c    
  d          a          d          c          x
  e          a          d          e          x
  b          b          d          e          x
  b          b          d          e    
  a          b          a          e          x
  c          b          a          c          x
  f          f          a          c          x
  d          f          d          c          x
  e          f          d          e          x
  a          a          d          e          x
  f          a          f          e          x
  b          a          f          b          x
  e          e          f          b          x
  c          e          c          b          x

Total cache misses: 13

LFU

class LFU : public Strategy {
public:
    LFU() : Strategy("LFU")
    {
        for (int i=0; i<cacheSize; ++i) requestFrequency[i] = 0;
    }

    int apply(int requestIndex) override
    {
        int least = 0;

        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            else if(requestFrequency[i] < requestFrequency[least])
                least = i;
        }

        return least;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {
        if(cacheMiss)
            requestFrequency[cachePos] = 1;

        else
            ++requestFrequency[cachePos];
    }

private:

    // how frequently was the page used
    int requestFrequency[cacheSize];
};

LFUはページの使用頻度を最小限に抑えます。したがって、更新戦略はすべてのアクセスをカウントすることです。もちろん、見逃した後はカウントがリセットされます。プログラムの結果は次のとおりです。

Strategy: LFU

Cache initial: (a,b,c)

Request    cache 0    cache 1    cache 2    cache miss
  a          a          b          c    
  a          a          b          c    
  d          a          d          c          x
  e          a          d          e          x
  b          a          b          e          x
  b          a          b          e    
  a          a          b          e    
  c          a          b          c          x
  f          a          b          f          x
  d          a          b          d          x
  e          a          b          e          x
  a          a          b          e    
  f          a          b          f          x
  b          a          b          f    
  e          a          b          e          x
  c          a          b          c          x

Total cache misses: 10

LFD

class LFD : public Strategy {
public:
    LFD() : Strategy("LFD")
    {
        // precalc next usage before starting to fullfill requests
        for (int i=0; i<cacheSize; ++i) nextUse[i] = calcNextUse(-1, cache[i]);
    }

    int apply(int requestIndex) override
    {
        int latest = 0;

        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            else if(nextUse[i] > nextUse[latest])
                latest = i;
        }

        return latest;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {
            nextUse[cachePos] = calcNextUse(requestIndex, cache[cachePos]);
    }

private:

    int calcNextUse(int requestPosition, char pageItem)
    {
        for(int i = requestPosition+1; i < requestLength; ++i)
        {
            if (request[i] == pageItem)
                return i;
        }

        return requestLength + 1;
    }

    // next usage of page
    int nextUse[cacheSize];
};

LFDの戦略はこれまで誰もが違っていた。それは退去する人の将来の要求を使用する唯一の戦略です。この実装では、関数calcNextUseを使用して、次回の使用が将来最も遠くなるページを取得します。プログラムの解は上から手で解に等しい：

Strategy: LFD

Cache initial: (a,b,c)

Request    cache 0    cache 1    cache 2    cache miss
  a          a          b          c    
  a          a          b          c    
  d          a          b          d          x
  e          a          b          e          x
  b          a          b          e    
  b          a          b          e    
  a          a          b          e    
  c          a          c          e          x
  f          a          f          e          x
  d          a          d          e          x
  e          a          d          e    
  a          a          d          e    
  f          f          d          e          x
  b          b          d          e          x
  e          b          d          e    
  c          c          d          e          x

Total cache misses: 8 

欲張りの戦略LFDは実際に提示された5つの最適な戦略です。証明はかなりの長さで、見つけることができるここやジョン・クラインバーグとエヴァタルドスの本に（ダウン下の備考欄にソースを参照してください）。

アルゴリズム対現実

LFD戦略は最適ですが、大きな問題があります。その最適なオフラインソリューションです。プラクシスでは、キャッシュは通常オンラインの問題です。つまり、次回に特定のアイテムが必要になったときには、この戦略が役に立たないためです。他の4つの戦略もオンライン戦略です。オンライン問題については、一般的なアプローチが必要です。