Xây dựng Lớp LRU Cache Hiệu năng cao với OrderedDict

Mục tiêu kiến thức

• Hiểu nguyên lý hoạt động của chiến lược loại bỏ phần tử cũ nhất (Least Recently Used - LRU).
• Khai thác sức mạnh của collections.OrderedDict với các phương thức O(1): move_to_end() và popitem(last=False).
• Thiết kế lớp quản lý bộ nhớ đệm đáp ứng thời gian thực cho hệ thống Backend và LLM Prompt Cache.

Mô tả bài toán

Trong hệ thống AI Empire Academy, ta cần lưu trữ các câu trả lời gần nhất của trợ giảng AI để phản hồi tức thì cho học viên mà không cần gọi lại API tốn kém. Khi bộ nhớ đệm đầy, phần tử ít được sử dụng nhất (truy cập hoặc cập nhật xa nhất trong quá khứ) sẽ bị loại bỏ trước.

Hãy cài đặt lớp LRUCache:

• Khởi tạo: __init__(self, capacity: int)
• capacity: Sức chứa tối đa của cache (số lượng key-value).
• Nếu capacity <= 0, ném ngoại lệ ValueError("capacity phai lon hon 0").
• Phương thức get(self, key: Any) -> Any:
• Nếu key tồn tại trong cache: đánh dấu key là vừa được sử dụng (chuyển lên vị trí mới nhất) và trả về giá trị tương ứng.
• Nếu key không tồn tại: trả về -1.
• Phương thức put(self, key: Any, value: Any) -> None:
• Nếu key đã tồn tại: cập nhật giá trị mới và đánh dấu key là vừa được sử dụng.
• Nếu key chưa tồn tại:
• Nếu cache đã đạt tới capacity, loại bỏ phần tử ít được sử dụng nhất (LRU key).
• Thêm cặp (key, value) mới vào cache và đánh dấu là mới nhất.
• Phương thức size(self) -> int:
• Trả về số lượng phần tử hiện đang lưu trữ trong cache.
• Phương thức clear(self) -> None:
• Xóa toàn bộ phần tử trong cache.

Mọi thao tác get và put đều phải đạt độ phức tạp thời gian trung bình O(1).

Ràng buộc

• 1 ≤ capacity ≤ 10⁵.
• Số lượng thao tác: tối đa 2 × 10⁵.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.