मान लीजिए हम लीस्ट फ्रीक्वेंटली यूज्ड (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 होगा।
हल करने के चरण
इनिशियलाइज़र क्षमता मान लेगा
remain := क्षमता
least_freq := 1
node_for_freq := सम्मिलन क्रम के अनुसार डेटा रखने के लिए एक मैप
node_for_key := एक नया मैप
_update() फ़ंक्शन परिभाषित करें। यह key, value लेगा
x, freq := node_for_key[key]
node_for_freq[freq] से key के अनुरूप तत्व हटाएं
यदि node_for_freq[least_freq] का आकार 0 के समान है, तो
least_freq := least_freq + 1
node_for_freq[freq+1, key] := value, freq+1
node_for_key[key] := value, freq+1
get() फ़ंक्शन परिभाषित करें। यह key लेगा
यदि key, node_for_key में नहीं है, तो -1 लौटाएं
value := node_for_key[key, 0]
_update(key, value)
value लौटाएं
set() फ़ंक्शन परिभाषित करें। यह key, value लेगा
यदि key, node_for_key में है, तो _update(key, value)
अन्यथा,
node_for_key[key] := value, 1
node_for_freq[1, key] := value, 1
यदि remain, 0 के समान है, तो
removed := node_for_freq[least_freq] से FIFO क्रम में एक तत्व हटाएं
node_for_key से removed[0] के अनुरूप कुंजी हटाएं
अन्यथा, remain := remain - 1
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
