Skip to main content

LRU Cache Implementation

LRU (Least Recently Used) cache is a type of cache that is used to store the most recently used data items or objects. It operates on the principle that items that have been used recently are more likely to be used again than items that have not been used for a long time.

In an LRU cache, the least recently used items are removed when the cache is full and new items need to be added. This is done to ensure that the cache always contains the most useful and frequently used data items, thereby improving the overall performance of the system.

Here given code implementation process.

import java.util.ArrayList;
/*
    Java Program for
    LRU Cache Implementation
*/
public class LRU
{
    public ArrayList < Integer > record;
    public int size;
    public int pageHit;
    public int pageFaults;
    public LRU(int size)
    {
        this.size = size;
        this.pageFaults = 0;
        this.pageHit = 0;
        this.record = new ArrayList < Integer > ();
    }
    public void refer(int page)
    {
        if (this.record.contains(page) == false)
        {
            this.pageFaults++;
        }
        if (this.record.contains(page))
        {
            this.pageHit++;
            // When given page alredy exist
            // So we need to remove it
            this.record.remove(new Integer(page));
        }
        else if (this.record.size() == this.size)
        {
            // In case record size is full so remove first element
            this.record.remove(0);
        }
        // Add new node at the last
        this.record.add(page);
    }
    public static void main(String[] args)
    {
        LRU cache = new LRU(4);
        // Page value
        int[] page = {
            6 , 2 , 4 , 2 , 1 , 3 , 2 , 5 , 1 , 3
        };
        // Get number of elements
        int n = page.length;
        for (int i = 0; i < n; ++i)
        {
            cache.refer(page[i]);
        }
        System.out.print("\n Cache Value : ");
        // Display cache value
        for (int i = 0; i < cache.record.size(); ++i)
        {
            System.out.print("  " + cache.record.get(i));
        }
        System.out.print("\n Page Hit : " + cache.pageHit);
        System.out.println("\n Page Faults : " + cache.pageFaults);
    }
}

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
// Include header file
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
/*
    C++ Program for
    LRU Cache Implementation
*/
class LRU
{
    public: 
    vector < int > record;
    int size;
    int pageHit;
    int pageFaults;
    LRU(int size)
    {
        this->size = size;
        this->pageFaults = 0;
        this->pageHit = 0;
    }
    void refer(int page)
    {
        if (find(this->record.begin(), this->record.end(), page) == 
            this->record.end())
        {
            this->pageFaults++;
        }
        if (find(this->record.begin(), 
                 this->record.end(), page) != this->record.end())
        {
            this->pageHit++;
            // When given page alredy exist
            // So we need to remove it
            this->record.erase(
              remove(this->record.begin(), 
                     this->record.end(), page), 
              this->record.end());
        }
        else if (this->record.size() == this->size)
        {
            // In case record size is full so remove first element
            this->record.erase(this->record.begin() + 0 - 1);
        }
        // Add new node at the last
        this->record.push_back(page);
    }
};
int main()
{
    LRU *cache = new LRU(4);
    // Page value
    int page[] = {
        6 , 2 , 4 , 2 , 1 , 3 , 2 , 5 , 1 , 3
    };
    // Get number of elements
    int n = sizeof(page) / sizeof(page[0]);
    for (int i = 0; i < n; ++i)
    {
        cache->refer(page[i]);
    }
    cout << "\n Cache Value : ";
    // Display cache value
    for (int i = 0; i < cache->record.size(); ++i)
    {
        cout << "  " << cache->record.at(i);
    }
    cout << "\n Page Hit : " << cache->pageHit;
    cout << "\n Page Faults : " << cache->pageFaults << endl;
    return 0;
}

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program for
    LRU Cache Implementation
