LRU (Least Recently Used) cache ช่วยขจัดรายการที่ไม่ได้เข้าถึงมานานที่สุดเมื่อถึงความจุ การออกแบบแบบคลาสสิกรวม hash map (O(1) lookup) กับ linked list แบบสองทิศทาง (O(1) reordering) ซึ่งให้ O(1) get และ put
HashMap: key -> node DLL (recency order):
MRU <-> ... <-> LRU
get/put: map finds node move touched node to front (MRU)
in O(1); DLL splices it evict the tail (LRU) when full
to the front in O(1)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = OrderedDict() # preserves access order
def get(self, key): # O(1)
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as most recently used
return self.cache[key]
def put(self, key, value): # O(1)
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False) # evict least recently used
OrderedDict เป็นตัวมันเองคือ hash map บวก linked list แบบสองทิศทาง ซึ่งเป็นโครงสร้างที่อธิบายไว้ข้างต้นทุกประการ
| การดำเนินการ | เวลา |
|---|---|
| get | O(1) |
| put | O(1) |
| space | O(capacity) |
Linked list แบบสองทิศทางช่วยให้คุณ ตัดปมออกจากตรงกลางใน O(1) (คุณเก็บ prev/next ของมัน) ซึ่งเป็นไปไม่ได้กับ linked list ทางเดียวหรืออาร์เรย์โดยไม่มีการขยับ O(n)
LRU caches นั่งอยู่หน้าฐานข้อมูล เซิร์ฟเวอร์เว็บ และ CPU เพื่อให้ข้อมูลที่ใช้บ่อยเร็วและหน่วยความจำมีขีดจำกัด
ปัญหานี้เป็นปัญหาพื้นฐานของสัมภาษณ์สำหรับผู้บริหารเพราะมันทดสอบการรวมโครงสร้างสองแบบเพื่อให้ แต่ละแบบครอบคลุมจุดอ่อนของอีกแบบหนึ่ง — ทักษะการออกแบบระบบที่สำคัญ