โปรแกรมสร้าง Least Frequently Used (LFU) Cache ใน Python

คำอธิบายโจทย์

ต้องการสร้างโครงสร้างข้อมูล LFU Cache รองรับการดำเนินการ:

• get(key) - คืนค่าของ key ถ้ามีใน cache มิฉะนั้นคืน -1
• set(key, value) - เพิ่ม/อัปเดต key-value pair

เมื่อ cache เต็ม ต้องลบรายการที่ใช้บ่อยน้อยที่สุด (least frequently used) ก่อน แล้วค่อยเพิ่มรายการใหม่

ตัวอย่าง

LFUCache(capacity=2)
set(1,1), set(2,2), get(1)→1, set(3,3), get(2)→-1, set(4,4), get(1)→-1, get(3)→1, get(4)→4

วิธีแก้ปัญหา

ใช้ 2 Hash Map:

1. node_for_key: key → (value, frequency)
2. node_for_freq: frequency → OrderedDict(key → (value, frequency)) รักษาลำดับการแทรก (FIFO สำหรับ tie-break)
3. least_freq: ติดตาม frequency ต่ำสุดที่มีรายการอยู่
4. เมื่อ get/set: ย้าย key ไป freq+1, อัปเดต least_freq ถ้าจำเป็น
5. เมื่อเต็มและเพิ่มใหม่: ลบรายการแรกใน node_for_freq[least_freq] (FIFO)

โค้ด Python

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 = {}
    
    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))

อินพุต

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)

เอาต์พุต

1 -1 1 -1 4