algorithm
Zastosowania techniki chciwości

Uwagi

Automat biletowy

Pierwszy prosty przykład:

Masz automat biletowy, który zapewnia wymianę monet o wartościach 1, 2, 5, 10 i 20. Rozliczenie wymiany można traktować jako serię spadających monet, dopóki nie zostanie wydana odpowiednia wartość. Mówimy, że rozrzut jest optymalny, gdy jego liczba monet jest minimalna ze względu na jego wartość.

Niech M w [1,50] będzie ceną za bilet T a P w [1,50] pieniądze, które ktoś zapłacił za T , przy P >= M Niech D=PM . Definiujemy korzyść krok jako różnicę pomiędzy D i Dc z c monety dozowania automat w tym kroku.

Chciwa technika wymiany polega na następującym podejściu pseudo algorytmicznym:

Krok 1: podczas gdy D > 20 wydaje 20 monet i ustaw D = D - 20
Krok 2: podczas gdy D > 10 wydaje 10 monet i ustaw D = D - 10
Krok 3: podczas gdy D > 5 dozuje monetę 5 i ustawia D = D - 5
Krok 4: podczas gdy D > 2 wydaje 2 monety i ustaw D = D - 2
Krok 5: podczas gdy D > 1 wydaje 1 monetę i ustaw D = D - 1

Następnie suma wszystkich monet wyraźnie równa się D Jest to chciwy algorytm, ponieważ po każdym kroku i po każdej powtórzeniu kroku korzyść jest zmaksymalizowana. Nie możemy dozować kolejnej monety z wyższą korzyścią.

Teraz automat biletowy jako program (w 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;
}

Pamiętaj, że teraz sprawdzanie danych wejściowych jest proste. Jeden przykładowy wynik:

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

Tak długo, jak 1 jest w wartości monety, algorytm zostanie zakończony, ponieważ:

• D ściśle maleje z każdym krokiem
• D nigdy nie jest >0 i jest mniejsze niż najmniejsza moneta 1 jednocześnie

Ale algorytm ma dwie pułapki:

1. Niech C będzie największą wartością monety. Środowisko wykonawcze jest wielomianowe, o ile D/C jest wielomianowe, ponieważ reprezentacja D wykorzystuje tylko log D bitów, a środowisko wykonawcze jest co najmniej liniowe w D/C
2. Na każdym kroku nasz algorytm wybiera lokalne optimum. Nie wystarczy jednak powiedzieć, że algorytm znajduje globalne optymalne rozwiązanie (więcej informacji tutaj lub w Księdze Korte i Vygen ).

Prosty licznik: monety mają 1,3,4 a D=6 . Optymalnym rozwiązaniem są oczywiście dwie monety o wartości 3 ale chciwy wybiera 4 w pierwszym kroku, więc musi wybrać 1 w kroku drugim i trzecim. Więc nie daje optymalnego południe. Możliwy optymalny algorytm dla tego przykładu opiera się na programowaniu dynamicznym .

Planowanie interwałów

Mamy zestaw zadań J={a,b,c,d,e,f,g} . Niech j in J będzie pracą od początku w sj i kończy w fj . Dwa zadania są kompatybilne, jeśli się nie pokrywają. Obraz jako przykład: Celem jest znalezienie maksymalnego podzbioru wzajemnie kompatybilnych zadań . Istnieje kilka chciwych podejść do tego problemu:

1. Najwcześniejszy czas rozpoczęcia : rozważ zadania w porządku rosnącym sj
2. Najwcześniejszy czas zakończenia : rozważ zadania w porządku rosnącym od fj
3. Najkrótszy interwał : rozważ zadania w porządku rosnącym od fj-sj
4. Najmniej konfliktów : Dla każdego zadania j policz liczbę sprzecznych zadań cj

Pytanie, które podejście jest naprawdę skuteczne. Wczesny czas rozpoczęcia zdecydowanie nie, oto przeciwny przykład Najkrótszy odstęp nie jest również optymalny a najmniej konfliktów może rzeczywiście brzmieć optymalnie, ale tutaj jest problem z tym podejściem: Co pozostawia nam najwcześniejszy czas zakończenia . Pseudo kod jest cichy prosty:

