algorithm
Applications de la technique gourmande

Remarques

Automate à billet

Premier exemple simple:

Vous avez un automate de ticket qui échange des pièces de monnaie avec les valeurs 1, 2, 5, 10 et 20. La répartition de l'échange peut être vue comme une série de pièces tombant jusqu'à ce que la bonne valeur soit distribuée. Nous disons qu'une dissension est optimale lorsque son nombre de pièces est minimal pour sa valeur.

Soit M dans [1,50] le prix du ticket T et P dans [1,50] l'argent que quelqu'un a payé pour T , avec P >= M Soit D=PM . Nous définissons l' avantage d'une étape comme la différence entre D et Dc avec c la pièce que l'automate distribue dans cette étape.

La technique gourmande pour l'échange est l'approche pseudo-algorithmique suivante:

Etape 1: pendant que D > 20 distribue 20 pièces et que D = D - 20
Étape 2: pendant que D > 10 distribue une pièce de 10 pièces et que D = D - 10
Etape 3: pendant que D > 5 distribue 5 pièces et que D = D - 5
Etape 4: pendant que D > 2 distribue 2 pièces et que D = D - 2
Etape 5: pendant que D > 1 distribue 1 pièce et que D = D - 1

Ensuite, la somme de toutes les pièces est clairement égale à D C'est un algorithme glouton car après chaque étape et après chaque répétition d'une étape, l'avantage est maximisé. Nous ne pouvons pas dispenser une autre pièce avec un avantage plus élevé.

Maintenant, le distributeur automatique de tickets en tant que programme (en 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;
}

Sachez qu'il y a maintenant une vérification des entrées pour garder l'exemple simple. Un exemple de sortie:

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

Tant que 1 est dans les valeurs de pièce, nous avons maintenant, que l'algorithme se terminera, car:

• D diminue à chaque pas
• D est jamais >0 et plus petit que la plus petite pièce 1 en même temps

Mais l'algorithme a deux pièges:

1. Soit C la plus grande valeur de pièce. Le runtime n'est que polynomial tant que D/C est polynomial, car la représentation de D n'utilise que log D bits log D et le runtime est au moins linéaire en D/C
2. À chaque étape, notre algorithme choisit l'optimum local. Mais cela ne suffit pas pour dire que l'algorithme trouve la solution optimale globale (voir plus d'informations ici ou dans le Livre de Korte et de Vygen ).

Un exemple simple de compteur: les pièces sont 1,3,4 et D=6 . La solution optimale est clairement de deux pièces de valeur 3 mais la gourmande choisit 4 dans la première étape, elle doit donc choisir 1 à l'étape deux et trois. Donc, cela ne donne aucune soution optimale. Un algorithme optimal possible pour cet exemple est basé sur la programmation dynamique .

Planification d'intervalle

Nous avons un ensemble de travaux J={a,b,c,d,e,f,g} . Soit j in J un travail que son début en sj et se termine en fj . Deux tâches sont compatibles si elles ne se chevauchent pas. Une image comme exemple: Le but est de trouver le sous-ensemble maximum de travaux compatibles entre eux . Il existe plusieurs approches gourmandes pour ce problème:

1. Heure de début au plus tôt : considérez les travaux dans l'ordre croissant de sj
2. Heure de fin la plus proche : considérez les travaux dans l'ordre croissant de fj
3. Intervalle le plus court : considérez les travaux dans l'ordre croissant de fj-sj
4. Moins de conflits : pour chaque emploi j , compter le nombre de tâches en conflit cj

La question est maintenant, quelle approche est vraiment réussie. Heure de début précoce définitivement pas, voici un contre-exemple L'intervalle le plus court n'est pas optimal non plus et les conflits les moins nombreux peuvent en effet sembler optimaux, mais voici un cas problématique pour cette approche: Ce qui nous laisse le plus tôt possible . Le pseudo-code est simple:

1. Trier les travaux en fonction de l'heure de fin pour que f1<=f2<=...<=fn
2. Soit A un ensemble vide
3. pour j=1 à n si j est compatible avec tous les jobs de A set A=A+{j}
4. A est un sous-ensemble maximum de travaux compatibles entre eux

Ou en tant que programme 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;
}

La sortie pour cet exemple est: Compatible: (1,3) (4,5) (6,8) (9,10)

L'implémentation de l'algorithme est clairement dans Θ (n ^ 2). Il existe une implémentation Θ (n log n) et le lecteur intéressé peut continuer à lire ci-dessous (exemple Java).

Maintenant, nous avons un algorithme glouton pour le problème de planification des intervalles, mais est-ce optimal?

Proposition: L’algorithme glouton le plus tôt possible est optimal.

