पायथन में कम से कम बार-बार उपयोग किए जाने वाले कैश को लागू करने का कार्यक्रम

मान लीजिए कि हम कम से कम बार-बार उपयोग किए जाने वाले (एलएफयू) कैश सिस्टम के लिए डेटा संरचना लागू करना चाहते हैं। इसे निम्नलिखित कार्यों का समर्थन करना चाहिए:

• get(key) - यदि कुंजी कैश में मौजूद है, तो यह कुंजी का मान प्राप्त करने में मदद करता है, अन्यथा -1 लौटाता है।

• सेट (कुंजी, मान) - यदि कुंजी पहले से मौजूद नहीं है तो इसका उपयोग मान को सेट या सम्मिलित करने के लिए किया जाएगा।

जब कैश अपनी अधिकतम क्षमता तक पहुँच जाता है, तो उसे एक नया तत्व सम्मिलित करने से पहले कम से कम उपयोग किए जाने वाले तत्व को अमान्य कर देना चाहिए।

इसलिए, यदि LFUCache को क्षमता 2 के साथ प्रारंभ किया गया है और इन विधियों को कॉल करें cache.set(1, 1); कैशे.सेट(2, 2); कैश.गेट (1); कैशे.सेट(3, 3); कैश.गेट(2); कैशे.सेट(4, 4); कैश.गेट (1); कैश। प्राप्त करें (3); कैश। प्राप्त करें (4); तो आउटपुट क्रमशः 1,−1,1,−1,4 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• प्रारंभकर्ता क्षमता मान लेगा

• शेष :=क्षमता

• कम से कम_फ्रीक:=1

• node_for_freq :=इन्सर्ट ऑर्डर के अनुसार डेटा को होल्ड करने के लिए मैप

• node_for_key :=एक नया नक्शा

• फ़ंक्शन को परिभाषित करें _update() । यह कुंजी, मान लेगा

• एक्स, आवृत्ति:=नोड_फॉर_की [कुंजी]

• कुंजी के अनुरूप node_for_freq[freq] से तत्व हटाएं

• अगर node_for_freq[least_freq] का आकार 0 के समान है, तो

  • कम से कम_फ़्रेक :=कम से कम_फ़्रेक + 1

• node_for_freq[freq+1, key] :=value, freq+1

• node_for_key[key] :=value, freq+1

• एक फ़ंक्शन को परिभाषित करें get() । यह कुंजी लेगा

• यदि नोड_फॉर_की में नहीं है तो कुंजी गैर-शून्य है, तो

  • वापसी -1

• मान :=node_for_key[कुंजी, 0]

• _अपडेट (कुंजी, मान)

• वापसी मूल्य

• फ़ंक्शन सेट() को परिभाषित करें। यह कुंजी, मान लेगा

• यदि नोड_फॉर_की में कुंजी गैर-शून्य है, तो

  • _अपडेट (कुंजी, मान)

• अन्यथा,

  • node_for_key[कुंजी] :=मान,1

  • node_for_freq[1, key] :=value,1

  • यदि शेष 0 के समान है, तो

    • हटाया गया :=fifoorder में node_for_freq[least_freq] से एक तत्व हटाएं

    • नोड_फॉर_की से हटाए गए तत्व को हटाई गई कुंजी से मेल खाती है[0]

  • अन्यथा,

    • बने रहें :=बने रहें - 1

• कम से कम_फ्रीक:=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