فهرست مقاله
کشِ دارای سقف باید هنگام ورود نتیجهٔ تازه تصمیم بگیرد کدام مدخل کنار برود. در روش LRU، مدخلی حذف میشود که مدت بیشتری از آخرین استفادهاش گذشته است. این درس ترتیب استفاده را با دادههای ساختگی و یک ساختار دادهٔ دستنویس بررسی میکند. هیچ سرویس، مدل، دادهٔ مشتری یا سنجش افزایش سرعت وجود ندارد؛ مسئله، درستبودن حذف و جابهجایی مدخلهاست.
۱. نبودن کلید را از مقدار ذخیرهشده جدا کنیم

مثال ما نتیجههای سادهٔ یک محاسبهٔ فرضی را نگه میدارد: مقدار میتواند None یا عدد صحیح صفر تا ۴۰۹۶ باشد. کلید دقیقاً رشتهای با یک تا شصتوچهار نقطهٔ کد است. bool، عدد شناور، فهرست و کلیدِ شیء سفارشی پذیرفته نیستند. این دامنهٔ محدود به ما اجازه میدهد دربارهٔ مقدارهای تغییرناپذیر و برابری رشتهایِ روشن صحبت کنیم.
نبودن کلید با یک شیء یکتای MISS نشان داده میشود؛ فراخوان باید آن را با is مقایسه کند. None، مقدارِ مجازِ ذخیرهشده است و صفر نیز برخورد موفق محسوب میشود. عبارت «اگر نتیجه درستنما نبود، دوباره محاسبه کن» قرارداد را خراب میکند، چون صفر و None ممکن است واقعاً در کش باشند. کد برای miss و hit خروجیهای قابلتفکیک ثبت میکند.
مستندات lru_cache پایتون دربارهٔ نگهداری نتیجه و الزامِ کلیدهای قابلهش توضیح میدهد. کلاس آموزشیِ ما آن decorator نیست؛ ظرفیتش تعداد مدخل است و هیچ تابع محاسبه یا شبکه را فراخوانی نمیکند. کاربرد مناسب مثال، استفادهٔ دوباره از نتیجهٔ خالص است؛ بازپخش اقدامِ دارای اثر بیرونی، قرارداد جداگانهای میخواهد.
۲. get و peek ترتیب استفادهٔ یکسانی ندارند

ظرفیت نمونه دو مدخل است و ترتیب را از کماستفادهشدهٔ اخیر به تازهاستفادهشده مینویسیم. ابتدا r1:A با مقدار ده و سپس r1:B با مقدار None وارد میشوند؛ ترتیب A، B است. get روی A مقدار ده را برمیگرداند و A را به انتها میبرد، بنابراین ترتیب B، A میشود.
در قرارداد ما، peek فقط نگاه میکند. peek روی B یک hit با مقدار None است، اما ترتیب B، A را تغییر نمیدهد. حالا ورود r1:C با مقدار سی، B را حذف میکند و ترتیب A، C میشود. اگر peek هم تازگی را عوض میکرد، قربانیِ حذف متفاوت بود؛ بنابراین نام عملیات و رفتار آن باید کنار هم آزموده شوند.
get روی B پس از حذف، miss است و ترتیب را عوض نمیکند. سپس put روی A مقدارش را یازده میکند و A را تازهترین قرار میدهد: C، A. این بهروزرسانی، مدخل تازهای به تعداد اضافه نمیکند و چیزی حذف نمیشود. LRU با ترتیب ورود اولیه یکسان نیست؛ لمسکردن مدخلِ موجود در تصمیم بعدی اثر دارد.
۳. دو سر زنجیره و قربانی حذف را حفظ کنیم

دیکشنری، کلید را به گرهٔ آن وصل میکند و زنجیرهٔ دوسویه ترتیب را نگه میدارد. یک گرهٔ نگهبان داریم؛ همسایهٔ بعدی آن قدیمیترین و همسایهٔ قبلی آن تازهترین مدخل است. برای لمسِ یک کلید، گره از جای فعلی جدا و به انتها متصل میشود. در حذف، هر دو پیوندِ همسایهها باید اصلاح شوند؛ تغییر فقط یک جهت کافی نیست.
راهنمای OrderedDict عملیات تغییر ترتیب و بیرونآوردن عضوِ سرِ ترتیب را معرفی میکند و دستورهایی برای گونههای LRU دارد. ما برای دیدن منطق، دیکشنری و گرههای خودمان را ساختهایم؛ کدِ دستورهای مستندات را کپی نکردهایم. تابع بررسی ناوردا، مسیر رفت و برگشت، عضویت در دیکشنری و تعداد گرهها را مستقل وارسی میکند.
در ادامهٔ رد دستی، کلید r2:A با مقدار دوازده وارد میشود و C را کنار میزند. r1:A و r2:A دو رشتهٔ متفاوتاند و همزمان باقی میمانند. get نهایی روی r1:A مقدار یازده را میدهد و ترتیب نهایی r2:A، r1:A است. این پیشوندها فقط قرارداد نامگذاریِ ساختگیاند؛ کلاس، نسخهٔ معتبر را کشف یا مدخل قدیمی را خودکار بازنشسته نمیکند.
۴. کد کامل و مرجعِ مستقلِ ترتیب را اجرا کنیم

فایل bounded_lru_cache.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. پیادهسازی اصلی OrderedDict یا functools.lru_cache را فراخوانی نمیکند. در مقابل، مرجع مستقل برای هر لمس یک شمارهٔ منطقیِ افزایشی نگه میدارد و برای حذف، کمترین شماره را پیدا میکند؛ هیچ گره یا پیوندی در آن نیست.
"""Original dict + doubly linked list LRU, immutable toy values, single-threaded.
Entry count only: no TTL, permissions, byte budget, loading or exactly-once.
"""
from itertools import product
import json
import platform
MISS = object()
def validate_key(key):
if type(key) is not str or not 1 <= len(key) <= 64:
raise ValueError('key')
def validate_value(value):
if value is not None and (type(value) is not int or not 0 <= value <= 4096):
raise ValueError('value')
class Node:
__slots__ = ('key', 'value', 'prev', 'next')
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class BoundedLRU:
def __init__(self, capacity):
if type(capacity) is not int or not 0 <= capacity <= 16:
raise ValueError('capacity')
self._capacity, self._nodes = capacity, {}
self._root = Node()
self._root.prev = self._root.next = self._root
def _detach(self, node):
node.prev.next = node.next
node.next.prev = node.prev
node.prev = node.next = None
def _append_mru(self, node):
last = self._root.prev
node.prev, node.next = last, self._root
last.next = self._root.prev = node
def get(self, key):
validate_key(key)
node = self._nodes.get(key)
if node is None:
return MISS
self._detach(node)
self._append_mru(node)
return node.value
def peek(self, key):
validate_key(key)
node = self._nodes.get(key)
return MISS if node is None else node.value
def put(self, key, value):
validate_key(key)
validate_value(value)
if self._capacity == 0:
return None
node = self._nodes.get(key)
if node is not None:
node.value = value
self._detach(node)
self._append_mru(node)
return None
evicted_key = None
if len(self._nodes) == self._capacity:
victim = self._root.next
evicted_key = victim.key
self._detach(victim)
del self._nodes[evicted_key]
node = Node(key, value)
self._nodes[key] = node
self._append_mru(node)
return evicted_key
def delete(self, key):
validate_key(key)
node = self._nodes.pop(key, None)
if node is None:
return False
self._detach(node)
return True
def clear(self):
for node in self._nodes.values():
node.prev = node.next = None
self._nodes.clear()
self._root.prev = self._root.next = self._root
def snapshot(self):
entries = []
node = self._root.next
while node is not self._root:
entries.append({'key': node.key, 'value': node.value})
node = node.next
return entries
def check_invariants(self):
seen, previous, forward = set(), self._root, []
node = self._root.next
while node is not self._root:
assert id(node) not in seen and node.prev is previous
assert self._nodes[node.key] is node
seen.add(id(node)); forward.append(node.key)
previous, node = node, node.next
assert len(seen) <= self._capacity
assert previous is self._root.prev and len(seen) == len(self._nodes)
reverse, following = [], self._root
node = self._root.prev
while node is not self._root:
assert node.next is following
reverse.append(node.key)
assert len(reverse) <= self._capacity
following, node = node, node.prev
assert reverse == list(reversed(forward)) and following is self._root.next
return True
class StampOracle:
"""Independent map with increasing logical stamps, min eviction, no links."""
def __init__(self, capacity):
self.capacity, self.values, self.stamps, self.clock = capacity, {}, {}, 0
def touch(self, key):
self.clock += 1
self.stamps[key] = self.clock
def get(self, key):
if key not in self.values:
return MISS
self.touch(key)
return self.values[key]
def peek(self, key):
return self.values.get(key, MISS)
def put(self, key, value):
if self.capacity == 0:
return None
evicted = None
if key not in self.values and len(self.values) == self.capacity:
evicted = min(self.stamps, key=self.stamps.get)
del self.values[evicted]; del self.stamps[evicted]
self.values[key] = value
self.touch(key)
return evicted
def delete(self, key):
if key not in self.values:
return False
del self.values[key]; del self.stamps[key]
return True
def snapshot(self):
return [{'key': key, 'value': self.values[key]} for key in sorted(self.stamps, key=self.stamps.get)]
def observed(cache, operation):
method, key, *extra = operation
value = getattr(cache, method)(key, *extra)
if method in ('get', 'peek'):
result = {'hit': value is not MISS}
if value is not MISS:
result['value'] = value
else:
result = {'evicted_key': value} if method == 'put' else {'deleted': value}
return {'operation': list(operation), 'result': result, 'lru_to_mru': cache.snapshot()}
def rejects(call, message):
try:
call()
except ValueError as error:
return str(error) == message
return False
def run_example():
operations = [('put', 'r1:A', 10), ('put', 'r1:B', None), ('get', 'r1:A'),
('peek', 'r1:B'), ('put', 'r1:C', 30), ('get', 'r1:B'),
('put', 'r1:A', 11), ('put', 'r2:A', 12), ('get', 'r1:A')]
cache = BoundedLRU(2)
trace = []
for op in operations:
trace.append(observed(cache, op)); cache.check_invariants()
nulls = BoundedLRU(2); nulls.put('N', None); nulls.put('Z', 0)
disabled = BoundedLRU(0); disabled.put('A', 1)
single = BoundedLRU(1); single.put('A', 1); single.put('A', 2)
no_update_eviction = single.snapshot() == [{'key': 'A', 'value': 2}]
evicted_single = single.put('B', 3)
deletion = BoundedLRU(3)
for key in ['A', 'B', 'C']: deletion.put(key, 1)
deleted_middle = deletion.delete('B') and deletion.snapshot() == [{'key': 'A', 'value': 1}, {'key': 'C', 'value': 1}]
deleted_head_tail = deletion.delete('A') and deletion.delete('C') and not deletion.delete('C') and deletion.check_invariants()
clearing = BoundedLRU(2); clearing.put('A', 1); clearing.clear()
after_clear = clearing.snapshot() == [] and clearing.get('A') is MISS and clearing.check_invariants()
clearing.put('B', 2)
invalid = BoundedLRU(2); invalid.put('A', 1); prior_invalid = invalid.snapshot()
invalid_keys = [None, True, 1, 1.0, float('nan'), [], {}, '', 'x' * 65]
key_rejection = all(rejects(lambda value=value, method=method: getattr(invalid, method)(value), 'key')
for value in invalid_keys for method in ['get', 'peek', 'delete'])
key_rejection &= all(rejects(lambda value=value: invalid.put(value, 1), 'key') for value in invalid_keys)
value_rejection = all(rejects(lambda value=value: invalid.put('A', value), 'value')
for value in [True, 1.0, -1, 4097, float('nan'), [], MISS])
copied = cache.snapshot(); copied[0]['key'] = 'changed'; copied.append({'key': 'fake', 'value': 0})
for _ in range(20): cache.get('r1:A')
cases, oracle_ok = 0, True
choices = [('put', 'A', 1), ('put', 'B', None), ('put', 'C', 0),
('get', 'A'), ('peek', 'B'), ('put', 'A', 2), ('delete', 'C')]
for capacity in (0, 1, 2):
for ops in product(choices, repeat=4):
actual, reference = BoundedLRU(capacity), StampOracle(capacity)
for op in ops:
oracle_ok &= observed(actual, op) == observed(reference, op)
actual.check_invariants()
cases += 1
checks = {
'hand_initial_insertions_are_lru_to_mru': trace[1]['lru_to_mru'] == [{'key': 'r1:A', 'value': 10}, {'key': 'r1:B', 'value': None}],
'get_hit_moves_key_to_mru': trace[2]['result'] == {'hit': True, 'value': 10} and [x['key'] for x in trace[2]['lru_to_mru']] == ['r1:B', 'r1:A'],
'peek_returns_none_without_recency_change': trace[3]['result'] == {'hit': True, 'value': None} and trace[3]['lru_to_mru'] == trace[2]['lru_to_mru'],
'full_insert_evicts_least_recently_used': trace[4]['result'] == {'evicted_key': 'r1:B'} and [x['key'] for x in trace[4]['lru_to_mru']] == ['r1:A', 'r1:C'],
'get_miss_does_not_change_order': trace[5]['result'] == {'hit': False} and trace[5]['lru_to_mru'] == trace[4]['lru_to_mru'],
'replace_existing_value_refreshes_recency_not_size': trace[6]['result'] == {'evicted_key': None} and trace[6]['lru_to_mru'] == [{'key': 'r1:C', 'value': 30}, {'key': 'r1:A', 'value': 11}],
'different_revision_strings_are_distinct_keys': trace[7]['result'] == {'evicted_key': 'r1:C'} and trace[-1]['lru_to_mru'] == [{'key': 'r2:A', 'value': 12}, {'key': 'r1:A', 'value': 11}],
'cached_none_is_not_miss_sentinel': nulls.get('N') is None and nulls.get('missing') is MISS,
'cached_zero_is_a_hit_not_falsy_miss': observed(nulls, ('get', 'Z'))['result'] == {'hit': True, 'value': 0},
'zero_capacity_disables_storage': disabled.snapshot() == [] and disabled.get('A') is MISS and disabled.check_invariants(),
'capacity_one_update_and_replacement': no_update_eviction and evicted_single == 'A' and single.snapshot() == [{'key': 'B', 'value': 3}] and single.check_invariants(),
'delete_middle_head_tail_and_missing_preserves_links': deleted_middle and deleted_head_tail and deletion.snapshot() == [],
'clear_is_empty_and_cache_reusable': after_clear and clearing.snapshot() == [{'key': 'B', 'value': 2}] and clearing.check_invariants(),
'strict_capacity_bounds_and_bool_reject': all(rejects(lambda value=value: BoundedLRU(value), 'capacity') for value in [True, -1, 1.0, 17, None]) and BoundedLRU(16).check_invariants(),
'strict_string_keys_reject_before_state_change': bool(key_rejection) and invalid.snapshot() == prior_invalid,
'immutable_value_contract_rejects_before_replacement': value_rejection and invalid.snapshot() == prior_invalid,
'snapshot_copy_and_repeated_mru_access_preserve_links': cache.snapshot() == trace[-1]['lru_to_mru'] and cache.check_invariants(),
'independent_logical_stamp_oracle': cases == 7203 and bool(oracle_ok),
}
assert len(checks) == 18 and all(type(value) is bool and value for value in checks.values()), checks
return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
'scope': 'Single-threaded manual LRU; entry count not bytes; no TTL/authorization/loading/business action or measured speedup',
'results': {'capacity_entries': 2, 'trace': trace, 'final_lru_to_mru': cache.snapshot(),
'oracle_traces_inside_one_group': cases, 'oracle_operations_each': 4,
'limits': {'capacity': 'exact int0..16', 'key': 'exact str1..64codepoints',
'value': 'None or exact int0..4096; immutable only',
'miss': 'unique object checked with is, never cached'}}, 'checks': checks}
if __name__ == '__main__':
print(json.dumps(run_example(), ensure_ascii=False, indent=2))
هجده گروه اجرایی شامل پاسخ دستی، None و صفر، ظرفیت صفر و یک، جایگزینی مقدار موجود، حذف گرههای میانی و انتهایی، پاککردن و ورودی نامعتبرند. هفت عملیاتِ کوچک در همهٔ ردهای چهارتایی و سه ظرفیت صفر، یک و دو اجرا میشوند: ۷۲۰۳ رد در یک گروهِ مرجع مستقل. پس از هر عملیات، نتیجه و تمام ترتیب مقایسه و ناورداهای ساختار اصلی بررسی میشوند.
snapshot فهرست و دیکشنریهای تازه میدهد، اما این ادعا دربارهٔ کپیِ عمیقِ هر نوع شیء نیست؛ مقدارهای مجاز ما تغییرناپذیرند. تغییر snapshot نباید ساختار کش را عوض کند. همچنین چند بار گرفتن تازهترین کلید نباید گرهٔ تکراری بسازد. بررسی پیوندها برای کشف همین خطاهایی است که ممکن است در نگاهکردن صرف به مقدار برگشتی پنهان بمانند.
۵. سقف مدخل و چهار پرسش پاسخدار را روشن نگه داریم

ظرفیت دقیقاً عدد صحیح صفر تا شانزده است؛ صفر یعنی ذخیرهسازی غیرفعال و هر خواندن miss. ظرفیت دو، دو مدخل را محدود میکند و بودجهٔ بایت حافظه نیست. اعتبارسنجیِ کلید و مقدار پیش از جابهجایی گره انجام میشود؛ ورودی نامعتبر نباید مقدار قبلی یا ترتیب را تغییر دهد. این کلاس زمان انقضا، کنترل دسترسی، همزمانی رشتهها یا پاکسازی امن حافظه ندارد. الزامات اعتبار و مجوز کش پاسخ با درستبودن LRU برآورده نمیشوند.
{
"python": "3.14.5",
"dependencies": "Python standard library only",
"scope": "Single-threaded manual LRU; entry count not bytes; no TTL/authorization/loading/business action or measured speedup",
"results": {
"capacity_entries": 2,
"trace": [
{
"operation": [
"put",
"r1:A",
10
],
"result": {
"evicted_key": null
},
"lru_to_mru": [
{
"key": "r1:A",
"value": 10
}
]
},
{
"operation": [
"put",
"r1:B",
null
],
"result": {
"evicted_key": null
},
"lru_to_mru": [
{
"key": "r1:A",
"value": 10
},
{
"key": "r1:B",
"value": null
}
]
},
{
"operation": [
"get",
"r1:A"
],
"result": {
"hit": true,
"value": 10
},
"lru_to_mru": [
{
"key": "r1:B",
"value": null
},
{
"key": "r1:A",
"value": 10
}
]
},
{
"operation": [
"peek",
"r1:B"
],
"result": {
"hit": true,
"value": null
},
"lru_to_mru": [
{
"key": "r1:B",
"value": null
},
{
"key": "r1:A",
"value": 10
}
]
},
{
"operation": [
"put",
"r1:C",
30
],
"result": {
"evicted_key": "r1:B"
},
"lru_to_mru": [
{
"key": "r1:A",
"value": 10
},
{
"key": "r1:C",
"value": 30
}
]
},
{
"operation": [
"get",
"r1:B"
],
"result": {
"hit": false
},
"lru_to_mru": [
{
"key": "r1:A",
"value": 10
},
{
"key": "r1:C",
"value": 30
}
]
},
{
"operation": [
"put",
"r1:A",
11
],
"result": {
"evicted_key": null
},
"lru_to_mru": [
{
"key": "r1:C",
"value": 30
},
{
"key": "r1:A",
"value": 11
}
]
},
{
"operation": [
"put",
"r2:A",
12
],
"result": {
"evicted_key": "r1:C"
},
"lru_to_mru": [
{
"key": "r1:A",
"value": 11
},
{
"key": "r2:A",
"value": 12
}
]
},
{
"operation": [
"get",
"r1:A"
],
"result": {
"hit": true,
"value": 11
},
"lru_to_mru": [
{
"key": "r2:A",
"value": 12
},
{
"key": "r1:A",
"value": 11
}
]
}
],
"final_lru_to_mru": [
{
"key": "r2:A",
"value": 12
},
{
"key": "r1:A",
"value": 11
}
],
"oracle_traces_inside_one_group": 7203,
"oracle_operations_each": 4,
"limits": {
"capacity": "exact int0..16",
"key": "exact str1..64codepoints",
"value": "None or exact int0..4096; immutable only",
"miss": "unique object checked with is, never cached"
}
},
"checks": {
"hand_initial_insertions_are_lru_to_mru": true,
"get_hit_moves_key_to_mru": true,
"peek_returns_none_without_recency_change": true,
"full_insert_evicts_least_recently_used": true,
"get_miss_does_not_change_order": true,
"replace_existing_value_refreshes_recency_not_size": true,
"different_revision_strings_are_distinct_keys": true,
"cached_none_is_not_miss_sentinel": true,
"cached_zero_is_a_hit_not_falsy_miss": true,
"zero_capacity_disables_storage": true,
"capacity_one_update_and_replacement": true,
"delete_middle_head_tail_and_missing_preserves_links": true,
"clear_is_empty_and_cache_reusable": true,
"strict_capacity_bounds_and_bool_reject": true,
"strict_string_keys_reject_before_state_change": true,
"immutable_value_contract_rejects_before_replacement": true,
"snapshot_copy_and_repeated_mru_access_preserve_links": true,
"independent_logical_stamp_oracle": true
}
}
پرسش اول: چرا پس از get روی A و peek روی B، ورود C باعث حذف B شد؟ پاسخ: get، A را تازهترین کرده بود و peek طبق قرارداد تازگی را تغییر نداد؛ بنابراین B همچنان قدیمیترین بود.
پرسش دوم: آیا None یعنی کلید وجود ندارد؟ پاسخ: خیر؛ B پیش از حذف، یک hit با مقدار None بود. تنها شیء یکتای MISS نبودن کلید را نشان میدهد؛ صفر نیز hit است.
پرسش سوم: آیا put روی کلید موجود باید ظرفیت بیشتری بخواهد؟ پاسخ: در این قرارداد خیر؛ مقدار جایگزین و همان گره تازهترین میشود. در نمونه، A از ده به یازده تغییر کرد و بدون حذف، ترتیب C، A شد.
پرسش چهارم: آیا اضافهشدن r2:A صحت نسخهٔ پاسخ را تضمین میکند؟ پاسخ: خیر؛ انتخاب نسخه و سازگاری تصویر ثابت نمایه قواعد دیگری دارند. منابع در ۲۴ مهر ۱۴۰۵ خوانده شدند؛ صفحات مرجع Python 3.14.8 بودند و اجرای کد روی 3.14.5 ثبت شد. این آموزش دادهساختار، معیار سرعت سرویس یا اجرای یکبارهٔ اقدام نیست.
منابع و مطالعهٔ بیشتر
بررسی منابع: ۲۴ مهر ۱۴۰۵. تحلیلها و پیشنهادهای اجرایی، جمعبندی نویسندهاند.

