algorithm
Applicazioni della tecnica Greedy

Osservazioni

Biglietteria automatica

Primo semplice esempio:

Avete un distributore automatico di biglietti che dà lo scambio in monete con i valori 1, 2, 5, 10 e 20. La dispensa dello scambio può essere vista come una serie di gettoni finché non viene erogato il giusto valore. Diciamo che una dispensa è ottimale quando il suo conteggio delle monete è minimo per il suo valore.

Sia M in [1,50] il prezzo per il biglietto T e P in [1,50] il denaro che qualcuno ha pagato per T , con P >= M D=PM . Definiamo il vantaggio di un passo come la differenza tra D e Dc con c la moneta che l'erogatore automatico distribuisce in questo passaggio.

La tecnica greedy per lo scambio è il seguente approccio pseudo-algoritmico:

Passaggio 1: mentre D > 20 erogare una moneta da 20 e impostare D = D - 20
Passaggio 2: mentre D > 10 erogare una moneta da 10 e impostare D = D - 10
Passaggio 3: mentre D > 5 eroga una moneta da 5 e imposta D = D - 5
Passaggio 4: mentre D > 2 erogare una moneta 2 e impostare D = D - 2
Passaggio 5: mentre D > 1 erogare una moneta da 1 e impostare D = D - 1

Successivamente la somma di tutte le monete è chiaramente uguale a D È un algoritmo avido perché dopo ogni passo e dopo ogni ripetizione di un passo il vantaggio viene massimizzato. Non possiamo dispensare un'altra moneta con un beneficio maggiore.

Ora il biglietto automatico come 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;
}

Si noti che ora è in corso il controllo dell'input per mantenere l'esempio semplice. Un esempio di output:

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

Finché 1 è nei valori della moneta, ora che l'algoritmo terminerà, perché:

• D diminuisce rigorosamente ad ogni passo
• D non è mai >0 e più piccolo della moneta più piccola 1 allo stesso tempo

Ma l'algoritmo ha due problemi:

1. Sia C il valore più grande delle monete. Il runtime è solo polinomiale fintanto che D/C è polinomiale, poiché la rappresentazione di D utilizza solo i bit di log D e il runtime è almeno lineare in D/C
2. In ogni passo il nostro algoritmo sceglie l'optimum locale. Ma questo non è sufficiente per dire che l'algoritmo trova la soluzione ottimale globale (vedi più informazioni qui o nel Libro di Korte e Vygen ).

Un semplice esempio di contatore: le monete sono 1,3,4 e D=6 . La soluzione ottimale è chiaramente due monete del valore 3 ma avido sceglie 4 nel primo passo, quindi deve scegliere 1 al secondo e al terzo passaggio. Quindi non dà una scelta ottimale. Un possibile Algoritmo ottimale per questo esempio si basa sulla programmazione dinamica .

Programmazione a intervalli

Abbiamo un insieme di lavori J={a,b,c,d,e,f,g} . Sia j in J un lavoro che il suo inizio in sj e termina in fj . Due lavori sono compatibili se non si sovrappongono. Una foto come esempio: L'obiettivo è trovare il sottoinsieme massimo di lavori reciprocamente compatibili . Ci sono molti approcci avidi per questo problema:

1. Prima ora di inizio : considera i lavori in ordine ascendente di sj
2. Primo tempo di finitura : considera i lavori in ordine ascendente di fj
3. Intervallo più breve : considera i lavori in ordine ascendente di fj-sj
4. Conflitti minimi : per ogni lavoro j , conta il numero di lavori in conflitto cj

La domanda ora è, quale approccio ha davvero successo. L'orario di inizio precoce non è definitivo, ecco un esempio contrario Anche l'intervallo più breve non è ottimale e il minor numero di conflitti può effettivamente sembrare ottimale, ma qui c'è un problema per questo approccio: Il che ci lascia con il primo tempo di finitura . Lo pseudo codice è semplice e tranquillo:

1. Ordina i lavori per ora di fine in modo che f1<=f2<=...<=fn
2. Sia A un set vuoto
3. per j=1 a n se j è compatibile con tutti i lavori in A set A=A+{j}
4. A è un sottoinsieme massimo di lavori reciprocamente compatibili

O come programma C ++:

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

const int jobCnt = 10;

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

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

using namespace std;

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

L'output per questo esempio è: Compatible: (1,3) (4,5) (6,8) (9,10)

L'implementazione dell'algoritmo è chiaramente in Θ (n ^ 2). Esiste un'implementazione Θ (n log n) e il lettore interessato può continuare a leggere qui sotto (Esempio Java).

Ora abbiamo un algoritmo avido per il problema della schedulazione degli intervalli, ma è ottimale?

Proposizione: l'algoritmo goloso è il primo momento di fine è ottimale.

