LRUキャッシュの実装

class LRUCache: class _Node: __slots__ = ("key", "val", "prev", "next") def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None def __init__(self, capacity: int): if capacity <= 0: raise ValueError("capacity は正の整数でなければなりません") self.capacity = capacity self.map = {} # key -> _Node # 番兵付き双方向連結リスト: # head <-> ... <-> tail # 最も最近使用されたものは head の直後。 # 最も長く使用されていないものは tail の直前。 self.head = self._Node() self.tail = self._Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: _Node) -> None: p, n = node.prev, node.next p.next = n n.prev = p def _add_to_front(self, node: _Node) -> None: # head の直後に挿入する（最も最近使用されたものとしてマークする） first = self.head.next node.prev = self.head node.next = first self.head.next = node first.prev = node def _move_to_front(self, node: _Node) -> None: self._remove(node) self._add_to_front(node) def _evict_lru(self) -> None: # tail の直前のノードを削除する lru = self.tail.prev if lru is self.head: return self._remove(lru) del self.map[lru.key] def get(self, key: int) -> int: node = self.map.get(key) if node is None: return -1 self._move_to_front(node) return node.val def put(self, key: int, value: int) -> None: node = self.map.get(key) if node is not None: node.val = value self._move_to_front(node) return new_node = self._Node(key, value) self.map[key] = new_node self._add_to_front(new_node) if len(self.map) > self.capacity: self._evict_lru() # 正しさのデモンストレーション cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # 期待される出力: 10 cache.put(3, 30) # キー 2 を削除する print(cache.get(2)) # 期待される出力: -1 cache.put(4, 40) # キー 1 を削除する print(cache.get(1)) # 期待される出力: -1 print(cache.get(3)) # 期待される出力: 30 print(cache.get(4)) # 期待される出力: 40 # 出力: # 10 # -1 # -1 # 30 # 40 # O(1) の簡単な説明: # - 辞書（ハッシュマップ）がキーをノードに対応付けることで、get/put の平均ルックアップは O(1) になる。 # - 双方向連結リストが使用順序を維持する。ノードを先頭へ移動すること、 # 新しいノードを挿入すること、LRU ノードを削除することはすべて O(1) のポインタ更新である。 # これらを組み合わせることで、get と put の両方で平均 O(1) 時間が得られる。

```python import collections class LRUCache: """ 最も最近使われていない（LRU）キャッシュの実装。 このキャッシュは、キーの検索を O(1) で行うために辞書を使用し、 使用順序を維持するために双方向連結リストを使用します。辞書はキーを 連結リスト内のノードに対応付けます。 """ # 双方向連結リスト内のノードを表す内部クラス class _Node: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None def __init__(self, capacity: int): """ 正の整数の容量でキャッシュを初期化します。 """ if capacity <= 0: raise ValueError("容量は正の整数でなければなりません。") self.capacity = capacity self.cache = {} # リスト操作を簡単にするための先頭と末尾の番兵ノード self.head = self._Node() self.tail = self._Node() self.head.next = self.tail self.tail.prev = self.head def _remove_node(self, node: _Node): """連結リストからノードを削除します。""" prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _add_to_front(self, node: _Node): """連結リストの先頭（最新）にノードを追加します。""" node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _move_to_front(self, node: _Node): """既存のノードをリストの先頭に移動します。""" self._remove_node(node) self._add_to_front(node) def get(self, key: int) -> int: """ キーが存在する場合はそのキーに対応する値を返し、そうでない場合は -1 を返します。 キーにアクセスすると、それは最も最近使用されたものとしてマークされます。 """ if key in self.cache: node = self.cache[key] # アクセスされたノードを先頭に移動して、最近使用されたものとしてマークする self._move_to_front(node) return node.value return -1 def put(self, key: int, value: int) -> None: """ キーと値のペアを挿入または更新します。 容量を超えた場合は、最も最近使われていないキーを追い出します。 """ if key in self.cache: # キーが存在する場合は、その値を更新して先頭に移動する node = self.cache[key] node.value = value self._move_to_front(node) else: # キーが新しい場合は、新しいノードを作成する new_node = self._Node(key, value) self.cache[key] = new_node self._add_to_front(new_node) # キャッシュが容量を超えた場合は、最も最近使われていない項目を追い出す if len(self.cache) > self.capacity: # LRU 項目は末尾の番兵の直前にあるもの lru_node = self.tail.prev self._remove_node(lru_node) del self.cache[lru_node.key] # --- デモンストレーション --- print("LRUCache の機能をデモンストレーションします:") cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(f"get(1): {cache.get(1)}") # 期待される結果: 10 cache.put(3, 30) # キー 2 を追い出す print(f"get(2): {cache.get(2)}") # 期待される結果: -1 cache.put(4, 40) # キー 1 を追い出す print(f"get(1): {cache.get(1)}") # 期待される結果: -1 print(f"get(3): {cache.get(3)}") # 期待される結果: 30 print(f"get(4): {cache.get(4)}") # 期待される結果: 40 # --- デモンストレーションの期待される出力 --- # LRUCache の機能をデモンストレーションします: # get(1): 10 # get(2): -1 # get(1): -1 # get(3): 30 # get(4): 40 # --- O(1) 時間計算量の説明 --- # `get` と `put` の両方で平均 O(1) の時間計算量が達成されるのは、2 つのデータ構造を組み合わせているためです: # 1. **ハッシュマップ（辞書）:** Python の `dict` は、挿入、削除、検索に対して平均 O(1) の時間計算量を提供します。この実装では、辞書 `self.cache` がキーを格納し、それらを双方向連結リスト内の対応するノードに直接対応付けます。これにより、キャッシュ内の任意のノードをそのキーによって即座に見つけることができます。 # 2. **双方向連結リスト:** このデータ構造は使用順序を維持します。新しいノードを先頭（最も最近使用された位置）に追加することや、最後のノード（最も最近使われていないもの）を削除することは、いくつかのポインタを更新するだけでよいため O(1) の操作です。項目にアクセスまたは更新されたとき、その対応するノード（ハッシュマップによって O(1) で見つかる）は、隣接ノードを単純につなぎ替えることで O(1) でリストの先頭に移動できます。 # 両方の構造を一緒に使用することで、`get` および `put` 操作のすべての部分――キーの検索、値の更新、ノードの移動、LRU ノードの削除――を一定の平均時間で実行できます。 ```