Pythonで最も使用頻度の低いキャッシュを実装するプログラム

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

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

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

• 残り：=容量

• 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）

• 戻り値

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

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

  • _update（key、value）

• それ以外の場合

  • node_for_key [key]：=value、1

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

  • 残りが0と同じ場合、

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

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

  • それ以外の場合

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