LRU හැඹිලි ක්‍රියාත්මක කිරීම  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance ප්රාග්ධන එක් සිස්කෝ සිටඩෙල් සහජීවනය ක ru ස් ස්වයංක්‍රීයකරණය නාමාවලි එකක් ඊ බේ Expedia ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් මයික්රොසොෆ්ට් නූටනික්ස් ඔරකල් පේපෑල් Pinterest Salesforce Snapchat ටෙස්ලා ට්රිලිලියෝ Uber VMware වෝල්මාර්ට් ලැබ් ප්‍රාර්ථනා කරන්න සිලෝව්
නිර්මාණ මෙහෙයුම් පද්ධති

අවම වශයෙන් මෑතකදී භාවිතා කළ (LRU) හැඹිලිය යනු දත්ත නඩත්තු කිරීම සඳහා භාවිතා කරන ක්‍රමයක් වන අතර එමඟින් දත්ත භාවිතා කිරීමට ගතවන කාලය අවම විය හැකිය. හැඹිලිය පිරී ඇති විට LRU ඇල්ගොරිතම භාවිතා කරයි. පද්ධතියේ හැඹිලි මතකයෙන් අවම වශයෙන් මෑතකදී භාවිතා කළ දත්ත අපි ඉවත් කරමු. හැඹිලි මතකයේ ප්‍රමාණය සහ අප යොමු කළ යුතු පිටු ලබා දී ඇති මෙය ඉතා සිත්ගන්නාසුලු ගැටලුවකි. අපි දත්ත a ලැයිස්තුව දත්ත දැනටමත් තිබේ නම් එහි පිහිටීම වෙනස් කර එම මූලද්‍රව්‍යය ලැයිස්තුවේ ඉදිරියෙන් තබන්න. නැතිනම් ලැයිස්තුවට ඉදිරියෙන් දත්ත එක් කරන්න.

LRU හැඹිලිය සඳහා පැහැදිලි කිරීම  

LRU හැඹිලි ක්‍රියාත්මක කිරීම පිළිබඳ ඉක්මන් අවබෝධයක් පහත උදාහරණයෙන් බලමු- හැඹිලි මතකයේ සඳහන් කළ යුතු පිටු ගණන 3, 5, 6, 1, 3, 7, 1 වේ.

LRU හැඹිලි ක්‍රියාත්මක කිරීමපින්

 

LRU හැඹිලි ක්‍රියාත්මක කිරීමපින්

LRU හැඹිලි ක්‍රියාත්මක කිරීමපින්

LRU හැඹිලි ක්‍රියාත්මක කිරීමපින්

LRU හැඹිලි ක්‍රියාත්මක කිරීමපින්

පින්

පින්

පින්

සටහන: මෙන්න අපට පිටු 5 ක් තුළ පිටු 2 ක දෝෂයක් සහ පිටු XNUMX ක පහරක් ලැබුණි.

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

කාල සංකීර්ණත්වය  

ඕ (එස් * එන්) මෙහි S යනු හැඹිලියේ ප්‍රමාණය වන අතර N යනු අපට යොමු කිරීමට අවශ්‍ය පිටු ගණනයි. සෑම පිටුවක් සඳහාම, එය තිබේද නැද්ද යන්න අපි පරීක්ෂා කරමු. පිටු පහරක් සිදුවුවහොත් ඉවත් කිරීමේ ශ්‍රිතය භාවිතා කරන්න. පිටු දෝෂයක් සිදුවුවහොත් පොප්_ෆ්‍රන්ට් ඕ (1) හි පළමු අංගය ඉවත් කරයි. O (1) හි ලැයිස්තුව අවසානයේ පිටුව ඇතුළු කිරීම සඳහා.

මෙයද බලන්න
සංගීත මාරුව ලීට් කේතය සිදු කරන්න

ආශ්රිත