Preuve: (par contradiction)

Supposons que greedy n'est pas optimal et que i1,i2,...,ik désignent l'ensemble des jobs sélectionnés par les gourmands. Soit j1,j2,...,jm l'ensemble des travaux dans une solution optimale avec i1=j1,i2=j2,...,ir=jr pour la plus grande valeur possible de r .

Le travail i(r+1) existe et se termine avant j(r+1) (première arrivée). Mais que sont j1,j2,...,jr,i(r+1),j(r+2),...,jm aussi une solution optimale et pour tout k dans [1,(r+1)] est jk=ik . thats une contradiction à la maximalité de r . Ceci conclut la preuve.

Ce second exemple montre qu'il existe généralement de nombreuses stratégies gourmandes possibles, mais que seules certaines d'entre elles, voire aucune, pourraient trouver la solution optimale dans chaque cas.

Ci-dessous, un programme Java qui s'exécute dans log (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));
    }
}

Et le résultat attendu est:

Optimal profit is 250

Minimiser les retards

Il existe de nombreux problèmes minimisant le retard, nous avons ici une seule ressource qui ne peut traiter qu'un seul travail à la fois. La tâche j nécessite tj unités de temps de traitement et est due à l'instant dj . si j commence à l'instant sj il finira à l'instant fj=sj+tj . Nous définissons le retard L=max{0,fj-dh} pour tout j . Le but est de minimiser le retard maximal L.

La solution L=7 n'est évidemment pas optimale. Regardons quelques stratégies gourmandes:

1. Temps de traitement le plus court en premier : planifier les travaux dans l'ordre croissant og temps de traitement j`
2. Première date limite en premier : Planifier les travaux dans l'ordre croissant des délais dj
3. Le plus petit jeu : planifier les travaux en ordre croissant de jeu dj-tj

Il est facile de voir que le temps de traitement le plus court n’est pas optimal.

la plus petite solution de pile a des problèmes similaires

la dernière stratégie semble valide, nous commençons donc avec du pseudo-code:

1. Trier n travaux en temps d1<=d2<=...<=dn pour que d1<=d2<=...<=dn
2. Set t=0
3. pour j=1 à n
   • Attribuer le travail j à l'intervalle [t,t+tj]
   • set sj=t et fj=t+tj
   • définir t=t+tj
4. intervalles de retour [s1,f1],[s2,f2],...,[sn,fn]

Et comme implémentation en 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;
}

Et la sortie de ce programme est la suivante:

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

Le temps d'exécution de l'algorithme est évidemment Θ (n log n) car le tri est l'opération dominante de cet algorithme. Maintenant, nous devons montrer que c'est optimal. Clairement, un horaire optimal n'a pas de temps d'inactivité . la première échéance n'a pas non plus de temps mort.

Supposons que les travaux sont numérotés de sorte que d1<=d2<=...<=dn . Nous disons qu'une inversion d'une planification est une paire de travaux i et j sorte que i<j mais j est planifié avant i . En raison de sa définition, la première échéance n’a pas d’inversion. Bien sûr, si un programme a une inversion, il en a un avec une paire de travaux inversés programmés consécutivement.

Proposition: L' échange de deux travaux inversés adjacents réduit le nombre d'inversions de un et n'augmente pas le retard maximal.

Preuve: Soit L le retard avant le swap et M le retard après. Comme l'échange de deux travaux adjacents ne déplace pas les autres travaux de leur position, c'est Lk=Mk pour tout k != i,j .

De toute évidence , il est Mi<=Li depuis travail i suis programmé plus tôt. si le travail j est en retard, il découle de la définition:

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

Cela signifie que le retard après l’échange est inférieur ou égal à celui d’avant. Ceci conclut la preuve.

Proposition: La date limite la plus proche du premier horaire S est optimale.

Preuve: (par contradiction)

Supposons que S* est le programme optimal avec le plus petit nombre possible d'inversions. nous pouvons supposer que S* n'a pas de temps d'inactivité. Si S* n'a pas d'inversions, alors S=S* et nous avons terminé. Si S* a une inversion, il a une inversion adjacente. La dernière proposition indique que nous pouvons échanger l'inversion adjacente sans augmenter les retards mais en diminuant le nombre d'inversions. Ceci contredit la définition de S* .

Le problème de la minimisation des retards et son problème de makespan minimum proche, où la question d'un calendrier minimal est posée, ont beaucoup d'applications dans le monde réel. Mais généralement, vous n'avez pas une seule machine, mais beaucoup d'entre elles et elles gèrent la même tâche à des rythmes différents. Ces problèmes font que NP-complete est vraiment rapide.

