এলআরইউ ক্যাশে বাস্তবায়ন  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ByteDance ক্যাপিটাল ওয়ান সিসকো দুর্গ সংহতি ক্রুজ অটোমেশন ড্রপবক্স ইবে এক্সপিডিয়া ফেসবুক গোল্ডম্যান শ্যাস গুগল মাইক্রোসফট Nutanix আকাশবাণী পেপ্যাল পিন্টারেস্ট বিক্রয় বল Snapchat টেসলা Twilio উবার অথবা VMware ওয়ালমার্ট ল্যাব কামনা Zillow
নকশা অপারেটিং সিস্টেম

সর্বনিম্ন ব্যবহৃত ব্যবহৃত (LRU) ক্যাশে এমন এক পদ্ধতি যা ডেটা বজায় রাখতে ব্যবহৃত হয় যাতে ডেটা ব্যবহারের জন্য প্রয়োজনীয় সময়টি সর্বনিম্ন সম্ভব হয়। ক্যাশে পূর্ণ হলে LRU অ্যালগরিদম ব্যবহার করা হয়। আমরা সিস্টেমের ক্যাশে মেমরি থেকে সম্প্রতি ব্যবহৃত ডেটা সরিয়ে ফেলি। এটি এত উত্তেজনাপূর্ণ সমস্যা যেখানে ক্যাশে মেমরির আকার এবং আমাদের যে পৃষ্ঠাগুলি উল্লেখ করতে হবে তা দেওয়া হয়েছে। আমরা একটিতে ডেটা যুক্ত করি তালিকা যেমন যদি ডেটা ইতিমধ্যে উপস্থিত থাকে তবে তার অবস্থান পরিবর্তন করুন এবং সেই উপাদানটিকে তালিকার সামনে রাখুন। অন্যথায় তালিকার সামনে ডেটা যুক্ত করুন।

এলআরইউ ক্যাশের জন্য ব্যাখ্যা  

আসুন নীচের উদাহরণটি দেখে এলআরইউ ক্যাশে বাস্তবায়নের জন্য একটি দ্রুত বোঝা যাক- ক্যাশে স্মৃতিতে আমাদের যে পৃষ্ঠাগুলির উল্লেখ করতে হবে তার সংখ্যা 3, 5, 6, 1, 3, 7, 1।

এলআরইউ ক্যাশে বাস্তবায়নপিন

 

এলআরইউ ক্যাশে বাস্তবায়নপিন

এলআরইউ ক্যাশে বাস্তবায়নপিন

এলআরইউ ক্যাশে বাস্তবায়নপিন

এলআরইউ ক্যাশে বাস্তবায়নপিন

পিন

পিন

পিন

বিঃদ্রঃ: পৃষ্ঠা রেফারির সময় আমরা এখানে 5-পৃষ্ঠার ত্রুটি এবং 2-পৃষ্ঠার হিট পেয়েছি।

এলআরইউ ক্যাশে বাস্তবায়নের জন্য বাস্তবায়ন  

/*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

সময় জটিলতা  

ও (এস * এন) যেখানে এস হ'ল ক্যাশের আকার এবং N হল সেই পৃষ্ঠাগুলির সংখ্যা যা আমরা উল্লেখ করতে চাই। প্রতিটি পৃষ্ঠার জন্য, আমরা এটি উপস্থিত কিনা তা যাচাই করি। যদি পৃষ্ঠা হিট হয় তবে মুছে ফাংশনটি ব্যবহার করুন যা সময় জটিলতা হ'ল (এস)। যদি কোনও পৃষ্ঠার ত্রুটি দেখা দেয় তবে পপ_ফ্রন্ট ও (1) এর প্রথম উপাদানটি সরিয়ে ফেলবে। ও (1) এর তালিকা শেষে পৃষ্ঠাটি সন্নিবেশ করানোর জন্য।

আরো দেখুন
স্ট্রিং শিফটগুলি লেটকোড সম্পাদন করুন

তথ্যসূত্র