algorithm
Toepassingen van hebzuchtige techniek

Opmerkingen

Ticketautomaat

Eerste eenvoudige voorbeeld:

U hebt een kaartjesautomaat die omwisseling in munten met waarden 1, 2, 5, 10 en 20 geeft. De verdeling van de omwisseling kan worden gezien als een reeks muntdalingen totdat de juiste waarde is uitgegeven. We zeggen dat een verzending optimaal is als het aantal munten minimaal is voor zijn waarde.

Laat M in [1,50] de prijs zijn voor het ticket T en P in [1,50] het geld dat iemand voor T heeft betaald, met P >= M Laat D=PM . We definiëren het voordeel van een stap als het verschil tussen D en Dc met c de munt die de automaat in deze stap afgeeft.

De hebzuchtige techniek voor de uitwisseling is de volgende pseudo-algoritmische aanpak:

Stap 1: geef terwijl D > 20 een munt van D > 20 af en stel D = D - 20
Stap 2: terwijl D > 10 een munt van 10 geeft en D = D - 10
Stap 3: terwijl D > 5 een munt van 5 geeft en D = D - 5
Stap 4: terwijl D > 2 een munt van 2 geeft en D = D - 2
Stap 5: terwijl D > 1 een munt van 1 geeft en D = D - 1

Nadien is de som van alle munten duidelijk gelijk aan D Het is een hebzuchtig algoritme omdat na elke stap en na elke herhaling van een stap het voordeel wordt gemaximaliseerd. We kunnen geen nieuwe munt meer uitgeven met een hoger voordeel.

Nu de ticketautomaat als programma (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;
}

Houd er rekening mee dat er nu invoercontrole is om het voorbeeld eenvoudig te houden. Een voorbeelduitvoer:

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

Zolang 1 in de muntwaarden staat, weten we nu dat het algoritme wordt beëindigd, omdat:

• D strikt af met elke stap
• D is nooit >0 en kleiner dan tegelijkertijd de kleinste munt 1

Maar het algoritme heeft twee valkuilen:

1. Laat C de grootste muntwaarde zijn. De looptijd is alleen polynoom zolang D/C polynoom is, omdat de weergave van D alleen log D bits gebruikt en de looptijd ten minste lineair is in D/C
2. Bij elke stap kiest ons algoritme het lokale optimum. Maar dit is niet voldoende om te zeggen dat het algoritme de globale optimale oplossing (zie voor meer informatie vindt hier of in het Boek van Korte en Vygen ).

Een eenvoudig tegenvoorbeeld: de munten zijn 1,3,4 en D=6 . De optimale oplossing is duidelijk twee munten van waarde 3 maar hebzuchtig kiest 4 in de eerste stap, dus moet het 1 kiezen in stap twee en drie. Het geeft dus geen optimale oplossing. Een mogelijk optimaal algoritme voor dit voorbeeld is gebaseerd op dynamisch programmeren .

Intervalplanning

We hebben een aantal taken J={a,b,c,d,e,f,g} . Laat j in J een baan zijn dan zijn start bij sj en eindigt op fj . Twee taken zijn compatibel als ze elkaar niet overlappen. Een foto als voorbeeld: Het doel is om de maximale subset van onderling compatibele taken te vinden . Er zijn verschillende hebzuchtige benaderingen voor dit probleem:

1. Vroegste starttijd : overweeg banen in oplopende volgorde van sj
2. Vroegste eindtijd : overweeg taken in oplopende volgorde van fj
3. Kortste interval : overweeg taken in oplopende volgorde van fj-sj
4. Minste conflicten : tel voor elke taak j het aantal conflicterende taken cj

De vraag is nu welke aanpak echt succesvol is. Vroege starttijd zeker niet, hier is een tegenvoorbeeld Het kortste interval is ook niet optimaal en de minste conflicten klinken inderdaad optimaal, maar hier is een probleemgeval voor deze aanpak: Dat laat ons met de vroegste eindtijd . De pseudocode is stil, eenvoudig:

1. Sorteer taken op eindtijd zodat f1<=f2<=...<=fn
2. Laat A een lege set zijn
3. voor j=1 tot n als j compatibel is met alle taken in A set A=A+{j}
4. A is een maximale subset van onderling compatibele taken

Of als C ++ programma:

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

De output voor dit voorbeeld is: Compatible: (1,3) (4,5) (6,8) (9,10)

De implementatie van het algoritme staat duidelijk in Θ (n ^ 2). Er is een Θ (n log n) -implementatie en de geïnteresseerde lezer kan hieronder verder lezen (Java-voorbeeld).

Nu hebben we een hebzuchtig algoritme voor het intervalplanningsprobleem, maar is het optimaal?

Stelling: de hebzuchtige vroegste eindtijd van het algoritme is optimaal.

Bewijs: (tegenstrijdigheid)

