algorithm
Tillämpningar av girig teknik

Anmärkningar

Biljett automat

Första enkla exempel:

Du har en biljettautomat som ger utbyte i mynt med värden 1, 2, 5, 10 och 20. Utdelningen av utbytet kan ses som en serie av mynt sjunker tills rätt värde är utdelat. Vi säger att en dispens är optimal när dess mynträkning är minimal för dess värde.

Låt M i [1,50] vara priset för biljetten T och P i [1,50] pengarna som någon betalade för T , med P >= M Låt D=PM . Vi definierar fördelen med ett steg som skillnaden mellan D och Dc med c det mynt som automaten fördelar i detta steg.

Den giriga tekniken för utbytet är följande pseudo-algoritmisk strategi:

Steg 1: medan D > 20 fördelar ett 20 mynt och ställ in D = D - 20
Steg 2: medan D > 10 fördelar ett 10 mynt och ställ in D = D - 10
Steg 3: medan D > 5 fördelar ett 5 mynt och ställ in D = D - 5
Steg 4: medan D > 2 fördelar ett 2-mynt och ställ in D = D - 2
Steg 5: medan D > 1 fördelar ett 1-mynt och ställ in D = D - 1

Därefter är summan av alla mynt tydligt lika med D Det är en girig algoritm eftersom fördelarna maximeras efter varje steg och efter varje repitition av ett steg. Vi kan inte fördela ett annat mynt med en högre fördel.

Nu biljettautomaten som program (i 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;
}

Var medveten om att det nu är ingångskontroll för att göra exemplet enkelt. Ett exempel på utgången:

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

Så länge 1 är i myntvärdena nu, kommer algoritmen att avslutas, eftersom:

• D minskar strikt med varje steg
• D är aldrig >0 och mindre än än det minsta myntet 1 samtidigt

Men algoritmen har två fallgropar:

1. Låt C vara det största myntvärdet. Drifttiden är endast polynom så länge som D/C är polynom, eftersom representationen av D använder endast log D bitar och körtiden är åtminstone linjär i D/C
2. I varje steg väljer vår algoritm det lokala optimumet. Men detta är inte tillräckligt för att säga att algoritmen hittar den globala optimala lösningen (se mer information här eller i Book of Korte och Vygen ).

Ett enkelt motexempel: mynten är 1,3,4 och D=6 . Den optimala lösningen är helt klart två mynt med värde 3 men giriga väljer 4 i det första steget så det måste välja 1 i steg två och tre. Så det ger ingen optimal soution. En möjlig optimal algoritm för detta exempel är baserad på dynamisk programmering .

Intervallplanering

Vi har en uppsättning jobb J={a,b,c,d,e,f,g} . Låt j in J vara ett jobb än det börjar på sj och slutar vid fj . Två jobb är kompatibla om de inte överlappar varandra. En bild som exempel: Målet är att hitta den maximala undergruppen av ömsesidigt kompatibla jobb . Det finns flera giriga metoder för detta problem:

1. Tidigaste starttid : Överväga jobb i stigande ordning på sj
2. Tidigaste sluttid : Överväga jobb i stigande ordning på fj
3. Kortaste intervall : Tänk på jobb i stigande ordning på fj-sj
4. Minsta konflikter : För varje jobb j , räkna antalet motstridiga jobb cj

Frågan är nu, vilken strategi som verkligen är framgångsrik. Tidig starttid definitivt inte, här är ett motexempel Det kortaste intervallet är inte heller optimalt och få konflikter kanske verkligen låter optimalt, men här är ett problemfall för denna strategi: Det ger oss den tidigaste sluttiden . Pseudokoden är tyst enkel:

1. Sortera jobb efter sluttid så att f1<=f2<=...<=fn
2. Låt A vara en tom uppsättning
3. för j=1 till n om j är kompatibel med alla jobb i A set A=A+{j}
4. A är en maximal undergrupp av ömsesidigt kompatibla jobb

Eller som C ++ -program:

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

Utgången för detta exempel är: Compatible: (1,3) (4,5) (6,8) (9,10)

Implementeringen av algoritmen är tydligt i Θ (n ^ 2). Det finns en implementation (n log n) implementering och den intresserade läsaren kan fortsätta läsa nedan (Java-exempel).

Nu har vi en girig algoritm för intervallschemaläggningsproblemet, men är det optimalt?

Förslag: Den giriga algoritmen tidigaste sluttid är optimal.