*/
public class LRU
{
    public List < int > record;
    public int size;
    public int pageHit;
    public int pageFaults;
    public LRU(int size)
    {
        this.size = size;
        this.pageFaults = 0;
        this.pageHit = 0;
        this.record = new List < int > ();
    }
    public void refer(int page)
    {
        if (this.record.Contains(page) == false)
        {
            this.pageFaults++;
        }
        if (this.record.Contains(page))
        {
            this.pageHit++;
            // When given page alredy exist
            // So we need to remove it
            this.record.Remove(page);
        }
        else if (this.record.Count == this.size)
        {
            // In case record size is full so remove first element
            this.record.RemoveAt(0);
        }
        // Add new node at the last
        this.record.Add(page);
    }
    public static void Main(String[] args)
    {
        LRU cache = new LRU(4);
        // Page value
        int[] page = {
            6 , 2 , 4 , 2 , 1 , 3 , 2 , 5 , 1 , 3
        };
        // Get number of elements
        int n = page.Length;
        for (int i = 0; i < n; ++i)
        {
            cache.refer(page[i]);
        }
        Console.Write("\n Cache Value : ");
        // Display cache value
        for (int i = 0; i < cache.record.Count; ++i)
        {
            Console.Write("  " + cache.record[i]);
        }
        Console.Write("\n Page Hit : " + cache.pageHit);
        Console.WriteLine("\n Page Faults : " + cache.pageFaults);
    }
}

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
<?php
/*
    Php Program for
    LRU Cache Implementation
*/
class LRU
{
    public $record;
    public $size;
    public $pageHit;
    public $pageFaults;
    public function __construct($size)
    {
        $this->size = $size;
        $this->pageFaults = 0;
        $this->pageHit = 0;
        $this->record = array();
    }
    public function refer($page)
    {
        if (!in_array($page, $this->record))
        {
            $this->pageFaults++;
        }
        if (in_array($page, $this->record))
        {
            $this->pageHit++;
            // When given page alredy exist
            // So we need to remove it
            if (($key = array_search($page, $this->record)) !== false)
            {
                array_splice($this->record, $key, 1);
            }
        }
        else if (count($this->record) == $this->size)
        {
            // In case record size is full so remove first element
            array_splice($this->record, 0, 1);
        }
        // Add new node at the last
        $this->record[] = $page;
    }
}

function main()
{
    $cache = new LRU(4);
    // Page value
    $page = array(6, 2, 4, 2, 1, 3, 2, 5, 1, 3);
    // Get number of elements
    $n = count($page);
    for ($i = 0; $i < $n; ++$i)
    {
        $cache->refer($page[$i]);
    }
    echo("\n Cache Value : ");
    // Display cache value
    for ($i = 0; $i < count($cache->record); ++$i)
    {
        echo("  ".$cache->record[$i]);
    }
    echo("\n Page Hit : ".$cache->pageHit);
    echo("\n Page Faults : ".$cache->pageFaults.
        "\n");
}
main();

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
/*
    Node JS Program for
    LRU Cache Implementation
*/
class LRU
{
    constructor(size)
    {
        this.size = size;
        this.pageFaults = 0;
        this.pageHit = 0;
        this.record = [];
    }
    refer(page)
    {
        if (!this.record.includes(page))
        {
            this.pageFaults++;
        }
        if (this.record.includes(page))
        {
            this.pageHit++;
            // When given page alredy exist
            // So we need to remove it
            var index = this.record.indexOf(page);
            if (index !== -1) {
              this.record.splice(index, 1);
            }
        }
        else if (this.record.length == this.size)
        {
            // In case record size is full so remove first element
            this.record.splice(0, 1);
        }
        // Add new node at the last
        this.record.push(page);
    }
}

function main()
{
    var cache = new LRU(4);
    // Page value
    var page = [6, 2, 4, 2, 1, 3, 2, 5, 1, 3];
    // Get number of elements
    var n = page.length;
    for (var i = 0; i < n; ++i)
    {
        cache.refer(page[i]);
    }
    process.stdout.write("\n Cache Value : ");
    // Display cache value
    for (var i = 0; i < cache.record.length; ++i)
    {
        process.stdout.write("  " + cache.record[i]);
    }
    process.stdout.write("\n Page Hit : " + cache.pageHit);
    console.log("\n Page Faults : " + cache.pageFaults);
}
main();

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
#    Python 3 Program for
#    LRU Cache Implementation
class LRU :
    def __init__(self, size) :
        self.size = size
        self.pageFaults = 0
        self.pageHit = 0
        self.record = []
    
    def refer(self, page) :
        if (page not in self.record) :
            self.pageFaults += 1
        
        if (page in self.record) :
            self.pageHit += 1
            #  When given page alredy exist
            #  So we need to remove it
            self.record.remove(page)
        elif (len(self.record) == self.size) :
            #  In case record size is full so remove first element
            del self.record[0]
        
        #  Add new node at the last
        self.record.append(page)
    

def main() :
    cache = LRU(4)
    #  Page value
    page = [6, 2, 4, 2, 1, 3, 2, 5, 1, 3]
    #  Get number of elements
    n = len(page)
    i = 0
    while (i < n) :
        cache.refer(page[i])
        i += 1
    
    print("\n Cache Value : ", end = "")
    i = 0
    #  Display cache value
    while (i < len(cache.record)) :
        print("  ", cache.record[i], end = "")
        i += 1
    
    print("\n Page Hit : ", cache.pageHit, end = "")
    print("\n Page Faults : ", cache.pageFaults)

