LFU Cache trong Python

Giả sử muốn thiết kế và triển khai cấu trúc dữ liệu cho hệ thống cache LFU (Least Frequently Used). Hỗ trợ các thao tác:

get(key) – Lấy giá trị của key nếu tồn tại, ngược lại trả về -1.
put(key, value) – Thiết lập hoặc chèn giá trị nếu key chưa có.

Khi cache đạt dung lượng tối đa, nó vô hiệu hóa phần tử ít được dùng nhất trước khi chèn phần tử mới.

Ví dụ: LFUCache khởi tạo với dung lượng 2, gọi: cache.put(1,1); cache.put(2,2); cache.get(1); cache.put(3,3); cache.get(2); cache.put(4,4); cache.get(1); cache.get(3); cache.get(4) → kết quả: 1, -1, 1, -1, 4.

Giải thuật

Khởi tạo: capacity, remain = capacity, least_freq = 1
node_for_freq: map lưu dữ liệu theo thứ tự chèn
node_for_key: map mới
Hàm _update(key, value): cập nhật tần suất
Hàm get(key): trả về giá trị hoặc -1
Hàm put(key, value): chèn hoặc cập nhật, xóa LFU khi hết chỗ

Ví dụ triển khai

import collections

class LFUCache:
    def __init__(self, capacity):
        self.remain = capacity
        self.least_freq = 1
        self.node_for_freq = collections.defaultdict(collections.OrderedDict)
        self.node_for_key = {}

    def _update(self, key, value):
        _, freq = self.node_for_key[key]
        self.node_for_freq[freq].pop(key)
        if len(self.node_for_freq[self.least_freq]) == 0:
            self.least_freq += 1
        self.node_for_freq[freq + 1][key] = (value, freq + 1)
        self.node_for_key[key] = (value, freq + 1)

    def get(self, key):
        if key not in self.node_for_key:
            return -1
        value = self.node_for_key[key][0]
        self._update(key, value)
        return value

    def put(self, key, value):
        if key in self.node_for_key:
            self._update(key, value)
        else:
            self.node_for_key[key] = (value, 1)
            self.node_for_freq[1][key] = (value, 1)
            if self.remain == 0:
                removed = self.node_for_freq[self.least_freq].popitem(last=False)
                self.node_for_key.pop(removed[0])
            else:
                self.remain -= 1
            self.least_freq = 1

cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3)
print(cache.get(2))
cache.put(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))

Đầu vào

cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

Đầu ra