algorithm
Anwendungen der gierigen Technik

Bemerkungen

Ticketautomat

Erstes einfaches Beispiel:

Sie haben einen Ticketautomaten, der den Umtausch in Münzen mit den Werten 1, 2, 5, 10 und 20 ermöglicht. Die Ablehnung des Umtauschs kann als Reihe von Münzeinfällen betrachtet werden, bis der richtige Wert ausgegeben wird. Wir sagen, eine Disposition ist optimal, wenn die Anzahl der Münzen für ihren Wert minimal ist.

Sei M in [1,50] der Preis für das Ticket T und P in [1,50] das Geld, das jemand für T bezahlt hat, mit P >= M Sei D=PM . Wir definieren den Vorteil einer Stufe als die Differenz zwischen D und Dc mit c der Münze der automat Abgabe in diesem Schritt.

Die gierige Technik für den Austausch ist der folgende pseudo-algorithmische Ansatz:

Schritt 1: Geben Sie bei D > 20 eine 20 - Münze ein und setzen Sie D = D - 20
Schritt 2: Geben Sie bei D > 10 eine Münze ein und setzen Sie D = D - 10
Schritt 3: Wenn D > 5 geben Sie 5 Münzen aus und setzen Sie D = D - 5
Schritt 4: Während D > 2 eine 2 Münze ausgeben und D = D - 2
Schritt 5: Während D > 1 eine Münze ausgeben und D = D - 1

Danach ist die Summe aller Münzen eindeutig D Es ist ein gieriger Algorithmus, denn nach jedem Schritt und nach jeder Wiederholung eines Schrittes wird der Nutzen maximiert. Wir können keine andere Münze mit höherem Nutzen ausgeben.

Nun der Ticketautomat als Programm (in 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;
}

Beachten Sie, dass jetzt eine Eingabeüberprüfung erfolgt, damit das Beispiel einfach bleibt. Ein Beispiel für eine Ausgabe:

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

Solange 1 in den Münzwerten ist, wird der Algorithmus jetzt beendet, weil:

• D nimmt mit jedem Schritt strikt ab
• D ist niemals >0 und gleichzeitig kleiner als die kleinste Münze 1

Der Algorithmus hat jedoch zwei Fallstricke:

1. Sei C der größte Münzenwert. Die Laufzeit ist nur Polynom, solange D/C Polynom ist, da die Darstellung von D nur log D Bits verwendet und die Laufzeit in D/C mindestens linear ist.
2. In jedem Schritt wählt unser Algorithmus das lokale Optimum. Dies reicht jedoch nicht aus, um zu sagen, dass der Algorithmus die global optimale Lösung findet (siehe weitere Informationen hier oder im Book of Korte und Vygen ).

Ein einfaches Gegenbeispiel: Die Münzen sind 1,3,4 und D=6 . Die optimale Lösung ist eindeutig zwei Münzen Wert 3 aber gierige wählt 4 in der ersten Stufe , so dass es wählen hat 1 in Schritt zwei und drei. Es gibt also keine optimale Soution. Ein möglicher optimaler Algorithmus für dieses Beispiel basiert auf dynamischer Programmierung .

Intervallplanung

Wir haben eine Reihe von Jobs J={a,b,c,d,e,f,g} . Sei j in J ein Job als sein Start bei sj und endet bei fj . Zwei Jobs sind kompatibel, wenn sie sich nicht überlappen. Ein Bild als Beispiel: Ziel ist es, die maximale Teilmenge der miteinander kompatiblen Jobs zu finden . Es gibt mehrere gierige Ansätze für dieses Problem:

1. Früheste Startzeit : Berücksichtigen Sie Jobs in aufsteigender Reihenfolge von sj
2. Früheste Endzeit : Berücksichtigen Sie Jobs in aufsteigender Reihenfolge von fj
3. Kürzestes Intervall : Berücksichtigen Sie Jobs in aufsteigender Reihenfolge von fj-sj
4. Wenigste Konflikte : Zählen Sie für jeden Job j die Anzahl der in Konflikt stehenden Jobs cj

