Least Recently Used implementation using Python

     The Least Recently Used (LRU) Cache is a powerful strategy for managing limited memory by evicting the least recently accessed items. It’s widely used across systems where performance and resource optimization are critical.

LRU -Least Recently Used. It is a cache which manages the less memory. Mainly, it handles the resource in optimize manner.

Example:

Let us consider a Web browser. It stores the recently visited pages, scripts and images.

Python implementation:

              It uses doubly Linked list for storing the data. The steps are given as follows…

  • Create a c_node class and initialise three values. c_self,c_key and c_value.
  • Make the previous and nest pointers as Null.
  • Write the code for LRUcache. It holds the capacity value.
  • let us create a Dummy head and tail nodes.
  • Insert the values to the cache.
  • Delete a value in the list.
  • Function ‘get()’ is used to get the value. ‘put’ function displays the value.
  • ‘main()’ function calls the function to get the output.

Program:

class c_Node:

    def __init__(c_self, c_key, c_value):

        c_self.c_key = c_key

        c_self.c_value = c_value

        c_self.prev = c_self.next = None

class LRUCache:

    def __init__(c_self, capa: int):

        c_self.capa = capa

        c_self.cache = {}  # key -> node

 

        # let us create a Dummy head and tail nodes

        c_self.head = c_Node(0, 0)

        c_self.tail = c_Node(0, 0)

        c_self.head.next = c_self.tail

        c_self.tail.prev = c_self.head

 

    def _remove(c_self, node):

        """Method to Remove the node from linked list."""

        prev, nxt = node.prev, node.next

        prev.next = nxt

        nxt.prev = prev

 

    def _add(c_self, node):

        """insert the node right before tail (MRU)."""

        prev = c_self.tail.prev

        prev.next = node

        node.prev = prev

        node.next = c_self.tail

        c_self.tail.prev = node

    def get(c_self, c_key: int) -> int:

        if c_key not in c_self.cache:

            return -1

        node = c_self.cache[c_key]

        c_self._remove(node)

        c_self._add(node)

        return node.c_value

 

    def put(c_self, c_key: int, c_value: int) -> None:

        if c_key in c_self.cache:

            c_self._remove(c_self.cache[key])

        node = c_Node(c_key, c_value)

        c_self._add(node)

        c_self.cache[c_key] = node

 

        if len(c_self.cache) > c_self.capa:

            # delete the least recently used node

            lru = c_self.head.next

            c_self._remove(lru)

            del c_self.cache[lru.c_key]

if __name__ == "__main__":

    lru = LRUCache(2)

    lru.put(1, 130)

    lru.put(2, 220)

    print("Get the key value of node1:", lru.get(1))  # Output: 130

    lru.put(3, 30)                  # Evicts the key 2

    print("Get the key value of node2:", lru.get(2))  # Output: -1 (because idt is evicted already)

    print("Get the key value of node3:", lru.get(3))  # Output: 30

Output:

C:\raji\blog>py LRUcache.py

Get the key value of node1: 130

Get the key value of node2: -1

Get the key value of node3: 30

Here, the python program to implment LRU using linked list is written efficiently.

Comments

Popular posts from this blog

How to create a XML DTD for displaying student details

How to write your first XML program?

Java NIO examples to illustrate channels and buffers.