implement lru cache in Python
To implement LRU cache in Python, you can use the OrderedDict data structure from the collections module.
Example 1
Here’s an example implementation:
from collections import OrderedDict
class LRUCache:
# initialising capacity
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
# we return the value of the key
# that is queried in O(1) and return -1 if we
# don't find the key in out dict / cache.
# And also move the key to the end
# to show that it was recently used.
def get(self, key: int) -> int:
if key not in self.cache:
return -1
else:
self.cache.move_to_end(key)
return self.cache[key]
# first, we add / update the key by conventional methods.
# And also move the key to the end to show that it was recently used.
# But here we will also check whether the length of our
# ordered dictionary has exceeded our capacity,
# If so we remove the first key (least recently used)
def put(self, key: int, value: int) -> None:
self.cache[key] = value
self.cache.move_to_end(key)
if len(self.cache) > self.capacity:
self.cache.popitem(last = False)
if __name__ == "__main__":
cache = LRUCache(3)
cache.put(1, 1)
print(cache.cache)
cache.put(2, 1)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.put(3, 3)
print(cache.cache)
cache.get(2)
print(cache.cache)
cache.put(4, 4)
print(cache.cache)
cache.get(1)
print(cache.cache)
cache.get(3)
print(cache.cache)
cache.get(4)
print(cache.cache)
In this implementation, LRUCache is a class that takes a capacity as an argument. The cache attribute is an OrderedDict object that will store the key-value pairs in the cache.
The get method returns the value associated with the given key, and moves the key to the end of the cache dictionary to indicate that it has been accessed recently.
The put method adds a new key-value pair to the cache, and also moves the key to the end of the dictionary. If the cache has exceeded its capacity, the least recently used item is removed from the cache using the popitem method.
Example 2
import collections
class ListNode:
def __init__(self, key, val):
self.val = val
self.key = key
self.next = None
self.prev = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert(self, node):
if self.head is None:
self.head = node
else:
self.tail.next = node
node.prev = self.tail
self.tail = node
def delete(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
del node
class LRUCache:
def __init__(self, capacity):
self.list = LinkedList()
self.dict = {}
self.capacity = capacity
def _insert(self, key, val):
node = ListNode(key, val)
self.list.insert(node)
self.dict[key] = node
def get(self, key):
if key in self.dict:
val = self.dict[key].val
self.list.delete(self.dict[key])
self._insert(key, val)
return val
return -1
def set(self, key, val):
if key in self.dict:
self.list.delete(self.dict[key])
elif len(self.dict) == self.capacity:
del self.dict[self.list.head.key]
self.list.delete(self.list.head)
self._insert(key, val)
class LRUCache2:
def __init__(self, capacity):
self.cache = collections.OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
val = self.cache[key]
del self.cache[key]
self.cache[key] = val
return val
def set(self, key, value):
if key in self.cache:
del self.cache[key]
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
if __name__ == "__main__":
cache = LRUCache(3)
# cache = LRUCache2(3)
cache.set(1, 1)
cache.set(2, 2)
cache.set(3, 3)
print(cache.get(1))
cache.set(4, 4)
print(cache.get(2))