Die Frage ist nun, welcher Ansatz wirklich erfolgreich ist. Frühe Startzeit definitiv nicht, hier ein Gegenbeispiel Das kürzeste Intervall ist auch nicht optimal und die wenigsten Konflikte klingen in der Tat optimal, aber für diesen Ansatz gibt es einen Problemfall: Das lässt uns mit der frühesten Endzeit . Der Pseudocode ist ziemlich einfach:

1. Sortieren Sie die Jobs nach der Endzeit, sodass f1<=f2<=...<=fn
2. Sei A eine leere Menge
3. für j=1 bis n wenn j mit allen Jobs in A kompatibel ist, setze A=A+{j}
4. A ist eine maximale Teilmenge von miteinander kompatiblen Jobs

Oder als C ++ - Programm:

#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;
}

Die Ausgabe für dieses Beispiel ist: Compatible: (1,3) (4,5) (6,8) (9,10)

Die Implementierung des Algorithmus ist eindeutig in Θ (n ^ 2). Es gibt eine Implementierung von Θ (n log n), und der interessierte Leser kann unten weiterlesen (Java-Beispiel).

Jetzt haben wir einen gierigen Algorithmus für das Intervall-Scheduling-Problem, aber ist er optimal?

Vorschlag: Der gierige Algorithmus, der früheste Endzeitpunkt, ist optimal.

Beweis: (im Widerspruch)

Angenommen, Greedy ist nicht optimal, und i1,i2,...,ik bezeichnen die von Greedy ausgewählten Jobs. j1,j2,...,jm bezeichnen die Menge von Jobs in einer optimalen Lösung mit i1=j1,i2=j2,...,ir=jr für den größten möglichen Wert von r .

Der Job i(r+1) existiert und endet vor j(r+1) (frühestes Ende). Aber dann ist j1,j2,...,jr,i(r+1),j(r+2),...,jm auch eine optimale Lösung und für alle k in [1,(r+1)] ist jk=ik . das ist ein Widerspruch zur Maximalität von r . Damit ist der Beweis abgeschlossen.

Dieses zweite Beispiel zeigt, dass es in der Regel viele mögliche gierige Strategien gibt, aber nur einige oder gar keine werden in jedem Fall die optimale Lösung finden.

Unten ist ein Java-Programm, das in in (n log n) ausgeführt wird.

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));
    }
}

Und der erwartete Output ist:

Optimal profit is 250

Minimierung der Verspätung

Es gibt zahlreiche Probleme bei der Minimierung der Latenzzeit. Hier haben wir eine einzige Ressource, die jeweils nur einen Job verarbeiten kann. Der Job j erfordert tj Einheiten Verarbeitungszeit und ist zum Zeitpunkt dj fällig. Wenn j zum Zeitpunkt sj startet, sj es zum Zeitpunkt fj=sj+tj . Wir definieren die Latenz L=max{0,fj-dh} für alle j . Ziel ist es, die maximale Verspätung L zu minimieren.

Die Lösung L=7 ist offensichtlich nicht optimal. Schauen wir uns einige gierige Strategien an:

1. Kürzeste Bearbeitungszeit zuerst : Jobs in aufsteigender Reihenfolge und Bearbeitungszeit j 'einplanen
2. Frühester Termin zuerst : Planen Sie die Jobs in aufsteigender Reihenfolge nach dem Termin dj
3. Kleinster Slack : Planen Sie Jobs in aufsteigender Reihenfolge von Slack dj-tj

Es ist leicht zu erkennen, dass die kürzeste Bearbeitungszeit zunächst nicht optimal ist

Die kleinste Stapellösung weist ähnliche Probleme auf

Die letzte Strategie scheint gültig zu sein, also beginnen wir mit einem Pseudo-Code:

1. n Jobs nach Fälligkeit sortieren, so dass d1<=d2<=...<=dn
2. Setze t=0
3. für j=1 bis n
   • Weisen Sie den Job j dem Intervall [t,t+tj]
   • setze sj=t und fj=t+tj
   • setze t=t+tj
4. Rückkehrintervalle [s1,f1],[s2,f2],...,[sn,fn]

Und als Implementierung in 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;
}

Und die Ausgabe für dieses Programm ist:

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

