Chương trình triển khai bộ nhớ đệm Least Frequently Used (LFU) trong Python

Triển khai cấu trúc dữ liệu cho hệ thống bộ nhớ đệm Least Frequently Used (LFU). Hỗ trợ các thao tác:

• get(key): Trả về giá trị nếu key tồn tại, ngược lại trả về -1
• set(key, value): Thiết lập hoặc chèn giá trị nếu key chưa có

Khi bộ nhớ đệm đạt dung lượng tối đa, loại bỏ phần tử ít được sử dụng nhất trước khi chèn mới.

Ví dụ: LFUCache(2), các lệnh: set(1,1), set(2,2), get(1), set(3,3), get(2), set(4,4), get(1), get(3), get(4) → đầu ra: 1, -1, 1, -1, 4.

Giải pháp

Sử dụng hai dictionary:

• node_for_key: ánh xạ key -> (value, frequency)
• node_for_freq: ánh xạ frequency -> OrderedDict(key -> (value, frequency))
• least_freq: tần suất thấp nhất hiện tại
• remain: dung lượng còn trống

Khi get/set: cập nhật tần suất, di chuyển key sang bucket tần suất cao hơn. Khi hết chỗ: xóa key cũ nhất trong bucket least_freq (FIFO).

Ví dụ minh họa

from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity):
        self.remain = capacity
        self.least_freq = 1
        self.node_for_freq = defaultdict(OrderedDict)
        self.node_for_key = dict()
    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 set(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.set(1, 1)
cache.set(2, 2)
print(cache.get(1))
cache.set(3, 3)
print(cache.get(2))
cache.set(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))

Đầu vào

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

Đầu ra

1 -1 1 -1 4