Untitled
unknown
python
3 years ago
2.6 kB
6
Indexable
#Least Recently Used (LRU) is a common caching strategy. It defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first. #Let’s take an example of a cache that has a capacity of 4 elements. We cache elements 1, 2, 3 and 4. class LinkedList: def __init__(self, key, value): self.key = key self.value = value self.next = None self.prev = None class LRUCache: def __init__(self, capacity): self.capacity = capacity self.head = LinkedList(0, 0) self.tail = LinkedList(0, 0) self.head.next = self.tail self.tail.prev = self.head self.key_to_node = {} def _extract_node(self, node): nxt, prev = node.next, node.prev nxt.prev = prev prev.next = nxt node.next = None node.prev = None return node def _insert_to_head(self, node): old_next = self.head.next self.head.next = node node.next = old_next old_next.prev = node node.prev = self.head def set(self, key, value): if key in self.key_to_node: node = self.key_to_node[key] node.value = value self._extract_node(node) self._insert_to_head(node) else: node = LinkedList(key, value) self.key_to_node[key] = node self._insert_to_head(node) if len(self.key_to_node) > self.capacity: node_to_extract = self._extract_node(self.tail.prev) del self.key_to_node[node_to_extract.key] def find(self, key): if key not in self.key_to_node: return None node = self.key_to_node[key] self._extract_node(node) self._insert_to_head(node) return node.value class WebApplication: def __init__(self, config): self.cache = LRUCache(config['cache_capacity']) def make_key(self, req): return req def do_some_heavy_work(self, req): return req*2 def process_request(self, request): key = self.make_key(request) value = self.cache.find(key) if not value: value = self.do_some_heavy_work(request) self.cache.set(key, value) return value cfg = {'cache_capacity': 4} wa = WebApplication(cfg) wa.process_request(1) wa.process_request(2) wa.process_request(3) wa.process_request(4) wa.process_request(5)
Editor is loading...