LRU क्यास कार्यान्वयन  


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स राजधानी एक सिस्को Citadel एकता क्रूज स्वचालन ड्रपबक्स eBay Expedia फेसबुक Goldman सैक्स गुगल माइक्रोसफ्ट नुटानिक्स बजेट PayPal Pinterest SalesForce Snapchat tesla Twilio Uber VMware वालमार्ट ल्याबहरू इच्छा Zillow
डिजाइन सञ्चालन प्रणाली

हालसालै प्रयोग भएको (LRU) क्याच एक प्रकारको विधि हो जुन डाटा कायम राख्नको लागि प्रयोग गरिन्छ जस्तै डाटा प्रयोग गर्न आवश्यक समय न्यूनतम सम्भव हुन्छ। जब क्याच भरियो LRU एल्गोरिथ्म प्रयोग गरियो। हामीले प्रणालीको क्यास मेमोरीबाट भर्खरै प्रयोग गरिएको डाटा हटायौं। यो धेरै रोमाञ्चक समस्या हो जुन क्यास मेमोरीको आकार र पृष्ठहरू जुन हामीले सन्दर्भ गर्न आवश्यक छ। हामी डाटा एमा जोड्यौं सूची जस्तै यदि डाटा पहिले नै अवस्थित छ भने यसको स्थिति परिवर्तन गर्नुहोस् र त्यस तत्वलाई सूचीको अगाडि राख्नुहोस्। अन्यथा सूचीको अगाडि डाटा थप्नुहोस्।

LRU क्यासको लागि स्पष्टीकरण  

LRU क्यास कार्यान्वयनको लागि द्रुत समझ तलको उदाहरणबाट हेर्नुहोस्- पृष्ठहरूको संख्या जुन हामीले क्यास मेमोरीमा उल्लेख गर्नुपर्दछ 3, 5,,, १,,,,, १ हो।

LRU क्यास कार्यान्वयन

 

LRU क्यास कार्यान्वयन

LRU क्यास कार्यान्वयन

LRU क्यास कार्यान्वयन

LRU क्यास कार्यान्वयन

नोट: यहाँ हामीले--पृष्ठ गल्ती पायौं र पृष्ठ रेफरको क्रममा २-पृष्ठ हिट।

LRU क्यास कार्यान्वयनको लागि कार्यान्वयन  

/*C++ Implementation of LRU Cache*/ 
#include<bits/stdc++.h> 
using namespace std;
void LRU_Cache(int pages[],int cache_size,int total_page)
{
    int page_hit=0,page_fault=0;
    list<int> cache;
    for(int i=0;i<total_page;i++)
    {
        list<int>::iterator itr; 
        itr=find(cache.begin(),cache.end(),pages[i]);
        /*page is not present in cache memory*/
        if(itr==cache.end())
        {
            page_fault++;
            int rand_size=cache.size();
            /*if cache is full*/
            if(rand_size==cache_size)
            {
                /*remove the least recently used page from cache*/
                int pop_element=cache.front();
                cache.pop_front();
                /*push page at the end of cache*/
                cache.push_back(pages[i]);
            }
            else//cache is not full;
            {
               cache.push_back(pages[i]);   
            }
        }
        else//page is present in cache;
        {
            page_hit++;
            /*remove the page from previous location*/
            cache.remove(pages[i]);
            /*make the page to most recently used by inserting it at end of list*/
            cache .push_back(pages[i]);
        }
    }
    /*print the page hit and page fault*/
    cout<<"Page Hit: "<<page_hit<<" "<<"Page Fault: "<<page_fault<<endl;
    cout<<"Cache containg pages: ";
    for(auto itr:cache)
    {
        cout<<itr<<" ";
    }
    cout<<endl;
}
int main() 
{ 
    int cache_size,total_page;
    /*take input the size of cache and total pages count*/
    cin>>cache_size>>total_page;
    int pages[total_page];
    /*input the pages which we want to refer*/
    for(int i=0;i<total_page;i++)
    {
        cin>>pages[i];
    }
    /*call LRU_Cache*/
    LRU_Cache(pages,cache_size,total_page);
    return 0; 
}
4 7
3 5 6 1 3 7 1
Page Hit: 2 Page Fault: 5
Cache containg pages: 6 3 7 1

समय जटिलता  

O (S * N) जहाँ S क्यासको साइज हो र एन हामी सन्दर्भ गर्न चाहने पृष्ठहरूको संख्या हो। प्रत्येक पृष्ठको लागि हामी जाँच गर्छौं कि यो उपस्थित छ वा छैन। यदि पृष्ठ हिट भयो भने हटाउने प्रकार्य प्रयोग गर्नुहोस् जुन समयको जटिलता O (S) हो। यदि पृष्ठ त्रुटि देखा पर्दछ भने पप_ फ्रन्टले O (१) मा पहिलो तत्व हटाउनेछ। ओ (१) मा सूचीको अन्तमा पृष्ठ घुसाउनका लागि।

पनि हेर्नुहोस्
स्ट्रिंग शिफ्ट्स Leetcode प्रदर्शन गर्नुहोस्

सन्दर्भ