1. Sortuj zadania według czasu zakończenia, aby f1<=f2<=...<=fn
2. Niech A będzie pustym zestawem
3. dla j=1 do n , gdy j jest zgodna dla wszystkich zadań w A zestaw A=A+{j}
4. A to maksymalny podzbiór wzajemnie kompatybilnych zadań

Lub jako program 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;
}

Dane wyjściowe dla tego przykładu to: Compatible: (1,3) (4,5) (6,8) (9,10)

Implementacja algorytmu jest wyraźnie w Θ (n ^ 2). Istnieje implementacja Θ (n log n), a zainteresowany czytelnik może kontynuować czytanie poniżej (przykład Java).

Teraz mamy chciwy algorytm dla problemu planowania interwałów, ale czy jest optymalny?

Twierdzenie: optymalizacja algorytmu zachłanności najwcześniej .

Dowód: (przez zaprzeczenie)

Załóżmy, że chciwość nie jest optymalna, a i1,i2,...,ik oznaczają zestaw zadań wybranych przez chciwego. Niech j1,j2,...,jm oznaczają zbiór zadań w optymalnym rozwiązaniu z i1=j1,i2=j2,...,ir=jr dla największej możliwej wartości r .

Zadanie i(r+1) istnieje i kończy się przed j(r+1) (najwcześniejsze zakończenie). Ale niż jest j1,j2,...,jr,i(r+1),j(r+2),...,jm również rozwiązaniem optymalnym i dla wszystkich k w [1,(r+1)] to jk=ik . to jest sprzeczność z maksymalnością r . To kończy dowód.

Ten drugi przykład pokazuje, że zwykle istnieje wiele możliwych chciwych strategii, ale tylko niektóre lub nawet żadne z nich mogą nie znaleźć optymalnego rozwiązania w każdym przypadku.

Poniżej znajduje się program Java działający w Θ (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));
    }
}

Oczekiwany wynik to:

Optimal profit is 250

Minimalizowanie spóźnienia

Istnieje wiele problemów minimalizujących spóźnienie, tutaj mamy jeden zasób, który może przetwarzać tylko jedno zadanie na raz. Zadanie j wymaga tj Jednostek czasu przetwarzania i jest wymagalne w czasie dj . jeśli j zaczyna się w czasie sj , kończy się w czasie fj=sj+tj . Definiujemy spóźnienie L=max{0,fj-dh} dla wszystkich j . Celem jest zminimalizowanie maksymalnej spóźnienia L.

Rozwiązanie L=7 jest oczywiście optymalne. Przyjrzyjmy się niektórym chciwym strategiom:

1. Najpierw najkrótszy czas przetwarzania : zaplanuj zadania w porządku rosnącym i czas przetwarzania j`
2. Najpierw najwcześniejszy termin : Zaplanuj zadania w porządku rosnącym od ostatecznego terminu dj
3. Najmniejszy luz : harmonogram zadań w rosnącej kolejności luzu dj-tj

Łatwo zauważyć, że najkrótszy czas przetwarzania nie jest optymalny, dobrym przykładem jest licznik

najmniejsze rozwiązanie stosu ma podobne problemy

ostatnia strategia wygląda poprawnie, więc zaczynamy od pseudo kodu:

1. Posortuj n zadań według czasu, aby d1<=d2<=...<=dn
2. Ustaw t=0
3. dla j=1 do n
   • Przypisz zadanie j do przedziału [t,t+tj]
   • ustaw sj=t fj=t+tj
   • ustaw t=t+tj
4. interwały powrotu [s1,f1],[s2,f2],...,[sn,fn]

A jako implementacja w 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;
}

Dane wyjściowe dla tego programu to:

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

Czas działania algorytmu wynosi oczywiście Θ (n log n), ponieważ sortowanie jest dominującą operacją tego algorytmu. Teraz musimy pokazać, że jest optymalny. Oczywiście optymalny harmonogram nie ma czasu bezczynności . najwcześniejszy harmonogram pierwszego terminu również nie ma czasu bezczynności.

Załóżmy, że zadania są ponumerowane, więc d1<=d2<=...<=dn . Mówimy, że odwrócenie harmonogramu jest parą zadań i i j więc i<j ale j jest zaplanowane przed i . Ze względu na swoją definicję najwcześniejszy termin pierwszego harmonogramu nie ma inwersji. Oczywiście, jeśli harmonogram ma inwersję, to ma taką z parą odwróconych zadań zaplanowanych kolejno.

Propozycja: Zamiana dwóch sąsiednich, odwróconych zadań zmniejsza liczbę inwersji o jeden i nie zwiększa maksymalnego spóźnienia.

Dowód: Niech L będzie spóźnieniem przed zamianą, a M spóźnieniem później. Ponieważ zamiana dwóch sąsiednich zadań nie przesuwa innych zadań z ich pozycji, jest to Lk=Mk dla wszystkich k != i,j .

Oczywiste jest Mi<=Li od pracy i got zaplanowane wcześniej. jeśli zadanie j się spóźnia, wynika to z definicji:

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

Oznacza to, że opóźnienie po zamianie jest mniejsze lub równe niż przedtem. To kończy dowód.

Propozycja: najwcześniejszy termin pierwszego harmonogramu S jest optymalny.

Dowód: (przez zaprzeczenie)

Załóżmy, że S* to optymalny harmonogram z najmniejszą możliwą liczbą inwersji. możemy założyć, że S* nie ma czasu bezczynności. Jeśli S* nie ma żadnych inwersji, to S=S* i gotowe. Jeśli S* ma inwersję, to ma sąsiednią inwersję. Ostatnia propozycja mówi, że możemy zamienić sąsiednią inwersję bez zwiększania spóźnienia, ale ze zmniejszaniem liczby inwersji. Jest to sprzeczne z definicją S* .

Problem minimalizacji opóźnień i związany z nim prawie minimalny problem makespan , gdzie zadawane jest pytanie o minimalny harmonogram, ma wiele zastosowań w świecie rzeczywistym. Ale zwykle nie masz tylko jednej maszyny, ale wielu, a oni wykonują to samo zadanie w różnym tempie. Te problemy naprawdę szybko się uzupełniają.

Kolejne interesujące pytanie powstaje, jeśli nie spojrzymy na problem offline , w którym mamy wszystkie zadania i dane pod ręką, ale na wariant online , w którym zadania pojawiają się podczas wykonywania.

Buforowanie offline

Problem buforowania wynika z ograniczenia skończonej przestrzeni. Załóżmy, że nasza pamięć podręczna C ma k stron. Teraz chcemy przetworzyć sekwencję żądań m pozycji, które muszą zostać umieszczone w pamięci podręcznej przed ich przetworzeniem. Oczywiście, jeśli m<=k to po prostu umieszczamy wszystkie elementy w pamięci podręcznej i będzie działać, ale zwykle jest to m>>k .

Mówimy, że żądanie jest trafieniem w pamięć podręczną , gdy element jest już w pamięci podręcznej, w przeciwnym razie jest nazywany brakiem pamięci podręcznej . W takim przypadku musimy przenieść żądany element do bufora i eksmitować inny, zakładając, że bufor jest pełny. Celem jest harmonogram eksmisji, który minimalizuje liczbę eksmisji .

Istnieje wiele chciwych strategii dla tego problemu, spójrzmy na niektóre:

1. Pierwsze weszło, pierwsze wyszło (FIFO) : najstarsza strona zostaje eksmitowana
2. Last in, first out (LIFO) : Najnowsza strona zostaje eksmitowana
3. Ostatnie ostatnie wyjście (LRU) : strona eksmisji, do której ostatni dostęp był najwcześniejszy
4. Najmniej często żądane (LFU) : strona eksmitująca, o którą najczęściej pytano
5. Najdłuższa odległość do przodu (LFD) : strona eksmisji w pamięci podręcznej, która nie jest wymagana, aż do najdalej w przyszłości.

Uwaga: W poniższych przykładach eksmitujemy stronę o najmniejszym indeksie, jeśli można eksmitować więcej niż jedną stronę.

Przykład (FIFO)

Niech rozmiar pamięci podręcznej wynosi k=3 początkowa pamięć podręczna a,b,c oraz żądanie a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Trzynaście pominięć pamięci podręcznej przez szesnaście żądań nie brzmi zbyt optymalnie, spróbujmy tego samego przykładu z inną strategią:

Przykład (LFD)

Niech rozmiar pamięci podręcznej wynosi k=3 początkowa pamięć podręczna a,b,c oraz żądanie a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Osiem braków pamięci podręcznej jest znacznie lepsze.

Selftest : zrób przykład dla LIFO, LFU, RFU i zobacz, co się stanie.

Poniższy przykładowy program (napisany w C ++) składa się z dwóch części:

Szkielet to aplikacja, która rozwiązuje problem w zależności od wybranej chciwej strategii:

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

Podstawowa idea jest prosta: na każde żądanie mam dwa połączenia dwa moja strategia:

1. zastosowanie : strategia musi poinformować dzwoniącego, której strony użyć
2. aktualizacja : Po tym, jak dzwoniący skorzysta z tego miejsca, informuje strategię, czy to było spudłowanie, czy nie. Następnie strategia może zaktualizować swoje dane wewnętrzne. Na przykład strategia LFU musi zaktualizować częstotliwość trafień stron pamięci podręcznej, podczas gdy strategia LFD musi ponownie obliczyć odległości dla stron pamięci podręcznej.

Teraz spójrzmy na przykładowe implementacje naszych pięciu strategii:

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 potrzebuje tylko informacji o tym, jak długo strona jest w pamięci podręcznej (i oczywiście tylko w stosunku do innych stron). Jedyne, co należy zrobić, to poczekać na spudłowanie, a następnie sprawić, by strony, których nie eksmitowano, były starsze. W powyższym przykładzie rozwiązaniem programu jest:

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

Dokładnie to rozwiązanie z góry.

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

Implementacja LIFO jest mniej więcej taka sama jak FIFO, ale eksmitujemy najmłodszą, a nie najstarszą stronę. Wyniki programu są następujące:

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

W przypadku LRU strategia jest niezależna od tego, co znajduje się na stronie pamięci podręcznej, jej jedynym zainteresowaniem jest ostatnie użycie. Wyniki programu są następujące:

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 eksmituje stronę najczęściej. Strategia aktualizacji polega więc na policzeniu każdego dostępu. Oczywiście po spudłowaniu licznik resetuje się. Wyniki programu są następujące:

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

Strategia LFD różni się od wszystkich wcześniej. Jest to jedyna strategia, która wykorzystuje przyszłe wnioski o decyzję o tym, kogo eksmitować. Implementacja korzysta z funkcji calcNextUse aby uzyskać stronę, której następne użycie będzie najdalej w przyszłości. Rozwiązanie programu jest równe rozwiązaniu ręcznie z góry:

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 

Chciwa strategia LFD jest rzeczywiście jedyną optymalną strategią spośród pięciu przedstawionych. Dowód jest dość długi i można go znaleźć tutaj lub w książce Jona Kleinberga i Evy Tardos (patrz źródła w uwagach poniżej).

Algorytm a rzeczywistość

Strategia LFD jest optymalna, ale jest duży problem. To optymalne rozwiązanie offline . W praktyce buforowanie jest zwykle problemem online , co oznacza, że strategia jest bezużyteczna, ponieważ nie możemy teraz, gdy następnym razem będziemy potrzebować określonego elementu. Pozostałe cztery strategie to także strategie online . W przypadku problemów online potrzebujemy ogólnie innego podejścia.