पायथन में एलएफयू कैश

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

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

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

इसलिए, यदि LFUCache को क्षमता 2 के साथ प्रारंभ किया गया है और इन विधियों को कॉल करें cache.put(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 के समान है, तो
    - हटाया गया:=फीफो क्रम में node_for_freq[least_freq] से एक तत्व हटाएं
    - नोड_फॉर_की से हटाए गए तत्व को हटाई गई कुंजी से मेल खाती है[0]
  - अन्यथा,
    - शेष :=शेष - 1
  - कम से कम_फ्रीक:=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)

आउटपुट