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つの落とし穴があります:
-
C
最大のコイン値とする。ランタイムは、D
の表現がlog D
ビットのみを使用し、ランタイムがD/C
において少なくとも線形であるため、D/C
が多項式である限り、多項式のみである。 - すべてのステップで、アルゴリズムは局所最適を選択します。しかし、これはアルゴリズムがグローバルな最適解を(より多くの情報を参照してください見つかったと言うことは十分ではありませんここかのブックに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つのジョブが重複しない場合は互換性があります。例としての写真: 目標は、相互に互換性のあるジョブの最大サブセットを見つけることです。この問題には、いくつかの貪欲なアプローチがあります。
- 最も早い開始時間 :
sj
昇順でジョブを検討する - 最も早い終了時刻 :
fj
昇順でジョブを検討する - 最短間隔 :
fj-sj
昇順にジョブを検討する - 最も少ない競合 :各ジョブ
j
について、競合するジョブの数cj
問題は今、どちらのアプローチが本当に成功しているかです。 早い開始時間は間違いなく、ここに反例がある 最短間隔は最適ではない実際に最適化された競合はほとんどありませんが、ここではこのアプローチの問題点があります。 私たちは一番早く仕上げる 。擬似コードは静かです。
- 終了時刻別にジョブをソートすると、
f1<=f2<=...<=fn
-
A
空集合とする -
j
がA
セットA=A+{j}
内A
すべてのジョブと互換性がある場合、j=1
n
、 -
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を最小にすることである。
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
tj | 3 | 2 | 1 | 4 | 3 | 2 |
dj | 6 | 8 | 9 | 9 | 10 | 11 |
ジョブ | 3 | 2 | 2 | 5 | 5 | 5 | 4 | 4 | 4 | 4 | 1 | 1 | 1 | 6 | 6 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
時間 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Lj | -8 | -5 | -4 | 1 | 7 | 4 |
解L=7
は明らかに最適ではない。いくつかの貪欲な戦略を見てみましょう:
- 最短処理時間 :処理時間jの昇順にジョブをスケジュールする
- 最も早い締め切り1日目 :期限
dj
昇順にジョブをスケジュールする - 最小スラック :スラック
dj-tj
昇順にジョブをスケジュールする
その最短の処理時間が最初に最適ではないことがわかりやすいのは良いカウンターの例です
1 | 2 | |
---|---|---|
tj | 1 | 5 |
dj | 10 | 5 |
最小のスタックソリューションには類似の問題があります
1 | 2 | |
---|---|---|
tj | 1 | 5 |
dj | 3 | 5 |
最後の戦略が有効に見えるので、擬似コードから始めます。
- 期限までに
n
ジョブをソートすると、d1<=d2<=...<=dn
-
t=0
設定する -
j=1
n
- ジョブ
j
を区間[t,t+tj]
割り当てる - set
sj=t
、fj=t+tj
-
t=t+tj
設定する
- ジョブ
- 戻り間隔
[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
。
リクエストはキャッシュヒットで、アイテムがすでにキャッシュに入っている場合、それ以外の場合はキャッシュミスと呼ばれます。その場合、キャッシュがいっぱいであると仮定して、要求されたアイテムをキャッシュに持ち込み、別のアイテムを追い出す必要があります。目標は、退去の回数を最小限に抑える退去スケジュールです。
この問題のための数多くの貪欲な戦略があり、いくつかを見てみましょう:
- 先入れ先出し(FIFO) :最も古いページが追い出されます
- 最後に、先入れ先出し(LIFO) :最新のページが追い出される
- 直近の直近のアウト(LRU) :最も最近のアクセスが最も早い
- 最低限頻繁に要求された(LFU) :最も頻繁に要求されなかったページを削除する
- 最長前方距離(LFD) :将来最も遠くまで要求されないキャッシュ内のページを退去させる。
重要:以下の例では、2つ以上のページを追い出すことができる場合、最小の索引を持つページを退去させます。
例(FIFO)
キャッシュ・サイズがあるとするk=3
初期キャッシュ・a,b,c
および要求a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c
:
要求 | a | a | d | e | b | b | a | c | f | d | e | a | f | b | e | c |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
cache 1 | a | a | d | d | d | d | a | a | a | d | d | d | f | f | f | c |
cache 2 | b | b | b | e | e | e | e | c | c | c | e | e | e | b | b | b |
cache 3 | c | c | c | c | b | b | b | b | f | f | f | a | a | a | e | e |
キャッシュミス | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ |
16の要求による13のキャッシュミスが最適とは言えないので、別の戦略で同じ例を試すことができます。
例(LFD)
キャッシュ・サイズがあるとするk=3
初期キャッシュ・a,b,c
および要求a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c
:
要求 | a | a | d | e | b | b | a | c | f | d | e | a | f | b | e | c |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
cache 1 | a | a | d | e | e | e | e | e | e | e | e | e | e | e | e | c |
cache 2 | b | b | b | b | b | b | a | a | a | a | a | a | f | f | f | f |
cache 3 | c | c | c | c | c | c | c | c | f | d | d | d | d | b | b | b |
キャッシュミス | バツ | バツ | バツ | バツ | バツ | バツ | バツ | バツ |
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つ持っています:
- 適用 :戦略は呼び出し元にどのページを使用するかを伝える必要があります
- 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つの戦略もオンライン戦略です。オンライン問題については、一般的なアプローチが必要です。