পাইথনে LFU ক্যাশে

ধরুন আমরা Least Frequently Used (LFU) ক্যাশে সিস্টেমের জন্য একটি ডেটা স্ট্রাকচার ডিজাইন ও বাস্তবায়ন করতে চাই। এটি নিম্নলিখিত ক্রিয়াকলাপগুলিকে সমর্থন করবে -

• get(key) – ক্যাশে কীটি বিদ্যমান থাকলে এটি কীটির মান পেতে ব্যবহার করা হবে, অন্যথায় -1 ফেরত দিন।

• পুট(কী, মান) - যদি কীটি ইতিমধ্যে উপস্থিত না থাকে তবে এটি মান সেট বা সন্নিবেশ করতে ব্যবহার করা হবে৷

যখন ক্যাশে তার সর্বোচ্চ ক্ষমতায় পৌঁছে যায়, তখন একটি নতুন উপাদান সন্নিবেশ করার আগে এটিকে সর্বনিম্ন ঘন ঘন ব্যবহৃত উপাদানটি বাতিল করা উচিত।

সুতরাং, যদি 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।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ইনিশিয়ালাইজার ক্যাপাসিটি ভ্যালু নিবে

• বাকি :=ক্ষমতা

• low_freq :=1

• node_for_freq :=সন্নিবেশের আদেশ অনুসারে ডেটা ধরে রাখার জন্য একটি মানচিত্র

• node_for_key :=একটি নতুন মানচিত্র

• একটি ফাংশন _update() সংজ্ঞায়িত করুন। এটি কী, মান লাগবে

• x, freq :=node_for_key[কী]

• node_for_freq[freq] কী

  এর সাথে সম্পর্কিত উপাদান থেকে মুছুন

• যদি node_for_freq[least_freq] এর আকার 0 এর মতো হয়, তাহলে

  • low_freq :=least_freq + 1

• node_for_freq[freq+1, key] :=মান, freq+1

• node_for_key[key] :=মান, freq+1

• একটি ফাংশন সংজ্ঞায়িত করুন get()। এটি কী লাগবে

• যদি node_for_key-এ কী নন-শূন্য হয়, তাহলে

  • রিটার্ন -1

• মান :=node_for_key[কী, 0]

• _আপডেট(কী, মান)

• ফেরত মান

• একটি ফাংশন put() সংজ্ঞায়িত করুন। এটি কী, মান লাগবে

  • যদি node_for_key-এর কী অ-শূন্য হয়, তাহলে

    • _আপডেট(কী, মান)

  • অন্যথায়,

    • node_for_key[key] :=মান,1

    • node_for_freq[1, key] :=মান,1

    • যদি অবশিষ্ট থাকে 0 এর মতো, তাহলে

      • সরানো হয়েছে :=ফিফো ক্রমে node_for_freq[least_freq] থেকে একটি উপাদান মুছুন

      • নোড_ফর_কি থেকে উপাদান মুছে ফেলা কী মুছে ফেলার সাথে সম্পর্কিত[0]

    • অন্যথায়,

      • অবশিষ্ট :=অবশিষ্ট - 1

    • low_freq :=1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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