LRU Cache Implementation: Optimizing Memory with Python Dictionary Tracking

Last update on April 10 2025 12:54:10 (UTC/GMT +8 hours)

88. Dictionary-based LRU Cache

Write a Python program to implement an LRU (Least Recently Used) cache using dictionaries. The cache should have a fixed capacity and remove the least recently used items when full. Implement get and put methods with O(1) time complexity.

Solution:

Python Code:

# Define a class for implementing an LRU (Least Recently Used) cache.
class LRUCache:
    """
    An LRU (Least Recently Used) cache implementation using dictionaries.
    Has a fixed capacity and removes the least recently used items when full.
    """
    # Initialize the LRU Cache with a specified capacity, an empty dictionary for storage, and an order counter.
    def __init__(self, capacity):
        self.capacity = capacity  # Maximum number of items the cache can hold.
        self.cache = {}  # Dictionary to store key-value pairs along with their access order: key -> (value, order).
        self.order = 0  # Counter to track the order in which items are accessed or added.

    # Define the behavior for retrieving a value from the cache.
    def get(self, key):
        """
        Get a value from the cache and update its access order.
        
        Returns:
            The value if found, otherwise -1
        """
        # If the key is not in the cache, return -1 to indicate it's not found.
        if key not in self.cache:
            return -1
        
        # Retrieve the value and its current access order from the cache.
        value, _ = self.cache[key]
        # Increment the global order counter and update the access order for this key.
        self.order += 1
        self.cache[key] = (value, self.order)
        
        # Return the value associated with the key.
        return value

    # Define the behavior for adding or updating a key-value pair in the cache.
    def put(self, key, value):
        """
        Add or update a key-value pair in the cache.
        If the cache is full, remove the least recently used item.
        """
        # Increment the global order counter to reflect this operation.
        self.order += 1
        
        # If the key already exists in the cache, update its value and access order.
        if key in self.cache:
            self.cache[key] = (value, self.order)
            return
        
        # If the cache has reached its capacity, remove the least recently used item.
        if len(self.cache) >= self.capacity:
            # Find the key with the smallest access order (least recently used).
            lru_key = min(self.cache.items(), key=lambda x: x[1][1])[0]
            # Remove the least recently used key from the cache.
            del self.cache[lru_key]
        
        # Add the new key-value pair to the cache with the current access order.
        self.cache[key] = (value, self.order)

# Example usage of LRU Cache

# Create an instance of LRUCache with a capacity of 2.
cache = LRUCache(2)  # Capacity is set to 2.

# Add key-value pairs to the cache.
cache.put(1, 1)  # Cache now contains {1: (1, 1)}.
cache.put(2, 2)  # Cache now contains {1: (1, 1), 2: (2, 2)}.

# Retrieve the value for key 1 and update its access order.
print(cache.get(1))  # Output: 1 (Cache now contains {2: (2, 2), 1: (1, 3)}).

# Add a new key-value pair, which evicts the least recently used item (key 2).
cache.put(3, 3)  # Cache now contains {1: (1, 3), 3: (3, 4)}.
print(cache.get(2))  # Output: -1 (Key 2 is not found).

# Retrieve the value for key 3 and update its access order.
print(cache.get(3))  # Output: 3 (Cache now contains {1: (1, 3), 3: (3, 5)}).

# Add another key-value pair, which evicts the least recently used item (key 1).
cache.put(4, 4)  # Cache now contains {3: (3, 5), 4: (4, 6)}.
print(cache.get(1))  # Output: -1 (Key 1 is not found).

# Retrieve the values for keys 3 and 4, updating their access orders.
print(cache.get(3))  # Output: 3 (Cache now contains {4: (4, 6), 3: (3, 7)}).
print(cache.get(4))  # Output: 4 (Cache now contains {3: (3, 7), 4: (4, 8)}).

Output:

Explanation of Each Line:

Class Definition : Defines the LRUCache class to implement an LRU (Least Recently Used) cache.
Docstring : Provides a description of the class and its functionality.
Initialization : Initializes the cache with a fixed capacity, an empty dictionary (self.cache), and an order counter (self.order) to track access order.
Get Method : Implements the get method to retrieve a value from the cache and update its access order.
Key Not Found Check : Checks if the requested key exists in the cache; returns -1 if not found.
Update Access Order : Retrieves the value and updates the access order for the key by incrementing the global order counter.
Return Value : Returns the value associated with the key after updating its access order.
Put Method : Implements the put method to add or update a key-value pair in the cache.
Increment Order Counter : Increments the global order counter to reflect the current operation.
Update Existing Key : If the key already exists, updates its value and access order without evicting any items.
Eviction Logic : If the cache exceeds its capacity, identifies and removes the least recently used item based on the access order.
Find Least Recently Used : Uses the min function to find the key with the smallest access order.
Remove LRU Key : Deletes the least recently used key from the cache.
Add New Item : Adds the new key-value pair to the cache with the current access order.
Example Usage : Demonstrates how to use the LRUCache class with example operations.
Create Cache Instance : Creates an LRUCache instance with a capacity of 2.
Add Key-Value Pairs : Adds key-value pairs to the cache.
Retrieve Value : Retrieves the value for a key and updates its access order.
Evict LRU Item : Adds a new key-value pair, evicting the least recently used item when the cache is full.
Check Evicted Key : Verifies that the evicted key is no longer in the cache.
Retrieve Values : Retrieves values for remaining keys, updating their access orders.

Explanation - Dictionary-based LRU Cache

Concept: Implement a Least Recently Used (LRU) cache with fixed capacity using dictionaries.
Challenge: Achieve O(1) time complexity for operations while tracking usage order.
Key Skills:
- Algorithm design
- Efficiency optimization
- Cache management techniques
Applications:

Browser caching
Database query caching
API response caching
Memoization with limited memory

Benefits:

Optimizes memory usage by removing least used items
Provides fast access to frequently used data
Balances memory constraints with performance needs

For more Practice: Solve these Related Problems:

Write a Python function to implement a dictionary-based LFU (Least Frequently Used) cache.
Write a Python program to implement an LRU cache with different expiration times for different types of data.
Write a Python function to implement an LRU cache that persists to disk when memory is full.
Write a Python function to create an LRU cache that supports time-based and frequency-based eviction strategies.

Python Code Editor:

Previous: Bidirectional Dictionary.
Next: Dictionary Serialization with Circular References.