Day 129LRUキャッシュをOrderedDictで実装する

2026-07-03 JST ・ 難易度: 実用 ・ カテゴリ: 実用データ構造

Pythonコード

1from collections import OrderedDict2 3class LRUCache:4    def __init__(self, capacity):5        self.capacity = capacity6        self.cache = OrderedDict()7 8    def get(self, key):9        if key in self.cache:10            value = self.cache.pop(key)11            self.cache[key] = value12            return value13        else:14            return -115 16    def put(self, key, value):17        if key in self.cache:18            self.cache.pop(key)19        elif len(self.cache) >= self.capacity:20            self.cache.popitem(last=False)21        self.cache[key] = value22 23# LRUキャッシュの使用例24 cache = LRUCache(2)25 cache.put(1, 1)26 cache.put(2, 2)27 print(cache.get(1))  # 128 cache.put(3, 3)29 print(cache.get(2))  # -1

ここに出力が表示されます。

解説

• 行1〜2: collectionsモジュールからOrderedDictをインポートします。OrderedDictは、辞書とリストの機能を組み合わせたデータ構造です。LRUキャッシュを実装するために使用します。OrderedDictのpopitem(last=False)は、最も古いエントリを削除します。
• 行4〜6: LRUCacheクラスを定義します。__init__メソッドで、キャッシュの容量とOrderedDictのインスタンスを初期化します。
• 行8〜14: getメソッドを定義します。指定されたキーがキャッシュに存在する場合、値を返します。存在しない場合、-1を返します。また、キーが存在する場合、OrderedDictのpopと再挿入によって、キーを最も最近使用したキーとしてマークします。
• 行16〜22: putメソッドを定義します。指定されたキーがキャッシュに存在する場合、古いエントリを削除して、新しい値を挿入します。キャッシュが満杯の場合、最も古いエントリを削除して、新しいエントリを挿入します。
• 行24〜29: LRUキャッシュの使用例を示します。LRUCacheのインスタンスを作成し、putとgetメソッドを使用してキャッシュを操作します。
• 行19: 補足: len() は要素数（長さ）を返す関数です。例えば、len([1, 2, 3])は3を返します。
• 行27〜29: 補足: print() は画面に文字や値を表示する関数です。例えば、print('Hello, World!')は画面に'Hello, World!'と表示します。

次に試してみよう

• LRUCacheクラスに、キャッシュの内容を表示するメソッドを追加してみましょう。
• LRUCacheクラスを使用して、シンプルなキャッシュシステムを実装してみましょう。
• LRUCacheクラスに、キャッシュのサイズを動的に変更できる機能を追加してみましょう。