Dimostrazione: (per contraddizione)

Assumere avidi non è ottimale e i1,i2,...,ik denotano l'insieme di lavori selezionati da golosi. Sia j1,j2,...,jm denotano l'insieme di lavori in una soluzione ottimale con i1=j1,i2=j2,...,ir=jr per il valore più grande possibile di r .

Il lavoro i(r+1) esiste e termina prima di j(r+1) (primo aggiornamento). Ma rispetto a j1,j2,...,jr,i(r+1),j(r+2),...,jm anche una soluzione ottimale e per tutti i k in [1,(r+1)] è jk=ik . questa è una contraddizione alla massima di r . Questo conclude la dimostrazione.

Questo secondo esempio dimostra che di solito ci sono molte possibili strategie golose, ma solo alcune o addirittura nessuna potrebbe trovare la soluzione ottimale in ogni caso.

Di seguito è riportato un programma Java eseguito 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));
    }
}

E l'output atteso è:

Optimal profit is 250

Riduzione al minimo del ritardo

Ci sono numerosi problemi che riducono al minimo il ritardo, qui abbiamo una singola risorsa che può elaborare solo un lavoro alla volta. Il lavoro j richiede tj unità di tempo di elaborazione ed è dovuto al momento dj . se j inizia al momento sj finirà al tempo fj=sj+tj . Definiamo il ritardo L=max{0,fj-dh} per tutti i j . L'obiettivo è ridurre al minimo il ritardo massimo

La soluzione L=7 è ovviamente ottimale. Diamo un'occhiata ad alcune strategie golose:

1. Tempo di elaborazione minimo prima : pianificare i lavori in ordine ascendente e tempo di elaborazione j`
2. Prima la prima scadenza : pianifica i lavori in ordine crescente di scadenza dj
3. Il più piccolo allentamento : pianificare i lavori in ordine crescente di dj-tj allentato

È facile vedere che il tempo di elaborazione più breve non è ottimale, ad esempio un buon esempio di contatore

la soluzione di stack più piccola ha problemi simillari

l'ultima strategia sembra valida, quindi iniziamo con qualche pseudo codice:

1. Ordina n lavori per tempo in modo che d1<=d2<=...<=dn
2. Imposta t=0
3. per j=1 a n
   • Assegna il lavoro j all'intervallo [t,t+tj]
   • imposta sj=t e fj=t+tj
   • imposta t=t+tj
4. intervalli di ritorno [s1,f1],[s2,f2],...,[sn,fn]

E come implementazione 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;
}

E l'output per questo programma è:

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

Il runtime dell'algoritmo è ovviamente Θ (n log n) perché l'ordinamento è l'operazione dominante di questo algoritmo. Ora dobbiamo dimostrare che è ottimale. Chiaramente, un programma ottimale non ha tempi morti . anche la prima scadenza del primo termine non ha tempi di inattività.

Supponiamo che i lavori siano numerati in modo che d1<=d2<=...<=dn . Diciamo che l' inversione di un programma è una coppia di lavori i e j modo che i<j ma j sia pianificato prima di i . A causa della sua definizione, la prima scadenza del primo periodo non ha inversioni. Naturalmente se un programma ha una inversione ne ha uno con una coppia di lavori invertiti programmati consecutivamente.

Proposizione: lo scambio di due lavori adiacenti e invertiti riduce il numero di inversioni di uno e non aumenta il ritardo massimo.

Dimostrazione: Sia L il ritardo prima dello swap e M il ritardo dopo. Poiché lo scambio di due lavori adiacenti non sposta gli altri lavori dalla loro posizione, è Lk=Mk per tutti i k != i,j .

Chiaramente è Mi<=Li dal lavoro che i programmato in precedenza. se il lavoro j è in ritardo, così segue dalla definizione:

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

Ciò significa che il ritardo dopo lo scambio è inferiore o uguale a prima. Questo conclude la dimostrazione.

Proposizione: la prima scadenza prima S è ottimale.

Dimostrazione: (per contraddizione)

Supponiamo che S* sia la pianificazione ottimale con il minor numero possibile di inversioni. possiamo supporre che S* non abbia tempo di inattività. Se S* non ha inversioni, allora S=S* e abbiamo finito. Se S* ha una inversione, allora ha un'inversione adiacente. L'ultima proposizione afferma che possiamo scambiare l'inversione adiacente senza aumentare il ritardo ma con la diminuzione del numero di inversioni. Questo contraddice la definizione di S* .

Il minimizzare il problema di latenza e il suo problema di makepan minimo correlato, in cui viene posta la domanda per un programma minimo, hanno molte applicazioni nel mondo reale. Ma di solito non hai una sola macchina ma molte e gestiscono lo stesso compito a ritmi diversi. Questi problemi rendono NP-completo davvero veloce.

Un'altra domanda interessante sorge se non guardiamo al problema offline , dove abbiamo tutte le attività e i dati a portata di mano, ma nella variante online , dove le attività compaiono durante l'esecuzione.

Memorizzazione nella cache offline

Il problema del caching deriva dalla limitazione dello spazio finito. Supponiamo che la nostra cache C abbia pagine k . Ora vogliamo elaborare una sequenza di richieste di oggetti m che devono essere state inserite nella cache prima che vengano elaborate. Naturalmente se m<=k allora inseriamo tutti gli elementi nella cache e funzionerà, ma di solito è m>>k .

Diciamo che una richiesta è un colpo di cache , quando l'elemento è già in cache, altrimenti è chiamato " cache miss" . In tal caso dobbiamo portare l'elemento richiesto nella cache e sfrattarne un altro, supponendo che la cache sia piena. L'obiettivo è un programma di sfratto che riduce al minimo il numero di sfratti .

Ci sono numerose strategie golose per questo problema, vediamo alcune:

1. First in, first out (FIFO) : la pagina più vecchia viene sfrattata
2. Last in, first out (LIFO) : la pagina più recente viene sfrattata
3. Ultima uscita recente (LRU) : pagina Evict il cui accesso più recente è stato il più recente
4. Meno frequentemente richiesto (LFU) : Evita la pagina che è stata richiesta meno frequentemente
5. Distanza di inoltro più lunga (LFD) : Evita la pagina nella cache che non è richiesta fino al più lontano in futuro.

Attenzione: per gli esempi seguenti eliminiamo la pagina con l'indice più piccolo, se più di una pagina può essere sfrattata.

Esempio (FIFO)

Lascia che la dimensione della cache sia k=3 la cache iniziale a,b,c e la richiesta a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Tredici mancanze della cache di sedici richieste non sembrano molto ottimali, proviamo lo stesso esempio con un'altra strategia:

Esempio (LFD)

Lascia che la dimensione della cache sia k=3 la cache iniziale a,b,c e la richiesta a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Otto errori nella cache sono molto meglio.

Selftest : fai l'esempio per LIFO, LFU, RFU e guarda cosa succede.

Il seguente programma di esempio (scritto in C ++) è composto da due parti:

Lo scheletro è un'applicazione che risolve il problema in base alla strategia avida scelta:

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

L'idea di base è semplice: per ogni richiesta ho due chiamate due la mia strategia:

1. apply : la strategia deve dire al chiamante quale pagina usare
2. aggiornamento : dopo che il chiamante utilizza il luogo, indica alla strategia se si tratta di un errore o meno. Quindi la strategia può aggiornare i suoi dati interni. La strategia LFU, per esempio, deve aggiornare la frequenza dei colpi per le pagine della cache, mentre la strategia LFD deve ricalcolare le distanze per le pagine della cache.

Ora vediamo le implementazioni di esempio per le nostre cinque strategie:

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 ha solo bisogno di informazioni per quanto tempo una pagina è nella cache (e ovviamente solo rispetto alle altre pagine). Quindi l'unica cosa da fare è aspettare una miss e poi fare le pagine, che non vengono sfrattate più vecchie. Per il nostro esempio sopra la soluzione del programma è:

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

Questa è la soluzione esatta da sopra.

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

L'implementazione di LIFO è più o meno la stessa della FIFO, ma eliminiamo la pagina più giovane e non la più vecchia. I risultati del programma sono:

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 caso di LRU la strategia è indipendente da ciò che è nella pagina della cache, il suo unico interesse è l'ultimo utilizzo. I risultati del programma sono:

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 sfrutta la pagina meno frequentemente. Quindi la strategia di aggiornamento è solo per contare ogni accesso. Ovviamente dopo un errore il conteggio si azzera. I risultati del programma sono:

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

La strategia LFD è diversa da tutti prima. È l'unica strategia che utilizza le future richieste per la sua decisione di espellere. L'implementazione utilizza la funzione calcNextUse per ottenere la pagina che il prossimo utilizzo sarà più lontano in futuro. La soluzione del programma è uguale alla soluzione a mano dall'alto:

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 

La strategia golosa LFD è infatti l'unica strategia ottimale dei cinque presentati. La dimostrazione è piuttosto lunga e può essere trovata qui o nel libro di Jon Kleinberg e Eva Tardos (vedi fonti nelle osservazioni in basso).

Algoritmo vs realtà

La strategia LFD è ottimale, ma c'è un grosso problema. È una soluzione offline ottimale. In Praxis il caching è di solito un problema online , il che significa che la strategia è inutile perché non possiamo ora la prossima volta che abbiamo bisogno di un particolare oggetto. Le altre quattro strategie sono anche strategie online . Per i problemi online abbiamo bisogno di un approccio generale diverso.