পাইথনে সর্বনিম্ন ব্যবহৃত ক্যাশে বাস্তবায়নের জন্য প্রোগ্রাম

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

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

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

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

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

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

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

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

• 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-এ কী non−zero হয়, তাহলে

  • ফিরুন −1

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

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

• ফেরত মান

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

• যদি node_for_key-এ কী non−zero হয়, তাহলে

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

• অন্যথায়,

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

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

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

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

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

  • অন্যথায়,

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

• low_freq :=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