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 와 같습니다. 그것의 욕심 많은 알고리즘 때문에 각 단계 후 각 단계의 repitition 후 이익이 극대화됩니다. 우리는 더 많은 이익을 가진 다른 동전을 분배 할 수 없습니다.

이제 프로그램으로 티켓 자동 판매기 (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. 모든 단계에서 알고리즘은 로컬 최적을 선택합니다. 그러나 이것은 알고리즘이 전체적인 최적의 솔루션을 찾는다는 것을 말하는 것은 충분하지 않습니다. (자세한 정보는 여기 또는 Korte and Vygen 의 책을 보십시오 ).

간단한 반대 예제 : 동전은 1,3,4 , D=6 입니다. 최적의 솔루션은 분명히 가치 3 동전 2 3 이지만 탐욕스러운 첫 번째 단계에서는 4 를 선택하므로 2 단계와 3 단계에서 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 공집합이라하자 A
3. j 가 A 세트 A=A+{j} 모든 작업과 호환되면 j=1 ~ n 에 대해 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 은 r 가능한 가장 큰 값에 대해 i1=j1,i2=j2,...,ir=jr 인 최적 솔루션의 작업 세트를 나타냅니다.

작업 i(r+1) 가 존재하고 j(r+1) (가장 이른 마무리) 이전에 완료됩니다. 그러나 이상이 j1,j2,...,jr,i(r+1),j(r+2),...,jm 또한 최적해 및 모든 k 에 [1,(r+1)] jk=ik 이다. 그것은 r 의 극대성에 대한 모순 이다. 이것으로 증명을 마칩니다.

이 두 번째 예제는 일반적으로 가능한 많은 욕심 많은 전략이 있지만 일부 또는 일부만이 모든 경우에 최적의 솔루션을 찾을 수 있음을 보여줍니다.

아래는 Θ (n log n)에서 실행되는 Java 프로그램입니다.

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. 가장 짧은 처리 시간 첫 번째 : 작업을 오름차순으로 처리 시간 j '
2. 가장 빠른 데드 라인 첫 번째 : 마감일 dj 오름차순으로 작업 스케줄링
3. 가장 작은 여유 시간 : 느슨한 dj-tj 의 오름차순으로 작업 예약

가장 짧은 처리 시간이 처음 에는 최적이 아니라는 것을 쉽게 알 수 있습니다.

가장 작은 스택 솔루션에는 비슷한 문제가있다.

마지막 전략이 유효 해 보이므로 의사 코드로 시작합니다.

1. 만기 시간을 기준으로 n 작업을 정렬하여 d1<=d2<=...<=dn
2. t=0 설정
3. j=1 ~ n
   • 간격 j 에 작업 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 보다 먼저 스케줄됩니다. 그 정의로 인하여 가장 빠른 데드 라인 첫 번째 스케줄에는 역전이 없습니다. 물론 일정에 반전이있는 경우 연속적으로 예정된 한 쌍의 거꾸로 된 작업이있는 일정이 있습니다.

命 令 : 인접한 2 개의 인버트 작업을 서로 바꿔 가면서 역전 횟수를 1 만큼 줄이고 최대 지연 시간을 늘리지 않습니다 .

증명 : L 스왑 이전의 지각이라하고 나중에 M 을 지각이라고합니다. 인접한 두 작업을 교환하면 다른 작업이 그 위치에서 움직이지 않기 때문에 모든 k != i,j 대해 Lk=Mk 가됩니다.

명확하게는 Mi<=Li 일 이후 i 이전 예정되었다가. j 가 늦으면 정의에서 다음과 같이됩니다.

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

이는 스왑 이후의 지체가 이전보다 작거나 같음을 의미합니다. 이것으로 증명을 마칩니다.

명제 : 가장 빠른 기한 첫 번째 일정 S 가 최적입니다.

증명 : (모순에 의해)

가능한 한 적은 수의 반전으로 S* 가 최적의 스케줄이라고 가정합니다. 우리는 S* 가 유휴 시간이 없다고 추측 할 수있다. S* 에 역변환이 없으면 S=S* 로 끝난다. S* 에 반전이있는 경우 인접 반전보다 반올림됩니다. 마지막 Proposition은 우리가 lateness를 증가시키지 않고 역전의 수를 줄임으로써 인접한 역전을 교환 할 수 있다고 기술하고있다. 이것은 S* 의 정의와 모순된다.

최소한의 일정에 대한 질문에 현실 세계에서 많은 응용 프로그램이있는 Lateness 문제와 이와 관련된 최소한의 Makepan 문제를 최소화합니다. 그러나 보통 당신은 하나의 기계 만 가지고있는 것이 아니라 많은 기계들이 다른 속도로 동일한 작업을 처리합니다. 이러한 문제는 NP 완성을 매우 빠르게 만듭니다.

우리가 모든 작업과 데이터를 보유하고있는 오프라인 문제는 아니지만 실행 중에 작업이 나타나는 온라인 변종에 대해서는 다른 흥미로운 질문이 생깁니다.

오프라인 캐싱

캐싱 문제는 유한 공간의 제한으로 인해 발생합니다. 캐시 C 가 k 페이지를 가지고 있다고 가정합시다. 이제 우리는 처리되기 전에 캐시에 놓여 있어야만하는 m 항목 요청을 처리하려고합니다. 물론 m<=k 이면 모든 요소를 ​​캐시에 넣으면 작동하지만 일반적으로 m>>k .

아이템이 이미 캐시에있을 때 요청이 캐시 히트 라고 말하면, 그렇지 않으면 캐시 미스 라고합니다. 이 경우 요청 된 항목을 캐시로 가져와 캐시가 가득 차 있다고 가정하고 다른 항목을 제거해야합니다. 목표는 퇴거 횟수 를 최소화 하는 퇴거 일정입니다.

이 문제에 대한 수많은 욕심 많은 전략이 있습니다. 몇 가지를 살펴보십시오.

1. 선입 선출 (FIFO) : 가장 오래된 페이지가 축출됩니다.
2. 마지막 입력, 처음 출력 (LIFO) : 가장 새로운 페이지가 제거됨
3. 마지막 최근 아웃 (LRU) : 가장 최근 액세스가 가장 빠진 페이지 삭제
4. 자주 자주 요청되지 않는 항목 (LFU) : 가장 자주 요청하지 않은 페이지 제외
5. LFD (Longest forward distance) : 캐시에서 가장 멀리 떨어져있을 때까지 요청되지 않은 페이지를 제거합니다.

주의 : 다음 예제의 경우, 둘 이상의 페이지를 축출 할 수있는 경우 가장 작은 인덱스를 가진 페이지를 제거합니다.

예 (FIFO)

캐시 크기가하자 k=3 초기 캐시 a,b,c 및 요청 a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

16 개의 요청으로 13 개의 캐시 미스가 최적으로 들리지 않는다면 다른 전략으로 같은 예제를 시도해 볼 수 있습니다.

예 (LFD)

캐시 크기가하자 k=3 초기 캐시 a,b,c 및 요청 a,a,d,e,b,b,a,c,f,d,e,a,f,b,e,c :

8 회의 캐시 미스가 훨씬 좋습니다.

Selftest : LIFO, LFU, RFU에 대한 예제를 수행하고 어떤 일이 일어나는지보십시오.

다음 예제 programm (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. 업데이트 : 발신자가 장소를 사용한 후에 전략은 그것이 실패했는지 여부를 알려줍니다. 그런 다음 전략은 내부 데이터를 업데이트 할 수 있습니다. LFD 전략은 캐시 페이지의 거리를 다시 계산 해야하는 반면 전략 LFU 는 캐시 페이지의 히트 빈도를 예를 들어 업데이트해야합니다.

이제 5 가지 전략에 대한 예제 구현을 살펴보십시오.

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는 단지 페이지가 캐시에 얼마나 오래 있는지 (그리고 물론 다른 페이지들에 비례하여) 정보를 필요로합니다. 그래서해야 할 유일한 일은 놓치기를 기다린 다음 페이지를 만드는 것입니다. 위의 예에서 프로그램 솔루션은 다음과 같습니다.

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 의 경우 전략은 캐시 페이지에있는 것과 독립적이며, 그 유일한 관심은 마지막 사용법입니다. programm 결과는 다음과 같습니다.

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 는 페이지 사용 빈도를 최소화합니다. 따라서 업데이트 전략은 모든 액세스를 계산하는 것입니다. 물론 카운트를 놓친 후에 카운트가 리셋됩니다. 프로그램 결과는 다음과 같습니다.

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 는 실제로 제시된 다섯 가지 전략 중 유일하게 최적의 전략입니다. 증거는 다소 길며 여기 또는 Jon Kleinberg와 Eva Tardos의 책에서 찾을 수 있습니다 (아래의 참고 자료 참조).

알고리즘 대 현실

LFD 전략은 최적이지만 큰 문제가 있습니다. 그것의 최적의 오프라인 솔루션입니다. 실습에서 캐싱은 대개 온라인 문제입니다. 즉, 다음 번에 특정 항목이 필요할 때 사용할 수 없으므로 전략이 쓸모 없다는 의미입니다. 나머지 네 가지 전략은 온라인 전략이기도 합니다 . 온라인 문제에 대해서는 일반적으로 다른 접근 방식이 필요합니다.