Stel dat hebzucht niet optimaal is en i1,i2,...,ik duid de reeks taken aan die door hebzucht zijn geselecteerd. Laat j1,j2,...,jm de set taken in een optimale oplossing i1=j1,i2=j2,...,ir=jr met i1=j1,i2=j2,...,ir=jr voor de grootst mogelijke waarde van r .

De taak i(r+1) bestaat en eindigt voor j(r+1) (vroegste afwerking). Maar dan is j1,j2,...,jr,i(r+1),j(r+2),...,jm ook een optimale oplossing en voor alle k in [1,(r+1)] is jk=ik . dat is een tegenspraak met de maximaliteit van r . Hiermee is het bewijs afgesloten.

Dit tweede voorbeeld toont aan dat er meestal veel mogelijke hebzuchtige strategieën zijn, maar dat slechts enkele of zelfs geen in alle gevallen de optimale oplossing kunnen vinden.

Hieronder staat een Java-programma dat wordt uitgevoerd in Θ (n log n)

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

En de verwachte output is:

Optimal profit is 250

Latentie minimaliseren

Er zijn tal van problemen die latentie minimaliseren, hier hebben we een enkele bron die slechts één taak tegelijk kan verwerken. Taak j vereist tj verwerkingseenheden en is verschuldigd op tijdstip dj . als j begint op tijdstip sj zal het eindigen op tijdstip fj=sj+tj . We definiëren latentie L=max{0,fj-dh} voor alle j . Het doel is om de maximale latentie L te minimaliseren.

De oplossing L=7 is duidelijk niet optimaal. Laten we eens kijken naar enkele hebzuchtige strategieën:

1. Kortste verwerkingstijd eerst : taken plannen in oplopende volgorde of verwerkingstijd j`
2. Vroegste deadline eerst : taken plannen in oplopende volgorde van deadline dj
3. Kleinste speling : taken plannen in oplopende volgorde van speling dj-tj

Het is gemakkelijk om te zien dat de kortste verwerkingstijd eerst niet optimaal is, een goed tegenvoorbeeld is

de kleinste stapeloplossing heeft soortgelijke problemen

de laatste strategie lijkt geldig, dus we beginnen met een pseudo-code:

1. Sorteer n opdrachten op tijd zodat d1<=d2<=...<=dn
2. Stel t=0
3. voor j=1 tot n
   • Wijs taak j aan interval [t,t+tj]
   • stel sj=t en fj=t+tj
   • stel t=t+tj
4. retourintervallen [s1,f1],[s2,f2],...,[sn,fn]

En als implementatie 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;
}

En de output voor dit programma is:

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

De looptijd van het algoritme is duidelijk Θ (n log n) omdat sorteren de dominante werking van dit algoritme is. Nu moeten we laten zien dat het optimaal is. Het is duidelijk dat een optimaal schema geen inactieve tijd heeft . het vroegste deadline eerste schema heeft ook geen inactieve tijd.

Laten we aannemen dat de taken zijn genummerd zodat d1<=d2<=...<=dn . We zeggen dat een inversie van een schema een paar taken i en j zodat i<j maar j vóór i is gepland. Vanwege de definitie heeft het schema voor de eerste deadline geen inversies. Natuurlijk, als een schema een inversie heeft, heeft het er een met een paar omgekeerde taken die opeenvolgend zijn gepland.

Stelling: het verwisselen van twee aangrenzende, omgekeerde taken vermindert het aantal inversies met één en verhoogt niet de maximale latentie.

Bewijs: Laat L de latentie zijn voor de swap en M de latentie daarna. Omdat het uitwisselen van twee aangrenzende taken de andere taken niet van hun positie verplaatst, is het Lk=Mk voor alle k != i,j .

Het is duidelijk dat Mi<=Li sinds de taak die i eerder had gepland. als taak j laat is, volgt dit uit de definitie:

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

Dat betekent dat de latentie na swap minder of gelijk is dan voorheen. Hiermee is het bewijs afgesloten.

Stelling: Het vroegste deadline eerste schema S is optimaal.

Bewijs: (tegenstrijdigheid)

Laten we aannemen dat S* een optimaal schema is met het kleinst mogelijke aantal inversies. we kunnen aannemen dat S* geen tijd heeft om niets te doen. Als S* geen inversies heeft, dan is S=S* en zijn we klaar. Als S* een inversie heeft, dan heeft het een aangrenzende inversie. De laatste propositie stelt dat we de aangrenzende inversie kunnen verwisselen zonder de latentie te vergroten, maar met het verminderen van het aantal inversies. Dit is in tegenspraak met de definitie van S* .

Het minimaliserende latentieprobleem en het daarmee verband houdende minimale makespanprobleem , waarbij de vraag voor een minimaal schema wordt gesteld, heeft veel toepassingen in de echte wereld. Maar meestal hebt u niet slechts één machine, maar veel en deze voeren dezelfde taak uit met verschillende snelheden. Deze problemen zorgen ervoor dat NP-voltooiing echt snel wordt.

Een andere interessante vraag rijst als we niet kijken naar het offline probleem, waar we alle taken en gegevens bij de hand hebben, maar naar de online variant, waar taken verschijnen tijdens de uitvoering.

Offline caching

Het cachingprobleem ontstaat door de beperking van eindige ruimte. Laten we aannemen dat onze cache C k pagina's heeft. Nu willen we een reeks m itemverzoeken verwerken die in de cache moeten zijn geplaatst voordat ze worden verwerkt. Natuurlijk, als m<=k dan zetten we gewoon alle elementen in de cache en het zal werken, maar meestal is m>>k .

We zeggen dat een verzoek een hit in de cache is, wanneer het item al in de cache staat, anders wordt het een cache-misser genoemd . In dat geval moeten we het gevraagde item in de cache plaatsen en een ander uitzetten, ervan uitgaande dat de cache vol is. Het doel is een uitzettingsschema dat het aantal uitzettingen minimaliseert .

Er zijn tal van hebzuchtige strategieën voor dit probleem, laten we eens kijken naar enkele:

1. First in, first out (FIFO) : de oudste pagina wordt uitgezet
2. Last in, first out (LIFO) : de nieuwste pagina wordt uitgezet
3. Last recent out (LRU) : ontruimingspagina waarvan de meest recente toegang het vroegst was
4. Minst frequent aangevraagde (LFU) : ontruimingspagina die het minst vaak werd aangevraagd
5. Langste voorwaartse afstand (LFD) : verwijder de pagina in de cache die pas in de toekomst wordt aangevraagd.

Let op: voor de volgende voorbeelden verwijderen we de pagina met de kleinste index, als er meer dan één pagina kan worden verwijderd.

Voorbeeld (FIFO)

Laat de cachegrootte k=3 de initiële cache a,b,c en het verzoek a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Dertien cache mist met zestien aanvragen klinkt niet erg optimaal, laten we hetzelfde voorbeeld proberen met een andere strategie:

Voorbeeld (LFD)

Laat de cachegrootte k=3 de initiële cache a,b,c en het verzoek a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Acht cache-missers zijn een stuk beter.

Zelftest : doe het voorbeeld voor LIFO, LFU, RFU en kijk wat er is gebeurd.

Het volgende voorbeeldprogramma (geschreven in C ++) bestaat uit twee delen:

Het skelet is een applicatie die het probleem oplost afhankelijk van de gekozen hebzuchtige strategie:

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

Het basisidee is eenvoudig: voor elk verzoek heb ik twee aanroepen twee mijn strategie:

1. Toepassen : de strategie moet de beller vertellen welke pagina hij moet gebruiken
2. update : nadat de beller de plaats heeft gebruikt, vertelt deze de strategie of deze een misser was of niet. Dan kan de strategie zijn interne gegevens bijwerken. De strategie LFU moet bijvoorbeeld de hitfrequentie voor de cachepagina 's bijwerken, terwijl de LFD- strategie de afstanden voor de cachepagina's moet herberekenen.

Laten we nu eens kijken naar voorbeeldimplementaties voor onze vijf strategieën:

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 heeft alleen de informatie nodig over hoe lang een pagina zich in de cache bevindt (en natuurlijk alleen ten opzichte van de andere pagina's). Dus het enige wat je moet doen is wachten op een misser en dan de pagina's maken, die niet uitgezet zijn. Voor ons voorbeeld hierboven is de programma-oplossing:

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

Dat is precies de oplossing van bovenaf.

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

De implementatie van LIFO is min of meer hetzelfde als bij FIFO, maar we verdrijven de jongste niet de oudste pagina. De programmaresultaten zijn:

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

In het geval van LRU is de strategie onafhankelijk van wat er op de cachepagina staat, het enige belang ervan is het laatste gebruik. De programmaresultaten zijn:

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 evicts de pagina toepassingen minst vaak. Dus de updatestrategie is gewoon om elke toegang te tellen. Natuurlijk wordt de telling na een misser gereset. De programmaresultaten zijn:

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

De LFD- strategie is anders dan voorheen. Het is de enige strategie die de toekomstige verzoeken voor zijn beslissing gebruikt om te verdrijven. De implementatie gebruikt de functie calcNextUse om de pagina te krijgen die het volgende gebruik het verst weg is in de toekomst. De programma-oplossing is gelijk aan de oplossing van bovenaf:

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 

De hebzuchtige strategie LFD is inderdaad de enige optimale strategie van de vijf gepresenteerde. Het bewijs is vrij lang en kan hier of in het boek van Jon Kleinberg en Eva Tardos worden gevonden (zie bronnen in opmerkingen hieronder).

Algoritme versus realiteit

De LFD- strategie is optimaal, maar er is een groot probleem. Het is een optimale offline oplossing. In de praktijk is caching meestal een online probleem, wat betekent dat de strategie nutteloos is, omdat we nu de volgende keer dat we een bepaald item nodig hebben, niet kunnen. De andere vier strategieën zijn ook online strategieën. Voor online problemen hebben we een algemeen andere aanpak nodig.