Mastering LRU Cache: Efficient Memory Management Techniques
Written on
Chapter 1: Introduction to LRU Caches
Least Recently Used (LRU) caches serve to enhance the speed of data access for frequently used items. By retaining these items in a cache, the need to fetch them from slower storage options, like databases or file systems, is minimized, leading to a noticeable improvement in application performance.
When can LRU caches be applied?
- Memory Management: LRU caches effectively manage memory by maintaining a fixed capacity. Once full, they evict the least recently accessed items to make space for new entries, thus preventing excessive memory consumption while ensuring frequently used data remains accessible.
- Algorithm Optimization: This structure often forms the basis for more complex caching systems. Variants of LRU, such as Most Recently Used (MRU), can be adapted for specific requirements.
- Data Preprocessing: LRU caches can optimize data preprocessing tasks. For instance, in image processing, costly operations like resizing can be cached to avoid repeated calculations.
- Database Query Result Caching: In database environments, LRU caches are frequently utilized to store results from commonly executed queries, which alleviates the database load and accelerates response times.
- Content Delivery: Content delivery networks (CDNs) and proxy servers implement LRU caches to store frequently requested web assets, reducing the latency of web page delivery.
- Resource Management in Operating Systems: The principles of LRU caching are integral to operating systems for managing memory and page replacement strategies.
Chapter 2: Technical Insights into LRU Cache
Pro vs. Hard Coding Interview Problem - LRU Cache (LeetCode Day 24): This video delves into the intricacies of the LRU cache, discussing its implementation and common interview scenarios.
Under the hood, an LRU cache is a node-based structure that blends a hash map with a doubly linked list. The least recently used node is located at the right end, while the most recently used node is at the left.
The magic lies in utilizing a HashMap<K, V>, where V represents nodes in the linked list. This design allows for quick access to nodes, and since most linked list operations run in O(1) time, it results in an efficient structure without the need for iteration.
Section 2.1: Accessing Values in LRU Cache
In this section, we explore the efficiency of accessing values with a time complexity of O(1).
To illustrate:
- Setting the next node of 2 to 4 and the previous node of 4 to 2 involves two operations.
- Disconnecting node 3 requires two more operations.
- Finally, re-linking node 3 to the head adds three additional operations.
This sums up to seven operations in total.
Subsection 2.1.1: LRU Cache Implementation
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
def __repr__(self):
return f"Key: {self.key}, Value: {self.value}"
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache: dict[int, ListNode] = {}
self.head = None
self.tail = None
self.length = 0
def _add_node(self, node):
self.length += 1
if self.head is None:
self.head = self.tail = node
return
node.next = self.head
self.head.prev = node
self.head = node
def _remove_node(self, node):
self.length = max(0, self.length - 1)
if self.length == 0:
self.head = self.tail = None
return
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
if node == self.head:
self.head = node.next
if node == self.tail:
self.tail = node.prev
node.prev = None
node.next = None
def _move_to_head(self, node):
self._remove_node(node)
self._add_node(node)
def _pop_tail(self):
tail_node = self.tail
self._remove_node(tail_node)
return tail_node
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._move_to_head(node)
return node.value
return -1
def put(self, key, value):
if key in self.cache:
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
if len(self.cache) == self.capacity:
tail_node = self._pop_tail()
del self.cache[tail_node.key]
new_node = ListNode(key, value)
self.cache[key] = new_node
self._add_node(new_node)
def __repr__(self):
current = self.head
nodes = []
while current:
nodes.append(str(current))
current = current.next
return " -> ".join(nodes)
To demonstrate the functionality, we will create a small cache and test its operations.
# Initialize an LRUCache with a capacity of 2
cache = LRUCache(2)
# Insert key-value pairs
cache.put(1, 1)
cache.put(2, 2)
print(cache) # Output: Key: 2, Value: 2 -> Key: 1, Value: 1
# Fetch values from the cache
print(cache.get(1)) # Output: 1
print(cache) # Output: Key: 1, Value: 1 -> Key: 2, Value: 2
# Adding another key-value pair exceeds capacity, triggering eviction of the least recently used key (2)
cache.put(3, 3)
# Attempt to access the evicted key
print(cache.get(2)) # Output: -1
# Insert another key-value pair, evicting the least recently used key (1)
cache.put(4, 4)
# Access remaining keys
print(cache.get(1)) # Output: -1
print(cache.get(3)) # Output: 3
print(cache.get(4)) # Output: 4
# Display the current state of the cache
print(cache) # Output: Key: 4, Value: 4 -> Key: 3, Value: 3
Chapter 3: Practical Applications of LRU Cache
LeetCode 146. LRU Cache (Algorithm Explained): This video provides a thorough explanation of the LRU Cache algorithm, exploring its applications and implementation details.