PythonのLFUキャッシュ

Least Frequently Used（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になります。

これを解決するには、次の手順に従います-

• イニシャライザは容量値を取得します

• 残り：=容量

• least_freq：=1

• node_for_freq：=挿入順序に従ってデータを保持するためのマップ

• node_for_key：=新しいマップ

• 関数_update（）を定義します。これには重要な価値があります

• x、freq：=node_for_key [key]

• キーに対応するnode_for_freq[freq]から要素を削除します

• node_for_freq [least_freq]のサイズが0と同じ場合、

  • 最小_freq：=最小_freq + 1

• node_for_freq [freq + 1、key]：=value、freq + 1

• node_for_key [key]：=value、freq + 1

• 関数get（）を定義します。これが鍵になります

• node_for_keyにないキーがゼロ以外の場合、

  • -1を返す

• 値：=node_for_key [key、0]

• _update（key、value）

• 戻り値

• 関数put（）を定義します。これには重要な価値があります

  • node_for_keyのキーがゼロ以外の場合、

    • _update（key、value）

  • それ以外の場合

    • node_for_key [key]：=value、1

    • node_for_freq [1、key]：=value、1

    • 残りが0と同じ場合、

      • 削除：=node_for_freq[least_freq]からfifo順で1つの要素を削除

      • node_for_keyから要素を削除すると、削除されたキーに対応します[0]

    • それ以外の場合

      • 残る：=残る-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