import threading
import time
from collections import OrderedDict
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("容量は正の整数である必要があります。")
self.capacity = capacity
self.cache = {}
self.head = Node(None, None) # ダミーヘッド
self.tail = Node(None, None) # ダミーテール
self.head.next = self.tail
self.tail.prev = self.head
self...
全文を表示 ▼
import threading
import time
from collections import OrderedDict
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("容量は正の整数である必要があります。")
self.capacity = capacity
self.cache = {}
self.head = Node(None, None) # ダミーヘッド
self.tail = Node(None, None) # ダミーテール
self.head.next = self.tail
self.tail.prev = self.head
self.lock = threading.RLock() # この例では簡潔さのためにRLockを使用していますが、よりきめ細かなアプローチも可能です。
def _remove_node(self, 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.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
with self.lock:
if key in self.cache:
node = self.cache[key]
self._remove_node(node)
self._add_to_front(node)
return node.value
return None
def put(self, key, value):
with self.lock:
if key in self.cache:
node = self.cache[key]
node.value = value
self._remove_node(node)
self._add_to_front(node)
else:
if len(self.cache) >= self.capacity:
# LRUアイテムを削除
lru_node = self.tail.prev
self._remove_node(lru_node)
del self.cache[lru_node.key]
new_node = Node(key, value)
self.cache[key] = new_node
self._add_to_front(new_node)
def delete(self, key):
with self.lock:
if key in self.cache:
node = self.cache[key]
self._remove_node(node)
del self.cache[key]
return True
return False
def __len__(self):
with self.lock:
return len(self.cache)
def __str__(self):
with self.lock:
items = []
current = self.head.next
while current != self.tail:
items.append(f"({current.key}: {current.value})")
current = current.next
return " -> ".join(items)
# --- 並行処理戦略の説明 ---
# この実装では、すべての操作（get、put、delete）に単一のthreading.RLockを使用しています。
# これによりスレッドセーフティは保証されますが、プロンプトで要求されているように競合を最小限に抑えることはできません。
# より高度で、きめ細かなアプローチとしては、キャッシュをセグメント化したり、
# ロックフリーデータ構造を使用したりすることが考えられます。例えば、キャッシュエントリのサブセットを保護する複数のロック（ストライピングロック）を使用したり、
# 読み取り/書き込みロックを使用して複数のリーダーがキャッシュの異なる部分に同時にアクセスできるようにしたりすることができます。
# 現在のRLockは、一度に1つのスレッドのみがキャッシュの内部状態（辞書と双方向連結リスト）を変更できることを保証します。
# これにより、複数のスレッドが同じノードを更新しようとしたり、ノードを追加/削除したり、エントリを同時に削除したりして、データ破損やLRU順序の間違いにつながる競合状態を防ぎます。
# RLock（再入可能ロック）の使用は、スレッドがロックを複数回取得できるため、複雑なシナリオで役立つことがありますが、この特定の用途では標準的なLockと比較して競合特性を根本的に変更するものではありません。
# --- デモンストレーション ---
def worker(cache, operations, thread_id):
for op, key, value in operations:
if op == 'get':
cache.get(key)
elif op == 'put':
cache.put(key, value)
elif op == 'delete':
cache.delete(key)
# いくらかの作業をシミュレートし、他のスレッドが実行できるようにする
time.sleep(0.001)
def run_demonstration():
print("LRUキャッシュデモンストレーションを実行中...")
capacity = 5
cache = LRUCache(capacity)
num_threads = 10
ops_per_thread = 50
all_operations = []
for i in range(num_threads):
thread_ops = []
for j in range(ops_per_thread):
op_type = ['get', 'put', 'delete'][j % 3] # 操作タイプをローテーション
key = (i * ops_per_thread + j) % (capacity * 2) # キャッシュにあるかもしれないし、ないかもしれないキー
value = f"val_{i}_{j}"
thread_ops.append((op_type, key, value))
all_operations.append(thread_ops)
threads = []
for i in range(num_threads):
thread = threading.Thread(target=worker, args=(cache, all_operations[i], i))
threads.append(thread)
thread.start()
for thread in threads:
thread.join()
print(f"デモンストレーション完了。最終キャッシュサイズ: {len(cache)}")
# キャッシュが容量を超えないことをアサートする
assert len(cache) <= capacity, f"キャッシュ容量を超過しました！現在のサイズ: {len(cache)}, 容量: {capacity}"
print("アサート成功：キャッシュ容量は維持されています。")
# 基本的な整合性チェック
print("基本的な整合性チェックを実行中...")
# これは非常に基本的なチェックです。より堅牢なテストでは、期待される状態を追跡する必要があります。
# とりあえず、サイズが負にならない、アクセス中に例外が発生しないことを確認します。
try:
# 投入された可能性が高いキーをいくつかアクセスしてみる
for i in range(min(5, capacity)):
key_to_check = (i * ops_per_thread) % (capacity * 2)
cache.get(key_to_check)
print("基本的な整合性チェックに成功しました。")
except Exception as e:
print(f"整合性チェックが例外で失敗しました: {e}")
assert False, "キャッシュ整合性チェックに失敗しました。"
if __name__ == "__main__":
run_demonstration()
判定
勝利票
0 / 3
平均スコア
総合点
総評
回答Aは、辞書と双方向連結リストを用いた従来のLRUキャッシュを実装しており、基本的なシングルスレッドLRUロジックは妥当です。正の容量検証、get/put/deleteを正しく処理し、マルチスレッドのデモも含まれています。しかし、すべての操作に対して1つのグローバルRLockを明示的に使用しており、これはプロンプトで要求されている粗粒度ロックの回避に違反し、異なるキーに対する同時getを許可しません。デモのアサーションは弱く、基本的な容量チェック以上の厳密な同時実行性の正しさやデータ整合性を意味のある形で検証していません。
採点詳細を表示 ▼
正確さ
重み 35%辞書と双方向連結リストの実装は標準的なLRU動作に対しては正しいです。getは新しさを更新し、putはtail.prevを追い出します。削除動作も正しいです。しかし、意図された同時実行設定に対する正しさは、単一ロックによる完全な直列化によって制限されており、タスクが強調するより困難な競合状態に対処していません。
完全性
重み 20%必要なAPI、非正の容量に対する検証、説明、マルチスレッドデモが含まれています。しかし、競合の最小化や異なるキーに対する同時ノンブロッキング読み取りの要求を満たしておらず、デモではインターリーブ下での正しさを深くテストしていません。
コード品質
重み 20%コードは読みやすく、わかりやすく、明確に整理されています。リスト操作用のヘルパーメソッドも合理的です。しかし、不要なOrderedDictのインポートがあり、設計が要求されたものではないことを説明で認めており、テストロジックはかなり表面的です。
実用性
重み 15%単純なスレッドセーフLRUキャッシュとしては実用的ですが、単一のグローバルロックは高い競合を引き起こし、スケーラブルな同時アクセスという主な実用的な要件を損ないます。デモは、実際のマルチスレッドワークロードに対する信頼性を限定的にしか与えません。
指示遵守
重み 10%APIとモジュール形式の要件は満たしていますが、粗粒度のグローバルロックの回避と、異なるキーに対する同時getの許可という指示を明らかに満たしていません。これは中心的な要件に対する大きな欠落です。
総合点
総評
回答Aは、適切な双方向連結リストとハッシュマップ構造、正しい追い出しロジック、および適切なエッジケース処理を備えた、正しいLRUキャッシュ実装を提供します。コードはクリーンで読みやすいです。しかし、すべての操作に単一のRLockを使用しているため、コアとなる並行性の要件を根本的に満たしていません。これは、作成者自身もプロンプトで許容されないと認めている点です。デモンストレーションは存在しますが、アサーションは最小限です。これは、細かい並行性の要件を満たすには大幅な再設計が必要な、堅実なベースライン実装です。
採点詳細を表示 ▼
正確さ
重み 35%回答Aは、適切な双方向連結リストとハッシュマップを備えた正しいLRUキャッシュを実装しています。追い出しロジック、get/put/delete操作、およびエッジケース処理（容量が正でない場合のValueError）はすべて正しいです。しかし、すべてに単一のRLockを使用しており、作成者自身もこれが細かい並行性の要件を満たさないことを認めています。LRUセマンティクスは正しいですが、並行性モデルは単純すぎます。
完全性
重み 20%回答Aには、必要なすべての操作、エッジケース処理、および複数のスレッドを使用したデモンストレーションが含まれています。しかし、コア要件である細かい並行性の実装に明示的に失敗しています（単一のグローバルRLockを使用）。デモンストレーションは存在しますが、アサーションは最小限であり、整合性チェックは表面的です。
コード品質
重み 20%回答Aは、優れた構造を持ち、クリーンで読みやすいです。ダミーのヘッド/テールセンチネルの使用は適切です。しかし、ここでRLockを使用するのは不要であり、コメントでは実装が指定された要件を満たしていないことが認識されています。コードはよく整理されていますが、並行性の設計は既知の欠点です。
実用性
重み 15%回答Aの単一ロックアプローチは、高並行性シナリオでの実用的な価値が限られています。正しく機能しますが、負荷下ではボトルネックになります。作成者はこの制限を認識しています。本番環境での使用には、実装の大幅な再設計が必要になります。
指示遵守
重み 10%回答Aはほとんどの指示に従っていますが、単一のグローバルロックを超えるというコア要件に明示的に失敗しています。プロンプトには「すべてを囲む単一の粗粒度ロックは許容されない」と記載されており、回答Aはまさにそれを使用しています。作成者はコメントでこれを認めていますが、問題は解決されていません。デモンストレーションとエッジケース処理は存在します。
総合点
総評
回答Aは、標準的な辞書と双方向連結リストを使用したLRUキャッシュのスレッドセーフな実装を提供しており、コードはクリーンで理解しやすいです。しかし、すべての操作に単一のグローバルロックを使用しているため、プロンプトのコアとなる並行処理要件を根本的に満たしていません。この制限を説明で正しく認識しているものの、この設計上の選択は、要求されたものよりもはるかに単純で準拠していないソリューションとなっています。デモコードは機能しますが、その整合性チェックは非常に基本的なものです。
採点詳細を表示 ▼
正確さ
重み 35%単一のグローバルロックにより、LRUロジックとスレッドセーフティは正しいです。しかし、すべての操作をシリアル化し、パフォーマンス目標を満たせないため、要求された*並行*設計の正しい実装ではありません。
完全性
重み 20%回答は、クラス実装、説明、デモという要求されたすべてのコンポーネントを提供しています。しかし、コアとなる実装は、プロンプトの並行処理要件に関しては不完全です。
コード品質
重み 20%コードはクリーンで、コメントも適切であり、標準的なPythonのイディオムに従っています。辞書と双方向連結リストの実装は、直接的かつ正確です。
実用性
重み 15%単一ロックのLRUキャッシュは、ロックがすぐにボトルネックになるため、高並行処理アプリケーションでの実用的な価値は限定的です。基本的な教科書的な例としては役立ちますが、高性能なソリューションではありません。
指示遵守
重み 10%回答は、プロンプトの重要なネガティブ制約「すべてを囲む単一の粗粒度ロックは許容されない」に従っていません。すべての操作に単一のRLockを使用することで、タスクの難しさの中心であったこの指示に直接違反しています。