Bevis: (motsägelse)

Anta att girig är inte optimal och i1,i2,...,ik betecknar den uppsättning jobb som valts av giriga. Låt j1,j2,...,jm beteckna uppsättningen av jobb i en optimal lösning med i1=j1,i2=j2,...,ir=jr för största möjliga värde på r .

Jobbet i(r+1) finns och avslutas innan j(r+1) (tidigaste finish). Men än är j1,j2,...,jr,i(r+1),j(r+2),...,jm också en optimal lösning och för alla k i [1,(r+1)] är jk=ik . det är en motsägelse till det maximala av r . Detta avslutar beviset.

Detta andra exempel visar att det vanligtvis finns många möjliga giriga strategier, men bara några eller till och med ingen kan hitta den optimala lösningen i alla fall.

Nedan är ett Java-program som körs i Θ (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));
    }
}

Och den förväntade produktionen är:

Optimal profit is 250

Minimera latens

Det finns många problem som minimerar latensen, här har vi en enda resurs som bara kan behandla ett jobb åt gången. Jobb j kräver tj enheter för behandlingstid och beror på dj . om j börjar vid tidpunkten sj slutar den vid tiden fj=sj+tj . Vi definierar latens L=max{0,fj-dh} för alla j . Målet är att minimera maximal latens L.

Lösningen L=7 är uppenbarligen inte optimal. Låt oss titta på några giriga strategier:

1. Kortaste behandlingstid först : schemalägga jobb i stigande ordning och behandlingstid j`
2. Tidigast deadline först : Schemalägga jobb i stigande ordning med deadline dj
3. Minsta slack : schema jobb i stigande ordning av slack dj-tj

Det är lätt att se att den kortaste behandlingstiden först inte är optimal, ett bra motexempel är

den minsta stacklösningen har problem med samma sidor

den sista strategin ser giltig ut så vi börjar med någon pseudokod:

1. Sortera n jobb efter tid så att d1<=d2<=...<=dn
2. Ställ in t=0
3. för j=1 till n
   • Tilldela jobb j till intervallet [t,t+tj]
   • ställa in sj=t och fj=t+tj
   • ställa in t=t+tj
4. returintervall [s1,f1],[s2,f2],...,[sn,fn]

Och som implementering i 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;
}

Och utgången för detta program är:

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

Algoritmens körtid är uppenbarligen Θ (n log n) eftersom sortering är den dominerande funktionen för denna algoritm. Nu måste vi visa att det är optimalt. Det är uppenbart att ett optimalt schema inte har vilotid . den tidigaste tidsfristen första schemat har inte heller någon vilotid.

Låt oss anta att jobben är numrerade så att d1<=d2<=...<=dn . Vi säger att en inversion av ett schema är ett par jobb i och j så att i<j men j är planerat före i . På grund av sin definition har den första tidsfristen första schemat inga inversioner. Naturligtvis om ett schema har en inversion har den en med ett par inverterade jobb schemalagda i följd.

Förslag: Att byta två intilliggande, inverterade jobb minskar antalet inversioner med en och ökar inte den maximala latensen.

Bevis: Låt L vara fördröjningen innan bytet och M förseningen efteråt. Eftersom utbyte av två angränsande jobb inte flyttar de andra jobben från sin position är det Lk=Mk för alla k != i,j .

Det är uppenbart att det är Mi<=Li sedan i jobbade tidigare. om jobb j är sent följer så definitionen:

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

Det betyder att latensen efter swap är mindre eller lika mycket än tidigare. Detta avslutar beviset.

Förslag: Den tidigaste tidsfristen första schema S är optimal.

Bevis: (motsägelse)

Låt oss anta att S* är ett optimalt schema med minsta möjliga antal inversioner. vi kan anta att S* har någon vilotid. Om S* har några inversioner, så är S=S* och vi är klara. Om S* har en inversion, än den har en intilliggande inversion. Det sista förslaget säger att vi kan byta den intilliggande inversionen utan att öka latensen men med att minska antalet inversioner. Detta strider mot definitionen av S* .

Problemet med att minimera fördröjningen och det nära relaterade minimiproblemet , där frågan om ett minimalt schema ställs har många applikationer i den verkliga världen. Men vanligtvis har du inte bara en maskin utan många och de hanterar samma uppgift i olika hastigheter. Dessa problem blir NP-komplett riktigt snabbt.

En annan intressant fråga uppstår om vi inte tittar på offlineproblemet , där vi har alla uppgifter och data till hands men på onlinevarianten , där uppgifter visas under körning.

Offline-caching

Cacheproblemet beror på begränsningen av det begränsade utrymmet. Låt oss anta att vår cache C har k sidor. Nu vill vi behandla en sekvens av m artikelförfrågningar som måste ha placerats i cachen innan de behandlas. Naturligtvis om m<=k så lägger vi bara alla element i cachen och det kommer att fungera, men brukar vara m>>k .

Vi säger att en begäran är en cache-hit , när objektet redan är i cache, annars kallas det en cache-miss . I så fall måste vi ta med den begärda artikeln i cache och släppa ut en annan, förutsatt att cachen är full. Målet är ett evictionschema som minimerar antalet utkastningar .

Det finns många giriga strategier för detta problem, låt oss titta på några:

1. Först in, först ut (FIFO) : Den äldsta sidan släpps
2. Senast in, först ut (LIFO) : Den senaste sidan släpps ut
3. Senaste senaste ut (LRU) : Evict-sida vars senaste åtkomst var tidigast
4. Minst ofta begärda (LFU) : Avvisa den sida som minst begärdes
5. Längsta framsträcka (LFD) : Avlägsna sidan i cachen som inte begärs förrän längst framöver.

Uppmärksamhet: För följande exempel släpper vi sidan med det minsta indexet, om mer än en sida skulle kunna kastas ut.

Exempel (FIFO)

Låt cachestorleken vara k=3 den initiala cachen a,b,c och begäran a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Tretton cachemissar av sexton förfrågningar låter inte särskilt optimalt, låt oss prova samma exempel med en annan strategi:

Exempel (LFD)

Låt cachestorleken vara k=3 den initiala cachen a,b,c och begäran a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Åtta cachemissar är mycket bättre.

Självtest : Gör exemplet för LIFO, LFU, RFU och se vad som händer.

Följande exempelprogram (skrivet i C ++) består av två delar:

Skelettet är en applikation som löser problemet beroende på den valda giriga strategin:

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

Grundidén är enkel: för varje förfrågan har jag två samtal två min strategi:

1. tillämpas : Strategin måste berätta den som ringer vilken sida som ska användas
2. uppdatering : När den som ringer använder platsen berättar strategin om det var en miss eller inte. Då kan strategin uppdatera sina interna data. Strategin LFU måste till exempel uppdatera hitfrekvensen för cachesidorna , medan LFD- strategin måste beräkna om avstånden för cachesidorna.

Låt oss nu titta på exempelimplementeringar för våra fem strategier:

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 behöver bara informationen hur länge en sida är i cachen (och naturligtvis endast i förhållande till de andra sidorna). Så det enda man kan göra är att vänta på en miss och sedan göra sidorna, där de inte kastas ut äldre. För vårt exempel ovan är programlösningen:

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

Det är exakt lösningen ovanifrån.

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

Implementeringen av LIFO är mer eller mindre densamma som av FIFO men vi kastar ut den yngsta inte den äldsta sidan. Programresultaten är:

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

I fallet med LRU är strategin oberoende av vad som finns på cachesidan, dess enda intresse är den senaste användningen. Programresultaten är:

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 undviker att sidan används minst ofta. Så uppdateringsstrategin är bara att räkna varje åtkomst. Naturligtvis efter en miss återställs räkningen. Programresultaten är:

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- strategin skiljer sig från alla tidigare. Det är den enda strategin som använder de framtida förfrågningarna om dess beslut vem som ska avvisa. Implementeringen använder funktionen calcNextUse att få den sida som nästa användning är längst bort i framtiden. Programlösningen är lika med lösningen för hand ovanifrån:

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 

Den giriga strategin LFD är verkligen den enda optimala strategin av de fem som presenteras. Beviset är ganska långt och kan hittas här eller i boken av Jon Kleinberg och Eva Tardos (se källor i kommentarer nedan).

Algoritm vs verklighet

LFD- strategin är optimal, men det finns ett stort problem. Det är en optimal offline- lösning. I praxis är caching vanligtvis ett online- problem, det betyder att strategin är värdelös eftersom vi inte kan nu nästa gång vi behöver en viss artikel. De andra fyra strategierna är också onlinestrategier . För online-problem behöver vi ett allmänt annorlunda tillvägagångssätt.