if __name__ == "__main__": main()

Output

 Cache Value :    2   5   1   3
 Page Hit :  4
 Page Faults :  6
#    Ruby Program for
#    LRU Cache Implementation
class LRU 
    # Define the accessor and reader of class LRU
    attr_reader :record, :size, :pageHit, :pageFaults
    attr_accessor :record, :size, :pageHit, :pageFaults
    def initialize(size) 
        self.size = size
        self.pageFaults = 0
        self.pageHit = 0
        self.record = []
    end

    def refer(page) 
        if (!self.record.include?page) 
            self.pageFaults += 1
        end

        if (self.record.include?page) 
            self.pageHit += 1
            #  When given page alredy exist
            #  So we need to remove it
            self.record.delete(page)
        elsif (self.record.length == self.size) 
            #  In case record size is full so remove first element
            self.record.delete_at(0)
        end

        #  Add new node at the last
        self.record.push(page)
    end

end

def main() 
    cache = LRU.new(4)
    #  Page value
    page = [6, 2, 4, 2, 1, 3, 2, 5, 1, 3]
    #  Get number of elements
    n = page.length
    i = 0
    while (i < n) 
        cache.refer(page[i])
        i += 1
    end

    print("\n Cache Value : ")
    i = 0
    #  Display cache value
    while (i < cache.record.length) 
        print("  ", cache.record[i])
        i += 1
    end

    print("\n Page Hit : ", cache.pageHit)
    print("\n Page Faults : ", cache.pageFaults, "\n")
end

main()

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6

import scala.collection.mutable._;
/*
    Scala Program for
    LRU Cache Implementation
*/
class LRU(var record: ArrayBuffer[Int],
    var size: Int,
        var pageHit: Int,
            var pageFaults: Int)
{
    def this(size: Int)
    {
        this(new ArrayBuffer[Int](),size,0,0);
    }
    def refer(page: Int): Unit = {
        if (!this.record.contains(page))
        {
            this.pageFaults += 1;
        }
        if (this.record.contains(page))
        {
            this.pageHit += 1;
            // When given page alredy exist
            // So we need to remove it
            this.record -= page;
        }
        else if (this.record.size == this.size)
        {
            // In case record size is full so remove first element
            this.record.remove(0);
        }
        // Add new node at the last
        this.record += page;
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var cache: LRU = new LRU(4);
        // Page value
        var page: Array[Int] = Array(6, 2, 4, 2, 1, 3, 2, 5, 1, 3);
        // Get number of elements
        var n: Int = page.length;
        var i: Int = 0;
        while (i < n)
        {
            cache.refer(page(i));
            i += 1;
        }
        print("\n Cache Value : ");
        i = 0;
        // Display cache value
        while (i < cache.record.size)
        {
            print("  " + cache.record(i));
            i += 1;
        }
        print("\n Page Hit : " + cache.pageHit);
        println("\n Page Faults : " + cache.pageFaults);
    }
}

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
/*
    Kotlin Program for
    LRU Cache Implementation
*/
class LRU
{
    var record: MutableList < Int > ;
    var size: Int;
    var pageHit: Int;
    var pageFaults: Int;
    constructor(size: Int)
    {
        this.size = size;
        this.pageFaults = 0;
        this.pageHit = 0;
        this.record = mutableListOf < Int > ();
    }
    fun refer(page: Int): Unit
    {
        if (!this.record.contains(page))
        {
            this.pageFaults += 1;
        }
        if (this.record.contains(page))
        {
            this.pageHit += 1;
            // When given page alredy exist
            // So we need to remove it
            this.record.remove(page);
        }
        else if (this.record.size == this.size)
        {
            // In case record size is full so remove first element
            this.record.removeAt(0);
        }
        // Add new node at the last
        this.record.add(page);
    }
}
fun main(args: Array < String > ): Unit
{
    val cache: LRU = LRU(4);
    // Page value
    val page: Array < Int > = arrayOf(6, 2, 4, 2, 1, 3, 2, 5, 1, 3);
    // Get number of elements
    val n: Int = page.count();
    var i: Int = 0;
    while (i < n)
    {
        cache.refer(page[i]);
        i += 1;
    }
    print("\n Cache Value : ");
    i = 0;
    // Display cache value
    while (i < cache.record.size)
    {
        print("  " + cache.record[i]);
        i += 1;
    }
    print("\n Page Hit : " + cache.pageHit);
    println("\n Page Faults : " + cache.pageFaults);
}

Output

 Cache Value :   2  5  1  3
 Page Hit : 4
 Page Faults : 6
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment