5 Best Ways to Implement Least Frequently Used (LFU) Cache in Python

πŸ’‘ Problem Formulation: Caching is a critical aspect of performance optimization in computing. LFU cache policies evict the least frequently accessed items to free up space for new items. For instance, given a cache capacity, one should be able to insert key-value pairs, retrieve values, and ensure the least used items are evicted first. A typical input could be a sequence of cache accesses, and the output would be the state of the cache after these accesses, showing evictions and insertions.

Method 1: Using a Custom Class

A custom Python class can be implemented to maintain a record of the usage frequency of cache items. This method involves storing each key with its frequency and the last time it was used. The class would provide methods to get, put, and evict items based on their frequency.

Here’s an example:

class LFUCache:

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        # Dictionary format: {key: (value, frequency, last_used_time)}
        
    def get(self, key):
        # Your code to retrieve and update frequency
        pass
        
    def put(self, key, value):
        # Your code to insert values and maintain frequencies
        pass

# Usage
lfu_cache = LFUCache(2)
lfu_cache.put(1, 'A')
lfu_cache.put(2, 'B')
print(lfu_cache.get(1))
lfu_cache.put(3, 'C')  # This will evict key 2 as it is least frequently used.

Output:

'A'

This LFU Cache class maintains a simple structure where each key in the dictionary is associated with a tuple containing the value, its frequency, and the time it was last accessed. A more sophisticated version would need methods that update these values accordingly and handle eviction when the capacity is reached.

Method 2: Using a Dictionary and Heap

This method takes advantage of Python’s heapq module to track usage frequency in a heap structure. The main advantage is efficient minimum frequency extraction. The dictionary maps keys to values and the heap maintains keys sorted by frequency.

Here’s an example:

import heapq

class LFUCache:
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.frequency_heap = []
        # Heap format: [(frequency, last_used_time, key)]
        
    # Methods for get, put and eviction using heapq
    # ...

# Usage
# Similar to Method 1

This code snippet shows the setup for using a heap alongside a dictionary to manage the LFU cache. Items would be added or updated in the cache and the corresponding operation performed on the heap to sort by frequency and last used time.

Method 3: Using Python’s collections.Counter and time Modules

Here, the Counter class tracks frequencies and the time module provides a timestamp for resolving ties. This method emphasizes simplicity and leverages Python’s standard library.

Here’s an example:

from collections import Counter
import time

class LFUCache:
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.frequency = Counter()
        
    # Methods for get, put and eviction
    # ...

# Usage
# Similar to Method 1

This implementation suggests using Python’s built-in Counter class to manage frequencies easily. The _get_ and _put_ methods would also utilize the time module for the last_used_time, and evict accordingly.

Method 4: Third-party Libraries

You can use third-party libraries like cachetools which offer out-of-the-box LFU cache implementations. This is a high-level approach that minimizes development effort while providing robust, tested features.

Here’s an example:

from cachetools import LFUCache

# Create a LFU cache object with a specific capacity
lfu_cache = LFUCache(maxsize=2)

# Use the cache to store and retrieve values
lfu_cache[1] = 'A'
lfu_cache[2] = 'B'
print(lfu_cache[1])  # Access to update frequency
lfu_cache[3] = 'C'   # Will evict key 2

Output:

'A'

This example shows how simple it is to use an LFU cache when going with a third-party library. The LFUCache from cachetools will take care of frequency and eviction logic internally so that developers can focus on the business logic.

Bonus One-Liner Method 5: Using a Function Decorator

Python decorators can be used for caching, and with a little creativity, can be extended to implement LFU behavior. This approach simplifies caching down to just a function annotation.

Here’s an example:

# A decorator function would be implemented to wrap and provide LFU caching
# ...

@lfu_cache_decorator
def get_data(key):
    # Function that fetches data (expensive operation)
    pass

The decorator named @lfu_cache_decorator would manage the caching mechanism. When the get_data function is called, it would utilize the cache to reduce the number of expensive data fetch operations based on LFU logic.

Summary/Discussion

  • Method 1: Custom Class. The DIY approach offers full control and customizability but requires more implementation effort and rigorous testing.
  • Method 2: Using Dictionary and Heap. Efficient minimum frequency extraction, but more complex to manage heap synchronization with the cache.
  • Method 3: Using Counter and time Modules. Leverages Python’s standard library, offering simplicity but may lack efficiency compared to specialized structures.
  • Method 4: Third-party Libraries. Quick and reliable at the cost of external dependencies and less customizability.
  • Bonus Method 5: Function Decorator. Ultra-convenient caching with minimal code changes required, although can be tricky to encapsulate full LFU logic cleanly in a decorator.