Mercurial

comparison async_multi_threads/lru_version2.py @ 69:551d9fc0a2ba

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated wrong names.
author June Park <parkjune1995@gmail.com>
date Thu, 25 Dec 2025 20:07:46 -0800
parents
children
comparison
equal deleted inserted replaced
68:70ca1d99f3fd 69:551d9fc0a2ba
1 #
2 # Question: Least Recently Used (LRU) Cache Implementation
3 #
4 # Design and implement a Least Recently Used (LRU) cache. The cache should be initialized with a positive integer capacity.
5 #
6 # Your implementation must support the following operations with $O(1)$ time complexity for both:
7 #
8 # get(key): Retrieve the value of the item identified by key. If the key exists, return its value. If it doesn't, return $-1$. This operation also marks the key as the most recently used.
9 #
10 # put(key, value): Insert or update an item. If the key already exists, update its value and mark it as the most recently used. If the key does not exist, insert the new item. When the cache reaches its capacity, it must evict the least recently used item before inserting the new one.
11 #
12 # You must use a Hash Map and a Doubly Linked List for the implementation.
13
14 # Cache , limit 3
15
16 from typing import Dict
17
18 # tail.prev.next = node, node.left = tails.prev, tails.prev = Node, node.next = tail
19
20 # Head <-> Tail
21 # Head -> Node <-> Tail ,
22 # Head <-> Node <-> Node1 <-> Tail,
23 # node.prev.next = node.next, node.next.prev = node.prev
24
25 class Node:
26
27 def __init__(self, key: str, value: str):
28 self.next: Node | None = None
29 self.prev: Node | None = None
30 self.key = key
31 self.value = value
32
33 class LRU:
34
35 def __init__(self, capacity: int = 2):
36 self.db: Dict[str, Node] = {}
37 self.capacity = capacity
38
39 self.head = Node("-1", "-1")
40 self.tail = Node("-1", "-1")
41 self.head.next, self.tail.prev = self.tail, self.head
42
43 def get(self, key: str):
44 node = self.db[key]
45 self._remove(node)
46 self._add_to_tail(node)
47 return node.value
48
49 def put(self, key: str, value: str):
50 if len(self.db) < self.capacity or key in self.db:
51 new_node = Node(key, value)
52 self._add_to_tail(new_node)
53 self.db[key] = new_node
54 else:
55 least_recently_used_node = self.head.next
56 self._remove(least_recently_used_node)
57 del self.db[least_recently_used_node.key]
58
59 new_node = Node(key, value)
60 self._add_to_tail(new_node)
61 self.db[key] = new_node
62
63 def _remove(self, node: Node):
64 node.prev.next, node.next.prev = node.next, node.prev
65
66 def _add_to_tail(self, node):
67 self.tail.prev.next, node.prev, self.tail.prev, node.next = node, self.tail.prev, node, self.tail
68
69 lru = LRU()
70 lru.put("june", "park")
71 lru.put("victor", "sun")
72 lru.get("june")
73 lru.put("bowen", "sun")
74
75