algorithm
Aplicaciones de la técnica codiciosa.

Observaciones

Ticket automático

Primer ejemplo simple:

Usted tiene un ticket automático que ofrece el intercambio en monedas con valores 1, 2, 5, 10 y 20. La disposición del cambio se puede ver como una serie de monedas que caen hasta que se entrega el valor correcto. Decimos que una dispensión es óptima cuando su cuenta de monedas es mínima por su valor.

Sea M en [1,50] el precio del boleto T y P en [1,50] el dinero que alguien pagó por T , con P >= M Sea D=PM . Definimos el beneficio de un paso como la diferencia entre D y Dc con c la moneda que el autómata dispensa en este paso.

La técnica codiciosa para el intercambio es el siguiente enfoque pseudo algorítmico:

Paso 1: mientras que D > 20 dispensa una moneda de 20 y establece D = D - 20
Paso 2: mientras que D > 10 dispensa una moneda de 10 y establece D = D - 10
Paso 3: mientras que D > 5 dispensa una moneda de 5 y establece D = D - 5
Paso 4: mientras que D > 2 dispensa una moneda de 2 y establece D = D - 2
Paso 5: mientras que D > 1 dispensa una moneda 1 y establece D = D - 1

Después, la suma de todas las monedas es claramente D Es un algoritmo codicioso porque después de cada paso y después de cada repetición de un paso, el beneficio se maximiza. No podemos dispensar otra moneda con un beneficio mayor.

Ahora el ticket automático como programa (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;
}

Tenga en cuenta que ahora hay verificación de entrada para mantener el ejemplo simple. Un ejemplo de salida:

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

Mientras 1 esté en los valores de la moneda, ahora, el algoritmo terminará, porque:

• D disminuye estrictamente con cada paso.
• D nunca es >0 y más pequeño que la moneda más pequeña 1 al mismo tiempo

Pero el algoritmo tiene dos trampas:

1. Sea C el mayor valor de la moneda. El tiempo de ejecución es solo polinomial mientras D/C sea ​​polinomial, porque la representación de D utiliza solo los bits de log D y el tiempo de ejecución es al menos lineal en D/C
2. En cada paso nuestro algoritmo elige el óptimo local. Pero esto no es suficiente para decir que el algoritmo encuentra la solución óptima global (consulte más información aquí o en el Libro de Korte y Vygen ).

Un simple ejemplo de contador: las monedas son 1,3,4 y D=6 . La solución óptima es claramente dos monedas de valor 3 pero codiciosa elige 4 en el primer paso, por lo que debe elegir 1 en el paso dos y tres. Así que no da una soution óptima. Un posible algoritmo óptimo para este ejemplo se basa en la programación dinámica .

Programación de intervalos

Tenemos un conjunto de trabajos J={a,b,c,d,e,f,g} . Sea j in J un trabajo que su comienzo en sj y termina en fj . Dos trabajos son compatibles si no se superponen. Una imagen como ejemplo: El objetivo es encontrar el subconjunto máximo de trabajos compatibles entre sí . Hay varios enfoques codiciosos para este problema:

1. Hora de inicio más temprana : considerar trabajos en orden ascendente de sj
2. Tiempo de finalización más temprano : considerar trabajos en orden ascendente de fj
3. Intervalo más corto : considere trabajos en orden ascendente de fj-sj
4. Menos conflictos : para cada trabajo j , cuente el número de trabajos en conflicto cj

La pregunta ahora es, qué enfoque es realmente exitoso. Hora de inicio anticipado definitivamente no, aquí hay un ejemplo contrario. El intervalo más corto tampoco es óptimo y el menor número de conflictos puede parecer realmente óptimo, pero aquí hay un caso de problema para este enfoque: Lo que nos deja con el tiempo de llegada más temprano . El pseudo código es bastante simple:

1. Ordena los trabajos por tiempo de finalización para que f1<=f2<=...<=fn
2. Sea A un conjunto vacío.
3. para j=1 a n si j es compatible con todos los trabajos en A set A=A+{j}
4. A es un subconjunto máximo de trabajos compatibles entre sí.

O como programa 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 salida para este ejemplo es: Compatible: (1,3) (4,5) (6,8) (9,10)

La implementación del algoritmo está claramente en Θ (n ^ 2). Hay una implementación de Θ (n log n) y el lector interesado puede continuar leyendo a continuación (Ejemplo de Java).

Ahora tenemos un algoritmo codicioso para el problema de la programación de intervalos, pero ¿es óptimo?

Proposición: El algoritmo codicioso, el tiempo de llegada más temprano, es óptimo.

Prueba: (por contradicción)

Supongamos que la codicia no es óptima y i1,i2,...,ik denota el conjunto de trabajos seleccionados por codicia. Dejemos que j1,j2,...,jm denote el conjunto de trabajos en una solución óptima con i1=j1,i2=j2,...,ir=jr para el mayor valor posible de r .

El trabajo i(r+1) existe y finaliza antes de j(r+1) (primer final). Pero que es j1,j2,...,jr,i(r+1),j(r+2),...,jm también es una solución óptima y para todo k en [1,(r+1)] es jk=ik . eso es una contradicción a la maximalidad de r . Esto concluye la prueba.

Este segundo ejemplo demuestra que usualmente hay muchas estrategias codiciosas posibles pero solo algunas o incluso ninguna puede encontrar la solución óptima en cada instancia.

A continuación se muestra un programa Java que se ejecuta en Θ (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));
    }
}

Y la salida esperada es:

Optimal profit is 250

Minimizando la latitud

Existen numerosos problemas para minimizar la tardanza, aquí tenemos un recurso único que solo puede procesar un trabajo a la vez. El trabajo j requiere tj unidades de tiempo de procesamiento y se debe entregar en el momento dj . si j comienza en el tiempo sj , terminará en el tiempo fj=sj+tj . Definimos la tardanza L=max{0,fj-dh} para todos j . El objetivo es minimizar la tardanza máxima L.

La solución L=7 obviamente no es óptima. Veamos algunas estrategias codiciosas:

1. Tiempo de procesamiento más corto primero : programe trabajos en orden ascendente og tiempo de procesamiento j`
2. Primera fecha límite más temprana : programe los trabajos en orden ascendente de la fecha límite dj
3. Menor holgura : programe trabajos en orden ascendente de holgura dj-tj

Es fácil ver que el tiempo de procesamiento más corto primero no es óptimo, un buen ejemplo de contador es

La solución de pila más pequeña tiene problemas similares.

La última estrategia parece válida, así que comenzamos con un pseudo código:

1. Ordene n trabajos a su debido tiempo para que d1<=d2<=...<=dn
2. Establecer t=0
3. para j=1 a n
   • Asignar trabajo j a intervalo [t,t+tj]
   • establece sj=t y fj=t+tj
   • establecer t=t+tj
4. intervalos de retorno [s1,f1],[s2,f2],...,[sn,fn]

Y como implementación 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;
}

Y la salida para este programa es:

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

El tiempo de ejecución del algoritmo es obviamente Θ (n log n) porque la ordenación es la operación dominante de este algoritmo. Ahora tenemos que demostrar que es óptimo. Claramente un horario óptimo no tiene tiempo de inactividad . el primer horario del primer plazo tampoco tiene tiempo de inactividad.

Supongamos que los trabajos están numerados de modo que d1<=d2<=...<=dn . Decimos que una inversión de un cronograma es un par de trabajos i y j para que i<j pero j esté programado antes de i . Debido a su definición, el primer calendario de la primera fecha límite no tiene inversiones. Por supuesto, si un programa tiene una inversión, tiene uno con un par de trabajos invertidos programados consecutivamente.

Proposición: El intercambio de dos trabajos invertidos adyacentes reduce el número de inversiones en uno y no aumenta la tardanza máxima.

Prueba: Sea L la tardanza antes del cambio y M la tardanza después. Debido a que el intercambio de dos trabajos adyacentes no mueve los otros trabajos de su posición, es Lk=Mk para todo k != i,j .

Está claro que es Mi<=Li , porque la petición i he programado anteriormente. Si el trabajo j se retrasa, entonces se sigue de la definición:

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

Eso significa que la tardanza después del intercambio es menor o igual que antes. Esto concluye la prueba.

Proposición: El primer horario de la primera fecha límite S es óptimo.

Prueba: (por contradicción)

Supongamos que S* es un programa óptimo con el menor número posible de inversiones. Podemos asumir que S* no tiene tiempo de inactividad. Si S* no tiene inversiones, entonces S=S* y hemos terminado. Si S* tiene una inversión, entonces tiene una inversión adyacente. La última Proposición declara que podemos intercambiar la inversión adyacente sin aumentar el retraso, pero disminuyendo el número de inversiones. Esto contradice la definición de S* .

El problema de la minimización de la demora y su problema de makepan mínimo relacionado cercano, donde se hace la pregunta para un horario mínimo, tiene muchas aplicaciones en el mundo real. Pero, por lo general, no tiene una sola máquina, sino muchas, y manejan la misma tarea a diferentes velocidades. Estos problemas consiguen NP-completo muy rápido.

Otra pregunta interesante surge si no observamos el problema fuera de línea , donde tenemos todas las tareas y los datos a la mano, pero en la variante en línea , donde aparecen las tareas durante la ejecución.

Offline Caching

El problema del almacenamiento en caché surge de la limitación del espacio finito. Supongamos que nuestro caché C tiene k páginas. Ahora queremos procesar una secuencia de m solicitudes de elementos que deben haber sido colocadas en el caché antes de que sean procesadas. Por supuesto, si m<=k , simplemente colocamos todos los elementos en el caché y funcionará, pero generalmente es m>>k .

Decimos que una solicitud es un acierto de caché , cuando el elemento ya está en caché, de lo contrario se denomina falta de caché . En ese caso, debemos traer el elemento solicitado a la memoria caché y desalojar a otro, asumiendo que la memoria caché está llena. El objetivo es un programa de desalojo que minimiza el número de desalojos .

Existen numerosas estrategias codiciosas para este problema, veamos algunas:

1. Primero en entrar, primero en salir (FIFO) : la página más antigua se desaloja
2. Último en entrar, primero en salir (LIFO) : la página más nueva se desaloja
3. Última salida reciente (LRU) : página de desalojo cuyo acceso más reciente fue el más antiguo
4. Solicitud menos frecuente (LFU) : página de desalojo que se solicitó con menor frecuencia
5. Distancia de avance más larga (LFD) : Desaloja la página en el caché que no se solicita hasta el momento más lejano.

Atención: En los siguientes ejemplos, desalojamos la página con el índice más pequeño, si se puede desalojar más de una página.

Ejemplo (FIFO)

Sea el tamaño del caché k=3 el caché inicial a,b,c y la solicitud a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Trece fallos de caché por dieciséis solicitudes no suenan muy óptimos, probemos el mismo ejemplo con otra estrategia:

Ejemplo (LFD)

Sea el tamaño del caché k=3 el caché inicial a,b,c y la solicitud a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Ocho errores de caché es mucho mejor.

Prueba inmediata : haga el ejemplo para LIFO, LFU, RFU y vea lo que sucedió.

El siguiente programa de ejemplo (escrito en C ++) consta de dos partes:

El esqueleto es una aplicación que resuelve el problema dependiendo de la estrategia codiciosa elegida:

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

La idea básica es simple: para cada solicitud tengo dos llamadas dos mi estrategia:

1. aplicar : la estrategia tiene que decirle a la persona que llama qué página usar
2. actualización : después de que la persona que llama usa el lugar, le dice a la estrategia si fue una falla o no. Entonces la estrategia puede actualizar sus datos internos. La estrategia LFU, por ejemplo, tiene que actualizar la frecuencia de aciertos para las páginas de caché, mientras que la estrategia LFD tiene que recalcular las distancias para las páginas de caché.

Ahora veamos ejemplos de implementaciones para nuestras cinco estrategias:

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 solo necesita la información sobre el tiempo que una página está en el caché (y, por supuesto, solo en relación con las otras páginas). Así que lo único que hay que hacer es esperar a que se pierda y luego hacer las páginas, que no fueron desalojadas. Para nuestro ejemplo anterior, la solución del programa es:

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

Eso es exacto la solución de arriba.

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 implementación de LIFO es más o menos la misma que en FIFO, pero desalojamos a los más jóvenes y no a los más antiguos. Los resultados del programa son:

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

En el caso de LRU, la estrategia es independiente de lo que está en la página de caché, su único interés es el último uso. Los resultados del programa son:

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 desaloja la página con menos frecuencia. Así que la estrategia de actualización es solo contar cada acceso. Por supuesto, después de una falta, la cuenta se reinicia. Los resultados del programa son:

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 estrategia de LFD es diferente de todos antes. Es la única estrategia que utiliza las futuras solicitudes para su decisión a quién desalojar. La implementación utiliza la función calcNextUse para obtener la página que el siguiente uso está más lejos en el futuro. La solución del programa es igual a la solución a mano desde arriba:

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 estrategia codiciosa LFD es, de hecho, la única estrategia óptima de las cinco presentadas. La prueba es bastante larga y se puede encontrar aquí o en el libro de Jon Kleinberg y Eva Tardos (consulte las fuentes en los comentarios a continuación).

Algoritmo vs Realidad

La estrategia de LFD es óptima, pero hay un gran problema. Es una solución óptima fuera de línea . En la práctica, el almacenamiento en caché suele ser un problema en línea , lo que significa que la estrategia es inútil porque no podemos ahora la próxima vez que necesitemos un elemento en particular. Las otras cuatro estrategias son también estrategias en línea . Para problemas en línea necesitamos un enfoque general diferente.