मान लीजिए हम लीस्ट फ्रीक्वेंटली यूज्ड (LFU) कैश सिस्टम के लिए एक डेटा संरचना डिज़ाइन और कार्यान्वित करना चाहते हैं। यह निम्नलिखित संक्रियाओं का समर्थन करना चाहिए -
get(key) - यदि कुंजी कैश में मौजूद है तो उसका मान प्राप्त करने के लिए उपयोग किया जाएगा, अन्यथा -1 लौटाएगा।
put(key, value) - यदि कुंजी पहले से मौजूद नहीं है तो मान सेट या सम्मिलित करने के लिए उपयोग किया जाएगा।
जब कैश अपनी अधिकतम क्षमता तक पहुँच जाता है, तो नया तत्व सम्मिलित करने से पहले कम से कम उपयोग किए गए तत्व को अमान्य करना चाहिए।
इसलिए, यदि 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 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
इनिशियलाइज़र क्षमता मान लेगा
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 लौटाएं
put() फ़ंक्शन परिभाषित करें। यह 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
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
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
