লিস্ট ফ্রিকোয়েন্টলি ইউজড (LFU) ক্যাশ সিস্টেমের জন্য একটি ডেটা স্ট্রাকচার ডিজাইন ও ইমপ্লিমেন্ট করতে হবে। এটি নিচের অপারেশনগুলো সাপোর্ট করবে:
get(key) — কি যদি ক্যাশে থাকে তবে এর মান রিটার্ন করবে, নাইলে -1 রিটার্ন করবে।
put(key, value) — কি যদি ক্যাশে না থাকে তবে সেটি ইনসার্ট করবে।
যখন ক্যাশের সর্বোচ্চ ক্যাপাসিটিতে পৌঁছাবে, তখন কম ব্যবহৃত উপাদানটি (least frequently used) বাদ দিয়ে নতুন উপাদান ইনসার্ট করা হবে।
যেমন, LFUCache ক্যাপাসিটি ২ দিয়ে ইনিশিয়ালাইজ করলে এবং নিচের মেথডকলগুলো দিলে: 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।
ইনিশিয়ালাইজার ক্যাপাসিটি ভ্যালু নেবে।
remain := capacity
least_freq := 1
node_for_freq := ইনসার্ট অর্ডার অনুযায়ী ডেটা রাখার জন্য ম্যাপ
node_for_key := নতুন ম্যাপ
_update() ফাংশন ডিফাইন করবে (key, value প্যারামিটার लेकर)।
get() এবং put() ফাংশন ডিফাইন করবে।
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
# Testing
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3)
print(cache.get(2)) # -1
cache.put(4, 4)
print(cache.get(1)) # -1
print(cache.get(3)) # 1
print(cache.get(4)) # 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
