implement lru cache in Python
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)
or
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))
Disclaimer
- License under
CC BY-NC 4.0
- Copyright issue feedback
me#imzye.me
, replace # with @ - Not all the commands and scripts are tested in production environment, use at your own risk
- No privacy information is collected here