Die Laufzeit des Algorithmus ist offensichtlich Θ (n log n), da die Sortierung die dominierende Operation dieses Algorithmus ist. Jetzt müssen wir zeigen, dass es optimal ist. Natürlich hat ein optimaler Zeitplan keine Leerlaufzeit . der erste Termin hat auch keine Wartezeit.

Nehmen wir an, die Jobs sind nummeriert, so dass d1<=d2<=...<=dn . Wir sagen, eine Inversion eines Zeitplans ist ein Paar von Jobs i und j so dass i<j aber j ist vor i . Aufgrund seiner Definition hat der früheste Termin zuerst keine Inversionen. Wenn ein Zeitplan eine Umkehrung hat, hat er natürlich ein Paar invertierter Jobs, die nacheinander geplant werden.

Vorschlag: Durch das Austauschen zweier benachbarter, invertierter Jobs wird die Anzahl der Inversionen um eins verringert und die maximale Verzögerung nicht erhöht .

Beweis: Sei L die Verspätung vor dem Swap und M die Verspätung danach. Da beim Austausch zweier benachbarter Jobs die anderen Jobs nicht aus ihrer Position verschoben werden, ist Lk=Mk für alle k != i,j .

Es ist eindeutig Mi<=Li seit dem Job, den i früher eingeplant habe. Wenn Job j spät kommt, folgt aus der Definition:

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

Das bedeutet, dass die Verspätung nach dem Swap kleiner oder gleich ist als zuvor. Damit ist der Beweis abgeschlossen.

Vorschlag: Der früheste erste Termin S ist optimal.

Beweis: (im Widerspruch)

Nehmen wir an, S* ist ein optimaler Zeitplan mit einer möglichst geringen Anzahl von Inversionen. Wir können davon ausgehen, dass S* keine Leerlaufzeit hat. Wenn S* keine Inversionen hat, dann ist S=S* und wir sind fertig. Wenn S* eine Inversion hat, dann hat es eine angrenzende Inversion. Der letzte Satz besagt, dass wir die angrenzende Inversion austauschen können, ohne die Latenz zu erhöhen, aber die Anzahl der Inversionen zu verringern. Dies widerspricht der Definition von S* .

Das Problem der Minimierung der Verspätung und das damit zusammenhängende Problem der minimalen Spieldauer , bei dem die Frage nach einem minimalen Zeitplan gestellt wird, hat viele Anwendungen in der realen Welt. Normalerweise haben Sie jedoch nicht nur eine Maschine, sondern viele, und sie erledigen dieselbe Aufgabe zu unterschiedlichen Raten. Diese Probleme werden sehr schnell NP-vollständig.

Eine weitere interessante Frage stellt sich, wenn wir uns nicht mit dem Offline- Problem beschäftigen, bei dem alle Aufgaben und Daten zur Verfügung stehen, sondern bei der Online- Variante, bei der Aufgaben während der Ausführung auftreten.

Offline-Zwischenspeicherung

Das Caching-Problem ergibt sich aus der Begrenzung des begrenzten Raums. Nehmen wir an, unser Cache C hat k Seiten. Jetzt möchten wir eine Abfolge von m Elementanforderungen verarbeiten, die vor der Verarbeitung in den Cache gestellt werden müssen. Wenn m<=k , werden alle Elemente einfach in den Cache gestellt, und es funktioniert, aber normalerweise ist es m>>k .

Eine Anforderung ist ein Cache-Treffer , wenn sich das Objekt bereits im Cache befindet, andernfalls wird es als Cache-Miss bezeichnet . In diesem Fall müssen wir das angeforderte Element in den Cache laden und ein anderes löschen, vorausgesetzt der Cache ist voll. Das Ziel ist ein Räumungsplan, der die Anzahl der Räumungen minimiert .

Es gibt zahlreiche gierige Strategien für dieses Problem, schauen wir uns einige an:

1. First In, First Out (FIFO) : Die älteste Seite wird geräumt
2. Last in, first out (LIFO) : Die neueste Seite wird geräumt
3. Letzte Ausgabe (LRU) : Evict-Seite, deren jüngster Zugriff am frühesten war
4. Am wenigsten häufig angefragte (LFU) : Seite entfernen, die am seltensten angefordert wurde
5. Longest Forward Distance (LFD) : Die Seite im Cache wird entfernt, die erst in der Zukunft angefordert wird.