Une autre question intéressante se pose si nous ne regardons pas le problème hors ligne , où nous avons toutes les tâches et les données à portée de main, mais dans la variante en ligne , où les tâches apparaissent pendant l'exécution.

Mise en cache hors ligne

Le problème de mise en cache provient de la limitation de l'espace fini. Supposons que notre cache C a k pages. Maintenant, nous voulons traiter une séquence de m requêtes qui doivent avoir été placées dans le cache avant d'être traitées. Bien sûr, si m<=k nous mettons simplement tous les éléments dans le cache et cela fonctionnera, mais habituellement, c'est m>>k .

Nous disons qu'une requête est un succès de cache , lorsque l'élément est déjà en cache, sinon il est appelé un échec de cache . Dans ce cas, nous devons mettre l'élément demandé en cache et en expulser un autre, à condition que le cache soit plein. L'objectif est un calendrier d'expulsion qui minimise le nombre d'expulsions .

Il existe de nombreuses stratégies gourmandes pour ce problème:

1. Premier entré, premier sorti (FIFO) : la plus ancienne page est expulsée
2. Last in, first out (LIFO) : la page la plus récente est expulsée
3. Dernière sortie récente (LRU) : page d'éviction dont l'accès le plus récent était le plus ancien
4. Moins fréquemment demandé (LFU) : page d'éviction la moins fréquemment demandée
5. Distance la plus longue (LFD) : expulse la page dans le cache qui n'est demandée que plus tard.

Attention: Pour les exemples suivants, nous expulsons la page avec le plus petit index, si plusieurs pages peuvent être expulsées.

Exemple (FIFO)

Soit la taille du cache k=3 le cache initial a,b,c et la requête a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Treize caches manquent par seize requêtes ne sonnent pas très optimales, essayons le même exemple avec une autre stratégie:

Exemple (LFD)

Soit la taille du cache k=3 le cache initial a,b,c et la requête a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Huit caches manques sont beaucoup mieux.

Selftest : Faites l'exemple pour LIFO, LFU, RFU et regardez ce qui s'est passé.

L'exemple de programme suivant (écrit en C ++) comprend deux parties:

Le squelette est une application qui résout le problème en fonction de la stratégie gourmande choisie:

#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'idée de base est simple: pour chaque demande, j'ai deux appels deux ma stratégie:

1. apply : La stratégie doit indiquer à l'appelant quelle page utiliser
2. update : une fois que l'appelant a utilisé le lieu, il indique à la stratégie si elle a échoué ou non. La stratégie peut alors mettre à jour ses données internes. La stratégie LFU, par exemple, doit mettre à jour la fréquence des accès aux pages de cache, tandis que la stratégie LFD doit recalculer les distances des pages de cache.

Regardons maintenant des exemples d'implémentations pour nos cinq stratégies:

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 a juste besoin de savoir depuis combien de temps une page est dans le cache (et bien sûr seulement par rapport aux autres pages). Donc, la seule chose à faire est d'attendre un échec, puis de faire les pages qui ne sont pas expulsées plus anciennes. Pour notre exemple ci-dessus, la solution du programme est la suivante:

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

C'est la solution exacte ci-dessus.

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

La mise en œuvre du LIFO est plus ou moins la même que celle du FIFO mais nous expulsons la page la plus jeune et non la plus ancienne. Les résultats du programme sont les suivants:

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

Dans le cas d'une LRU, la stratégie est indépendante de ce qui se trouve sur la page cache, son seul intérêt est la dernière utilisation. Les résultats du programme sont les suivants:

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 expulse la page utilisée le moins souvent. La stratégie de mise à jour consiste simplement à compter chaque accès. Bien sûr, après un échec, le compte se réinitialise. Les résultats du programme sont les suivants:

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 stratégie LFD est différente de tout le monde auparavant. C'est la seule stratégie qui utilise les demandes futures pour sa décision d'expulsion. L'implémentation utilise la fonction calcNextUse pour obtenir la page la plus éloignée dans le futur. La solution du programme est égale à la solution par le haut:

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 stratégie gourmande LFD est en effet la seule stratégie optimale des cinq présentées. La preuve est assez longue et peut être trouvée ici ou dans le livre de Jon Kleinberg et Eva Tardos (voir les sources dans les remarques ci-dessous).

Algorithme vs réalité

La stratégie LFD est optimale, mais il y a un gros problème. C'est une solution hors ligne optimale. Dans la praxis, la mise en cache est généralement un problème en ligne , ce qui signifie que la stratégie est inutile car nous ne pouvons pas le faire la prochaine fois que nous avons besoin d'un élément particulier. Les quatre autres stratégies sont également des stratégies en ligne . Pour les problèmes en ligne, nous avons besoin d'une approche générale différente.