Python LRU Cache Implementation

Last update on December 21 2024 07:18:04 (UTC/GMT +8 hours)

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.

Python Code Editor :

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

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