algorithm
लालची तकनीक के अनुप्रयोग

टिप्पणियों

टिकट स्वचालित

पहला सरल उदाहरण:

आपके पास एक टिकट ऑटोमैटैट है जो 1, 2, 5, 10 और 20 के सिक्कों के साथ सिक्कों का आदान-प्रदान करता है। विनिमय का तनाव सिक्के की एक श्रृंखला के रूप में देखा जा सकता है जब तक कि सही मूल्य तिरस्कृत न हो। हम कहते हैं कि एक सिक्का इष्टतम है जब इसका सिक्का गिनती इसके मूल्य के लिए न्यूनतम है ।

M में [1,50] टिकट T और P लिए मूल्य है [1,50] में P >= M साथ किसी ने T लिए भुगतान किया गया धन। बता दें कि 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 में कम से कम रैखिक D/C ।
2. हर चरण में हमारा एल्गोरिदम स्थानीय इष्टतम चुनता है। लेकिन इस कि एल्गोरिथ्म वैश्विक इष्टतम समाधान (अधिक जानकारियां देख पाता है कहने के लिए पर्याप्त नहीं है यहाँ या की पुस्तक में लघु और Vygen )।

एक सरल काउंटर उदाहरण: सिक्के 1,3,4 और D=6 । इष्टतम समाधान स्पष्ट रूप से मूल्य 3 दो सिक्के हैं लेकिन लालची पहले चरण में 4 चुनता है इसलिए इसे चरण दो और तीन में 1 चुनना होगा। तो यह कोई इष्टतम soution देता है। इस उदाहरण के लिए एक संभावित इष्टतम एल्गोरिदम गतिशील प्रोग्रामिंग पर आधारित है।

अंतराल निर्धारण

हमारे पास नौकरियों का एक सेट है 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) में है। एक interested (एन लॉग एन) कार्यान्वयन है और इच्छुक पाठक नीचे पढ़ना जारी रख सकता है (जावा उदाहरण)।

अब हमारे पास अंतराल निर्धारण समस्या के लिए एक लालची एल्गोरिथ्म है, लेकिन क्या यह इष्टतम है?

प्रस्ताव: लालची एल्गोरिथ्म जल्द से जल्द खत्म होने का समय इष्टतम है।

प्रमाण: (विरोधाभास द्वारा)

मान लें कि लालची इष्टतम नहीं है और 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)] is jk=ik । r की अधिकतमता के विपरीत एक विरोधाभास है। यह प्रमाण को समाप्त करता है।

यह दूसरा उदाहरण दर्शाता है कि आमतौर पर कई संभावित लालची रणनीतियाँ हैं लेकिन केवल कुछ या किसी को भी हर उदाहरण में इष्टतम समाधान नहीं मिल सकता है।

नीचे एक जावा प्रोग्राम है जो Θ (एन लॉग एन) में चलता है

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 । हम सभी j लिए अक्षांश L=max{0,fj-dh} को परिभाषित करते हैं। लक्ष्य अधिकतम अक्षांश एल को कम करना है।

समाधान L=7 स्पष्ट रूप से इष्टतम नहीं है। कुछ लालची रणनीतियों को देखें:

1. सबसे कम प्रसंस्करण समय पहले : आरोही क्रम में अनुसूची नौकरी और प्रसंस्करण समय j`
2. सबसे पहले समय सीमा पहले : समय सीमा के क्रम में नौकरियों की अनुसूची dj
3. सबसे छोटा स्लैक : स्लैक dj-tj आरोही क्रम में जॉब

यह देखना आसान है कि सबसे कम प्रसंस्करण समय पहले इष्टतम नहीं है एक अच्छा काउंटर उदाहरण है

सबसे छोटे स्टैक समाधान में सिमिलर समस्याएं हैं

अंतिम रणनीति वैध लगती है इसलिए हम कुछ छद्म कोड के साथ शुरू करते हैं:

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]

और सी ++ में कार्यान्वयन के रूप में:

#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

एल्गोरिथ्म का रनटाइम स्पष्ट रूप से Θ (एन लॉग एन) है क्योंकि छंटनी इस एल्गोरिथ्म का वर्चस्व संचालन है। अब हमें यह दिखाने की जरूरत है कि यह इष्टतम है। स्पष्ट रूप से एक इष्टतम समय के लिए कोई निष्क्रिय समय नहीं है । सबसे पहले की समय सीमा पहले से निर्धारित समय से कम नहीं है।

मान लें कि नौकरियां गिने जा रही हैं ताकि d1<=d2<=...<=dn । हम कहते हैं कि शेड्यूल का उलटा i जॉब की एक जोड़ी है 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. पहले में, पहले बाहर (फीफो) : सबसे पुराना पेज बेदखल हो जाता है
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. अपडेट : कॉलर द्वारा जगह का उपयोग करने के बाद, यह रणनीति बताता है कि यह एक मिस था या नहीं। फिर रणनीति अपने आंतरिक डेटा को अपडेट कर सकती है। उदाहरण के लिए रणनीति 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

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 

लालची रणनीति एलएफडी वास्तव में प्रस्तुत पांच की एकमात्र इष्टतम रणनीति है। इसका प्रमाण अधिक लंबा है और यहां या जॉन क्लेनबर्ग और ईवा तारडोस की किताब में पाया जा सकता है (नीचे टिप्पणी में स्रोत देखें)।

एल्गोरिथम बनाम वास्तविकता

एलएफडी रणनीति इष्टतम है, लेकिन एक बड़ी समस्या है। इसका एक इष्टतम ऑफ़लाइन समाधान है। प्रैक्सिस कैशिंग में आमतौर पर एक ऑनलाइन समस्या है, इसका मतलब है कि रणनीति बेकार है क्योंकि हम अगली बार हमें किसी विशेष आइटम की आवश्यकता नहीं है। अन्य चार रणनीतियाँ भी ऑनलाइन रणनीतियाँ हैं। ऑनलाइन समस्याओं के लिए हमें एक अलग दृष्टिकोण की आवश्यकता है।