পাইথনে Least Frequently Used (LFU) ক্যাশে ইমপ্লিমেন্টেশন

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

• get(key) — কী থাকলে ভ্যালু রিটার্ন করে, নাইলে -1।

• set(key, value) — কী-ভ্যালু জোড়া ইনসার্ট বা আপডেট করে।

উদাহরণ: ক্ষমতা ২-র LFUCache-এ set(1,1); set(2,2); get(1); set(3,3); get(2); set(4,4); get(1); get(3); get(4) কল করলে আউটপুট হবে 1, -1, 1, -1, 4।

সমাধানের ধাপসমূহ

1. ইনিশিয়ালাইজারে capacity নিন। remain := capacity, least_freq := 1।

2. node_for_freq := ফ্রিকোয়েন্সি অনুযায়ী অর্ডার্ড ডিকশনারি (OrderedDict)। node_for_key := সাধারণ ডিকশনারি।

3. _update(key, value) ফাংশন:

   • পুরানো ফ্রিকোয়েন্সি থেকে কী মুছুন।

   • যদি least_freq বাকেট খালি হয়, তবে least_freq++।

   • নতুন ফ্রিকোয়েন্সি freq+1-এ কী যোগ করুন।

4. get(key):

   • কী নাইলে -1 রিটার্ন।

   • ভ্যালু পাওয়া গেলে _update() কল করুন এবং ভ্যালু রিটার্ন করুন।

5. set(key, value):

   • কী থাকলে _update()।

   • নতুন কী হলে ফ্রিকোয়েন্সি ১-এ যোগ করুন।

   • যদি remain == 0 হয়, তবে least_freq বাকেট থেকে সবচেয়ে পুরানো (FIFO) কী মুছুন।

   • অন্যথায় remain--।

   • least_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