โปรแกรมที่จะใช้แคชที่ใช้บ่อยน้อยที่สุดใน Python

สมมติว่าเราต้องการใช้โครงสร้างข้อมูลสำหรับระบบแคชที่ใช้บ่อยน้อยที่สุด (LFU) ควรสนับสนุนการดำเนินการดังต่อไปนี้:

• get(key) − สิ่งนี้จะช่วยให้ได้รับค่าของคีย์หากมีคีย์อยู่ในแคช มิฉะนั้นจะคืนค่า -1

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

เมื่อแคชถึงความจุสูงสุด มันควรจะทำให้องค์ประกอบที่ใช้บ่อยน้อยที่สุดเป็นโมฆะก่อนที่จะแทรกองค์ประกอบใหม่

ดังนั้น ถ้า LFUCache ถูกเตรียมใช้งานด้วยความจุ 2 และเรียกใช้เมธอดเหล่านี้ 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 ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตัวเริ่มต้นจะใช้ค่าความจุ

• เหลือ :=ความจุ

• ความถี่ต่ำสุด :=1

• node_for_freq :=แผนที่สำหรับเก็บข้อมูลตามคำสั่งแทรก

• node_for_key :=แผนที่ใหม่

• กำหนดฟังก์ชัน _update() นี้จะใช้เวลาที่สำคัญค่า

• x ความถี่ :=node_for_key[คีย์]

• ลบองค์ประกอบออกจาก node_for_freq[freq] ที่สอดคล้องกับคีย์

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

  • ความถี่ต่ำสุด :=ความถี่ต่ำสุด + 1

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

• node_for_key[คีย์] :=ค่า freq+1

• กำหนดฟังก์ชัน get() นี่จะใช้เวลาที่สำคัญ

• ถ้าคีย์ไม่อยู่ใน node_for_key ไม่ใช่ศูนย์ ดังนั้น

  • กลับ -1

• ค่า :=node_for_key[key, 0]

• _update(คีย์, ค่า)

• คืนค่า

• กำหนดฟังก์ชัน set() นี้จะใช้เวลาที่สำคัญค่า

• หากคีย์ใน node_for_key ไม่ใช่ศูนย์ ดังนั้น

  • _update(คีย์, ค่า)

• มิฉะนั้น

  • node_for_key[คีย์] :=ค่า,1

  • node_for_freq[1, คีย์] :=ค่า,1

  • หากยังคงเท่ากับ 0 แล้ว

    • ลบ :=ลบหนึ่งองค์ประกอบจาก node_for_freq[least_freq] ใน fifoorder

    • ลบองค์ประกอบจาก node_for_key สอดคล้องกับคีย์ที่ถูกลบ[0]

  • มิฉะนั้น

    • เหลือ :=เหลือ − 1

• ความถี่ต่ำสุด :=1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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