LRU Cache

The least recently used cache is a caching mechanism which flushes the data from the cache which was least used (when the cache is full) to make up the space for new data to be pushed in the cache.

It’s used by memcache, page file replacement algorithms.. etc.

we can use a deque. We insert a new data to the front of this deque. This will take O(1) time.

If the deque reaches max capacity, we can delete the last node (rear) from the deque and insert the new one in the front. Again this takes O(1) time.

For retrieving value we’ll have to search the whole deque for the key. Which takes O(n) time. If we maintian a hash-map with key as hash-map key and value as deque node, we can retrive node in O(1) time.
This also helps in deleting *any node* with a particular key in O(1) time.

For retrieving , we need to remove the node from the deque and then add it to the front. Both operations will take O(1) time.

Here is the implementation:

class Node:
	def __init__(self, key, value):
		self.value = value = None
		self.prev = None
		self.key = key

class LRU:
	def __init__(self, capacity = 10):
		self.capacity = capacity
		self.cache = {}
		self.front = None
		self.rear = None

	def set(self, key, value):
		new_node = Node(key, value)

		if len(self.cache) <  self.capacity:
			self.cache[key] = new_node 

			last_key = self.delete_last()
			del self.cache[last_key]
			self.cache[key] = new_node

	def get(self, key):
		if key in self.cache:

			return self.cache[key].value
			return -1 

	def _add_front(self, new_node):
		if self.front == None:
			self.front = new_node
			self.rear = new_node
			self.front.prev = new_node = self.front
			self.front= new_node

	def _move_to_front(self, key):
		current_node = self.cache[key]

	def _delete_node(self, current_node):
		if self.front == current_node:
			self.front = None
			self.rear = None
		else: =
			if = current_node.prev

	def delete_last(self):
		last_node_key = self.rear.key = None
		self.rear = self.rear.prev
		return last_node_key

my_lru = LRU(capacity = 3)
print my_lru.get(4)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s