Achtung: Für die folgenden Beispiele entfernen wir die Seite mit dem kleinsten Index, wenn mehr als eine Seite geräumt werden könnte.

Beispiel (FIFO)

Die Cache-Größe sei k=3 der anfängliche Cache a,b,c und die Anforderung a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Dreizehn Cache-Fehler von sechzehn Anforderungen klingen nicht sehr optimal. Versuchen wir dasselbe Beispiel mit einer anderen Strategie:

Beispiel (LFD)

Die Cache-Größe sei k=3 der anfängliche Cache a,b,c und die Anforderung a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Acht Cache-Fehler sind viel besser.

Selbsttest : Machen Sie das Beispiel für LIFO, LFU, RFU und schauen Sie, was passiert ist.

Das folgende Beispielprogramm (in C ++ geschrieben) besteht aus zwei Teilen:

Das Skelett ist eine Anwendung, die das Problem abhängig von der gewählten Strategie löst:

#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];
}

Die Grundidee ist einfach: Für jede Anfrage habe ich zwei Aufrufe, zwei meine Strategie:

1. Anwenden : Die Strategie muss dem Anrufer mitteilen, welche Seite verwendet werden soll
2. Update : Nachdem der Anrufer den Ort verwendet hat, teilt er der Strategie mit, ob es sich um einen Fehlschlag handelt oder nicht. Dann kann die Strategie ihre internen Daten aktualisieren. Die Strategie- LFU muss beispielsweise die Trefferhäufigkeit für die Cache-Seiten aktualisieren, während die LFD- Strategie die Entfernungen für die Cache-Seiten neu berechnen muss.

Schauen wir uns nun Beispiel-Implementierungen für unsere fünf Strategien an:

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 benötigt lediglich die Information, wie lange eine Seite im Cache ist (und natürlich nur relativ zu den anderen Seiten). Das einzige, was zu tun ist, ist, auf einen Fehler zu warten und dann die Seiten zu erstellen, die nicht älter wurden. Für unser Beispiel oben lautet die Programmlösung:

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

Das ist genau die Lösung von oben.

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];
};

Die Implementierung von LIFO ist mehr oder weniger dieselbe wie bei FIFO, aber wir entfernen die jüngste nicht die älteste Seite. Die Programmergebnisse sind:

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];
};

Im Falle von LRU ist die Strategie unabhängig von dem, was sich auf der Cache-Seite befindet. Das einzige Interesse gilt der letzten Verwendung. Die Programmergebnisse sind:

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 entfernt die Seite am wenigsten. Die Update-Strategie besteht also darin, jeden Zugriff zu zählen. Nach einem Fehlschlag wird der Zähler natürlich zurückgesetzt. Die Programmergebnisse sind:

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];
};

Die LFD- Strategie unterscheidet sich von allen zuvor. Es ist die einzige Strategie, die die zukünftigen Anträge für ihre Entscheidung verwendet, um sie zu räumen. Die Implementierung verwendet die Funktion calcNextUse , um die Seite zu erhalten, deren nächste Verwendung in Zukunft am weitesten entfernt ist. Die Programmlösung ist der Lösung von Hand gleich:

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 

Die gierige Strategie LFD ist in der Tat die einzige optimale Strategie der fünf vorgestellten. Der Beweis ist ziemlich lang und kann hier oder im Buch von Jon Kleinberg und Eva Tardos gefunden werden (siehe Quellen unten).

Algorithmus vs Realität

Die LFD- Strategie ist optimal, aber es gibt ein großes Problem. Es ist eine optimale Offline- Lösung. In der Praxis ist das Caching in der Regel ein Online- Problem. Das bedeutet, dass die Strategie nutzlos ist, da wir jetzt nicht das nächste Mal, wenn wir einen bestimmten Artikel benötigen, zur Verfügung stehen. Die anderen vier Strategien sind auch Online- Strategien. Für Online-Probleme benötigen wir einen generell anderen Ansatz.