algorithm
Применение жадности

замечания

Автомат для продажи билетов

Первый простой пример:

У вас есть автомат для билетов, который дает обмен в монетах со значениями 1, 2, 5, 10 и 20. Разделение обмена можно рассматривать как серию капель монет до тех пор, пока не будет отменено правильное значение. Мы говорим, что распределение является оптимальным, когда его количество монет минимально для его значения.

Пусть M в [1,50] будет ценой для билета T и P в [1,50] деньгами, которые кто-то заплатил за T , с P >= M Пусть D=PM . Определим преимущество шага как разница между D и Dc с c в монете автомат раздаточным в этом шаге.

Метод жадности для обмена - это следующий псевдо-алгоритмический подход:

Шаг 1: в то время как D > 20 выдают 20 монет и устанавливают D = D - 20
Шаг 2: в то время как D > 10 распределяет 10 монет и устанавливает D = D - 10
Шаг 3: в то время как D > 5 выдают 5 монет и устанавливают D = D - 5
Шаг 4: в то время как D > 2 выдают 2 монеты и устанавливают D = D - 2
Шаг 5: пока D > 1 раздаст 1 монету и установите D = D - 1

Впоследствии сумма всех монет явно равна D Его жадный алгоритм, потому что после каждого шага и после каждого повторения шага преимущество максимизируется. Мы не можем отказаться от другой монеты с более высокой выгодой.

Теперь автоматика билетов как программа (в 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;
}

Имейте в виду, что теперь есть проверка ввода, чтобы простой пример. Один пример:

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

Пока 1 находится в значениях монеты, мы теперь, что алгоритм закончится, потому что:

• D строго уменьшается с каждым шагом
• D никогда не >0 и меньше, чем самая маленькая монета 1 в то же время

Но алгоритм имеет две ошибки:

1. Пусть C - наибольшее значение монеты. Время выполнения является только полиномиальным, если D/C является полиномиальным, поскольку представление D использует только биты log D а время выполнения по крайней мере линейно в D/C
2. На каждом шаге наш алгоритм выбирает локальный оптимум. Но этого недостаточно, чтобы сказать, что алгоритм находит глобальное оптимальное решение (см. Больше информации здесь или в Книге Корте и Vygen ).

Простой пример счетчика: монеты составляют 1,3,4 и D=6 . Оптимальным решением является, очевидно, две монеты значения 3 но жадный выбор 4 на первом этапе, поэтому ему нужно выбрать 1 на шаге два и три. Поэтому он не дает оптимального суждения. Возможный оптимальный алгоритм для этого примера основан на динамическом программировании .

Планирование интервалов

У нас есть набор заданий J={a,b,c,d,e,f,g} . Пусть j in J - задание, чем его начало в sj и заканчивается в fj . Два задания совместимы, если они не перекрываются. Рисунок как пример: Цель состоит в том, чтобы найти максимальное подмножество взаимно совместимых заданий . Есть несколько жадных подходов к этой проблеме:

1. Самое раннее время начала : Рассмотрите задания в порядке возрастания sj
2. Самое раннее время окончания : рассмотрите задания в порядке возрастания fj
3. Самый короткий интервал : рассмотрите задания в порядке возрастания fj-sj
4. Наименьшие конфликты : для каждого задания j подсчитывайте количество противоречивых заданий cj

Вопрос в том, какой подход действительно успешный. Раннее время начала, конечно, нет, вот примерный пример Самый короткий интервал не является оптимальным и наименьшее количество конфликтов может действительно оказаться оптимальным, но здесь есть проблема для такого подхода: Что оставляет нас с самым ранним временем окончания . Псевдокод довольно простой:

1. Сортировка заданий по времени окончания, так что f1<=f2<=...<=fn
2. Пусть A - пустое множество
3. для j=1 до n , если j совместима со всех рабочих мест в A множества A=A+{j}
4. A - максимальное подмножество взаимно совместимых заданий

Или как программа на 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;
}

Выход для этого примера: Compatible: (1,3) (4,5) (6,8) (9,10)

Реализация алгоритма явно находится в Θ (n ^ 2). Существует реализация Θ (n log n), и заинтересованный читатель может продолжить чтение ниже (пример Java).

Теперь у нас есть жадный алгоритм для задачи планирования интервалов, но оптимален ли он?

Предложение: Самый жалкий алгоритм - самое раннее время окончания .

Доказательство: (от противного)

Предположим, что жадный не является оптимальным, а i1,i2,...,ik обозначают множество заданий, выбранных жадным. Пусть j1,j2,...,jm обозначает множество заданий в оптимальном решении с i1=j1,i2=j2,...,ir=jr для максимально возможного значения r .

Работа i(r+1) существует и заканчивается до j(r+1) (самое раннее завершение). Но, чем j1,j2,...,jr,i(r+1),j(r+2),...,jm также оптимальное решение и для всех k из [1,(r+1)] jk=ik . r . е. противоречие с максимальностью г. Это завершает доказательство.

Этот второй пример демонстрирует, что обычно существует много возможных жадных стратегий, но только некоторые или даже не могут найти оптимальное решение в каждом случае.

Ниже приведена программа Java, которая работает в Θ (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));
    }
}

И ожидаемый результат:

Optimal profit is 250

Минимизация задержек

Существует множество проблем, минимизирующих опоздание, здесь у нас есть единственный ресурс, который может обрабатывать только одно задание за раз. Задание j требует tj единиц времени обработки и ожидается в момент dj . если j начинается со временем sj оно будет завершено во время fj=sj+tj . Определим латентность L=max{0,fj-dh} для всех j . Цель состоит в том, чтобы свести к минимуму максимальную задержку L.

Решение L=7 , очевидно, не является оптимальным. Давайте посмотрим на некоторые жадные стратегии:

1. Самое короткое время обработки : расписание заданий в порядке возрастания og время обработки j`
2. Самый ранний крайний срок : расписание заданий в порядке возрастания dj
3. Наименьший спад : задание расписания в порядке возрастания slack dj-tj

Легко видеть, что кратчайшее время обработки вначале не является оптимальным, хороший пример счетчика

самое маленькое решение для стека имеет проблемы с simillar

последняя стратегия выглядит действительной, поэтому мы начинаем с некоторого псевдокода:

1. Сортируйте n заданий по времени, чтобы d1<=d2<=...<=dn
2. Положим t=0
3. для j=1 - n
   • Назначьте задание j интервалу [t,t+tj]
   • множество sj=t и fj=t+tj
   • множество t=t+tj
4. интервалы возврата [s1,f1],[s2,f2],...,[sn,fn]

И как реализация в 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;
}

И выход для этой программы:

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

Время выполнения алгоритма, очевидно, Θ (n log n), поскольку сортировка является доминирующей операцией этого алгоритма. Теперь нам нужно показать, что оно оптимально. Очевидно, что оптимальный график не имеет времени простоя . в самом раннем срочном графике также нет простоя.

Предположим, что задания нумеруются так, что d1<=d2<=...<=dn . Мы говорим, что инверсия графика - это пара заданий i и j так что i<j но j запланировано до i . Из-за его определения самый ранний крайний срок для первого графика не имеет инверсий. Конечно, если в расписании есть инверсия, у него есть одна с двумя инвертированными заданиями, запланированными последовательно.

Предложение: замена двух смежных, перевернутых заданий уменьшает количество инверсий на единицу и не увеличивает максимальную задержку.

Доказательство. Пусть L - задержка перед свопом, а M - позднее. Поскольку обмен двумя соседними заданиями не перемещает другие задания из их положения, это Lk=Mk для всех k != i,j .

Ясно, что Mi<=Li , так как работы i получил запланировано ранее. если задание j опаздывает, это следует из определения:

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

Это означает, что задержка после смены меньше или равна, чем раньше. Это завершает доказательство.

Предложение: самый ранний крайний срок первого графика S является оптимальным.

Доказательство: (от противного)

Предположим, что S* - оптимальное расписание с наименьшим числом инверсий. мы можем предположить, что S* не имеет простоя. Если S* не имеет инверсий, то S=S* и мы закончили. Если S* имеет инверсию, то она имеет смежную инверсию. В последнем предложении говорится, что мы можем поменять соседнюю инверсию без увеличения задержки, но с уменьшением числа инверсий. Это противоречит определению S* .

Сведение к минимуму проблемы с задержкой и связанной с ней минимальной проблемой разрешения проблемы, когда задан вопрос о минимальном расписании, есть множество приложений в реальном мире. Но обычно у вас не только одна машина, но и многие, и они выполняют одну и ту же задачу с разной скоростью. Эти проблемы очень быстрые.

Еще один интересный вопрос возникает, если мы не смотрим на автономную проблему, где у нас есть все задачи и данные под рукой, но в онлайн- варианте, где задачи появляются во время выполнения.

Автономное кэширование

Проблема кэширования возникает из-за ограничения конечного пространства. Допустим, что наш кеш C имеет k страниц. Теперь мы хотим обработать последовательность m запросов элементов, которые должны были быть помещены в кеш, прежде чем они будут обработаны. Конечно, если m<=k мы просто поместим все элементы в кеш, и он будет работать, но обычно это m>>k .

Мы говорим, что запрос - это кэш , когда элемент уже находится в кеше, иначе его называют пропуском кеша . В этом случае мы должны привести запрошенный элемент в кеш и выселить другого, считая, что кеш заполнен. Цель - график выселения, который минимизирует количество выселений .

Есть много жадных стратегий для этой проблемы, давайте посмотрим на некоторые:

1. Первое, сначала (FIFO) : старейшая страница выселяется
2. Последний, первый (LIFO) : самая новая страница выселяется
3. Последняя недавняя страница (LRU) : страница с изъятием, последний доступ которой был самым ранним
4. Наименее часто запрашиваемая (LFU) : страница с изъятием, которая была запрошена наименее часто
5. Самое длинное прямое расстояние (LFD) : вырезать страницу в кеше, которая не запрашивается дольше в будущем.

Внимание: В следующих примерах мы выселяем страницу с наименьшим индексом, если может быть выселено более одной страницы.

Пример (FIFO)

Пусть размер кеша k=3 - начальный кеш a,b,c и запрос a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Тринадцать промахов кэша на шестнадцать запросов не очень оптимальны, попробуйте один и тот же пример с другой стратегией:

Пример (LFD)

Пусть размер кеша k=3 - начальный кеш a,b,c и запрос a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

Восемь недостатков кэша намного лучше.

Selftest : Сделайте пример для LIFO, LFU, RFU и посмотрите, что произошло.

Следующая примерная программа (написанная на C ++) состоит из двух частей:

Скелет - это приложение, которое решает проблему, зависящую от выбранной жадной стратегии:

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

Основная идея проста: для каждого запроса у меня есть два вызова две моей стратегии:

1. применить : стратегия должна сообщить вызывающему абоненту, какая страница использовать
2. update : После того, как вызывающий абонент использует это место, он сообщает стратегии, было ли это пропуском или нет. Затем стратегия может обновить свои внутренние данные. Например, стратегия LFU должна обновлять частоту попадания для страниц кеша, тогда как стратегия LFD должна пересчитывать расстояния для страниц кеша.

Теперь рассмотрим примеры реализации для наших пяти стратегий:

ФИФО

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 просто нуждается в информации о том, как долго страница находится в кеше (и, конечно, только по отношению к другим страницам). Так что единственное, что нужно сделать - это подождать промаха, а затем сделать страницы, где бы не выселили. Для нашего примера выше решение программы:

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

Точное решение сверху.

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

Реализация LIFO более или менее такая же, как и FIFO, но мы выселяем самую молодую не самую старую страницу. Результаты программы:

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

В случае LRU стратегия не зависит от того, что находится на странице кэша, но ее единственным интересом является последнее использование. Результаты программы:

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

УКП

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 выселяет страницу, используя ее наименее часто. Поэтому стратегия обновления - это всего лишь подсчет каждого доступа. Конечно, после промаха счет сбрасывается. Результаты программы:

Strategy: LFU

Cache initial: (a,b,c)

Request    cache 0    cache 1    cache 2    cache miss
  a          a          b          c    
  a          a          b          c    
  d          a          d          c          x
  e          a          d          e          x
  b          a          b          e          x
  b          a          b          e    
  a          a          b          e    
  c          a          b          c          x
  f          a          b          f          x
  d          a          b          d          x
  e          a          b          e          x
  a          a          b          e    
  f          a          b          f          x
  b          a          b          f    
  e          a          b          e          x
  c          a          b          c          x

Total cache misses: 10

LFD

class LFD : public Strategy {
public:
    LFD() : Strategy("LFD")
    {
        // precalc next usage before starting to fullfill requests
        for (int i=0; i<cacheSize; ++i) nextUse[i] = calcNextUse(-1, cache[i]);
    }

    int apply(int requestIndex) override
    {
        int latest = 0;

        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            else if(nextUse[i] > nextUse[latest])
                latest = i;
        }

        return latest;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {
            nextUse[cachePos] = calcNextUse(requestIndex, cache[cachePos]);
    }

private:

    int calcNextUse(int requestPosition, char pageItem)
    {
        for(int i = requestPosition+1; i < requestLength; ++i)
        {
            if (request[i] == pageItem)
                return i;
        }

        return requestLength + 1;
    }

    // next usage of page
    int nextUse[cacheSize];
};

Стратегия LFD отличается от всех раньше. Это единственная стратегия, которая использует будущие просьбы о ее освобождении, которые выселяют. Реализация использует функцию calcNextUse чтобы получить страницу, которая будет использоваться дальше в будущем. Решение программы равно решению сверху сверху:

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 

Жадная стратегия LFD - действительно единственная оптимальная стратегия из пяти представленных. Доказательство довольно длинное и можно найти здесь или в книге Джона Клейнберга и Евы Тардос (см. Источники в примечаниях ниже).

Алгоритм против реальности

Стратегия LFD оптимальна, но есть большая проблема. Это оптимальное автономное решение. В практическом кэшировании обычно проблема онлайн , это означает, что стратегия бесполезна, потому что мы не можем сейчас в следующий раз нам нужен конкретный элемент. Другие четыре стратегии также являются онлайн- стратегиями. Для онлайн-проблем нам нужен общий подход.