LFU Cache (Least Frequently Used) ใน Python

สมมติว่าเราต้องการออกแบบและนำโครงสร้างข้อมูลสำหรับระบบแคช LFU (Least Frequently Used) มาใช้ ระบบควรรองรับการดำเนินการดังนี้ −

• get(key) – ใช้เพื่อดึงค่าของคีย์ หากคีย์มีอยู่ในแคช มิฉะนั้นคืนค่า -1

• put(key, value) – ใช้เพื่อตั้งค่าหรือแทรกค่า หากคีย์ยังไม่มีอยู่

เมื่อแคชถึงความจุสูงสุด ควรลบองค์ประกอบที่ถูกใช้งานน้อยที่สุด (least frequently used) ก่อนแทรกองค์ประกอบใหม่

เช่น หาก LFUCache เริ่มต้นด้วยความจุ 2 และเรียกเมธอดตามลำดับ: 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); ผลลัพธ์จะเป็น 1, -1, 1, -1, 4 ตามลำดับ

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

• Initializer รับค่า capacity

• remain := capacity

• least_freq := 1

• node_for_freq := Map เก็บข้อมูลตามลำดับการแทรก

• node_for_key := Map ใหม่

• กำหนดฟังก์ชัน _update() รับ key, value

• x, freq := node_for_key[key]

• ลบองค์ประกอบจาก node_for_freq[freq] ตาม key

• ถ้าขนาดของ node_for_freq[least_freq] เท่ากับ 0 แล้ว least_freq := least_freq + 1

• node_for_freq[freq+1, key] := value, freq+1

• node_for_key[key] := value, freq+1

• กำหนดฟังก์ชัน get() รับ key

• ถ้า key ไม่อยู่ใน node_for_key คืนค่า -1

• value := node_for_key[key, 0]

• _update(key, value)

• คืนค่า value

• กำหนดฟังก์ชัน put() รับ key, value

ตัวอย่างการใช้งาน

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

อินพุท

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)

เอาต์พุท

1
-1
1
-1
4