Python LRU Cache Implementation

Last update on April 17 2025 13:00:06 (UTC/GMT +8 hours)

12. Caching System with LRU Eviction

Write a Python program to create a caching system with support for LRU eviction policy.

The problem entails designing and implementing a caching system that incorporates support for the Least Recently Used (LRU) eviction policy. This entails storing recently accessed items in the cache and evicting the least recently used items when the cache reaches its maximum capacity. The solution should include data structures and algorithms to efficiently manage the cache, track access frequencies, and evict items based on the LRU policy. This caching system can enhance performance by storing frequently accessed data in memory, reducing the need to fetch it from slower storage mediums.

Sample Solution:

Python Code :

from collections import OrderedDict

# Define a class for the caching system with LRU eviction policy
class LRUCache:
    # Initialize the cache with a maximum capacity
    def __init__(self, capacity):
        self.capacity = capacity  # Set the maximum capacity
        self.cache = OrderedDict()  # Use OrderedDict for O(1) access and ordering

    # Get the value associated with the key from the cache
    def get(self, key):
        # If the key is not in the cache, return -1
        if key not in self.cache:
            return -1
        # Move the accessed key to the end to indicate recent use
        self.cache.move_to_end(key)
        # Return the value associated with the key
        return self.cache[key]

    # Put a key-value pair into the cache
    def put(self, key, value):
        # If the key is already in the cache, update its value and move it to the end
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
        else:
            # If the cache is at capacity, remove the least recently used item
            if len(self.cache) == self.capacity:
                self.cache.popitem(last=False)  # Remove the first item (least recently used)
            # Add the new key-value pair to the cache
            self.cache[key] = value

# Example usage
if __name__ == "__main__":
    # Create a cache with a capacity of 2
    cache = LRUCache(2)
    # Put key-value pairs into the cache
    cache.put(1, 1)
    cache.put(2, 2)
    # Retrieve and print the value associated with key 1 (should be 1)
    print(cache.get(1))
    # Put a new key-value pair into the cache (evicting key 2)
    cache.put(3, 3)
    # Retrieve and print the value associated with key 2 (should be -1, as it was evicted)
    print(cache.get(2))
    # Retrieve and print the value associated with key 3 (should be 3)
    print(cache.get(3))

Output:

1
-1
3

Explanation:

Importing libraries:
from collections import OrderedDict: Used to create an ordered dictionary for the cache, maintaining the insertion order of items.
LRUCache Class Definition:
Initialization (__init__): Initializes the cache with a specified capacity and an empty ordered dictionary.
Getting Items (get): Retrieves the value associated with a key from the cache. If the key exists, it moves it to the end of the cache to indicate recent use.
Putting Items (put): Adds a new key-value pair to the cache. If the cache is at capacity, it evicts the least recently used item before adding the new item.
Example usage:
Creates an instance of 'LRUCache' with a capacity of 2 and performs various operations (putting and getting items) to demonstrate the LRU eviction policy.

For more Practice: Solve these Related Problems:

Write a Python program to implement an LRU cache decorator using OrderedDict to cache function outputs.
Write a Python program to build a custom caching system with an LRU eviction policy using a doubly-linked list and hash map.
Write a Python program to create a thread-safe LRU cache class that stores computed results and evicts the least recently used items.
Write a Python program to implement an LRU cache that automatically removes the least accessed items when the cache exceeds its capacity.

Go to:

Previous: Asyncio Concurrent Task Scheduler Implementation in Python.
Next: Asyncio Concurrent Task Scheduler Implementation in Python

Python Code Editor :

Have another way to solve this solution? Contribute your code (and comments) through Disqus.