LRU Cache ကိုအကောင်အထည်ဖော်ခြင်း


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance Capital One Cisco သည် Citadel ပေါင်းစည်းမှု ခရုဇ် Automation Dropbox ကို ကို eBay Expedia Facebook က Goldman Sachs Google Microsoft က Nutanix Oracle က PayPal က Pinterest Salesforce Snapchat တက်စလာ Twilio Uber VMware က Walmart ဓာတ်ခွဲခန်းများ ဆုတောင်း Zillow
ပုံစံ လည်ပတ်မှုစနစ်များ

အနည်းဆုံးအသုံးပြုထားသော (LRU) Cache ဒေတာကိုအသုံးပြုရန်လိုအပ်သောအချိန်နိမ့်ဆုံးဖြစ်နိုင်သမျှထိုကဲ့သို့သောအချက်အလက်များကိုထိန်းသိမ်းရန်အသုံးပြုသည့်နည်းလမ်းတစ်ခုဖြစ်သည်။ LRU algorithm သည် cache ပြည့်နေသည့်အချိန်တွင်အသုံးပြုသည်။ ကျွန်ုပ်တို့သည်အနည်းဆုံးမကြာသေးမီကအသုံးပြုထားသောအချက်အလက်များကိုစနစ်၏ cache memory မှဖယ်ရှားသည်။ ၎င်းသည်အလွန်စိတ်လှုပ်ရှားဖွယ်ကောင်းသောပြproblemနာဖြစ်ပြီး Cache memory နှင့်ကျွန်ုပ်တို့ရည်ညွှန်းရန်လိုအပ်သောစာမျက်နှာများကိုပေးထားသည်။ ကျနော်တို့ကတစ် ဦး အတွက်ဒေတာထည့်ပါ စာရင်း ဒေတာရှိပြီးသားလျှင်၎င်း၏အနေအထားကိုပြောင်းလဲနှင့်စာရင်းများ၏ရှေ့မှောက်၌ထိုဒြပ်စင်ထားထိုကဲ့သို့သော။ အခြားအရာများကိုစာရင်း၏ရှေ့မှောက်၌ထည့်ပါ။

LRU Cache အတွက်ရှင်းလင်းချက်

အောက်ဖော်ပြပါဥပမာကိုကြည့်ခြင်းအားဖြင့် LRU Cache Implementation ကိုအလျင်အမြန်နားလည်နိုင်သည်။ ကြည့်ရှုရန်လိုအပ်သည့်စာမျက်နှာအရေအတွက်မှာ ၃၊ ၅၊ ၆၊ ၁၊ ၃၊ ၇၊ ၁ ဖြစ်သည်။

LRU Cache ကိုအကောင်အထည်ဖော်ခြင်း

 

LRU Cache ကိုအကောင်အထည်ဖော်ခြင်း

LRU Cache ကိုအကောင်အထည်ဖော်ခြင်း

LRU Cache ကိုအကောင်အထည်ဖော်ခြင်း

LRU Cache ကိုအကောင်အထည်ဖော်ခြင်း

မှတ်စု: ဤတွင်ကျွန်ုပ်တို့သည်စာမျက်နှာ ၅ မျက်နှာပြတ်တောက်မှုနှင့်စာမျက်နှာကိုရည်ညွှန်းစဉ် ၂ မျက်နှာထိမှန်ခြင်းတို့ဖြစ်ပွားခဲ့သည်။

LRU Cache ကိုအကောင်အထည်ဖော်ခြင်းအတွက်အကောင်အထည်ဖော်ခြင်း

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

အချိန်ရှုပ်ထွေး

အို (S * N) S သည် cache ၏အရွယ်အစားဖြစ်ပြီး N သည်ရည်ညွှန်းလိုသောစာမျက်နှာအရေအတွက်ဖြစ်သည်။ စာမျက်နှာတိုင်းအတွက်၊ အဲဒါရှိသလား၊ မစစ်ဆိုတာကျွန်တော်တို့စစ်ဆေးတယ်။ အကယ်၍ စာမျက်နှာထိမှန်လျှင်၊ (ရှုပ်ထွေးမှုသည် O (S) ဖြစ်သောအချိန်ဖယ်ကိုအသုံးပြုပါ။ စာမျက်နှာအမှားတစ်ခုဖြစ်ပေါ်လျှင် pop_front သည် O (1) တွင်ပထမဆုံး element ကိုဖယ်ရှားလိမ့်မည်။ အို (၁) တွင်စာရင်း၏အဆုံးမှာစာမျက်နှာကိုထည့်ရန်။

ကိုးကား