PythonでLFUキャッシュ（Least Frequently Used）を実装する方法

LFUキャッシュとは

LFU（Least Frequently Used：最低頻度使用）キャッシュは、使用頻度が最も低いデータを優先的に追い出すキャッシュアルゴリズムです。本記事では、Pythonを使ってLFUキャッシュのデータ構造を設計・実装する方法を解説します。

実装するLFUキャッシュは、以下の2つの操作をサポートする必要があります。

• get(key) – キーがキャッシュ内に存在する場合はその値を返し、存在しない場合は -1 を返します。
• put(key, value) – キーがまだ存在しない場合に、キーと値を設定または挿入します。

キャッシュが最大容量に達した場合は、新しい要素を挿入する前に、使用頻度が最も低い要素を無効化（削除）しなければなりません。同じ使用頻度の場合は、最も古く挿入された要素から削除します。

動作例

容量2でLFUCacheを初期化し、以下の順にメソッドを呼び出した場合を考えてみましょう。

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 の順になります。これは次のような流れによるものです。

1. put(1, 1) と put(2, 2) でキャッシュに {1=1, 2=2} が格納されます。
2. get(1) は 1 を返し、キー1の使用頻度が上がります。
3. put(3, 3) を呼ぶと容量が満杯のため、使用頻度が最も低いキー2が削除され、3が追加されます。
4. get(2) は既に削除されているため -1 を返します。
5. put(4, 4) では、この時点でキー1とキー3はどちらも使用頻度2ですが、キー1の方が先にアクセスされたため、キー1が削除されます。
6. 以降、get(1) は -1、get(3) は 1、get(4) は 4 を返します。

設計方針とアルゴリズム

この問題を解くために、以下の手順で実装を進めます。

• イニシャライザ（__init__）で容量を受け取ります。
• remain := 残り容量（capacity で初期化）
• least_freq := 現在の最小使用頻度（初期値は 1）
• node_for_freq := 使用頻度ごとに、挿入順序を保持してデータを管理するマップ（OrderedDict を使用）
• node_for_key := キーから (値, 頻度) への対応を保持するマップ

_update() メソッド

既存キーの値を更新し、使用頻度を1つ上げるための内部関数です。

• x, freq := node_for_key[key] から現在の頻度を取得
• node_for_freq[freq] から該当キーの要素を削除
• もし node_for_freq[least_freq] のサイズが 0 になったら、least_freq を +1 する
• node_for_freq[freq+1][key] := (value, freq+1) を登録
• node_for_key[key] := (value, freq+1) を更新

get() メソッド

• key が node_for_key に存在しない場合は -1 を返す
• value := node_for_key[key][0] で値を取得
• _update(key, value) を呼び出して頻度を更新
• value を返す

put() メソッド

• 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順で1要素を削除（popitem(last=False)）
    • node_for_key から removed[0] に対応する要素を削除
  • それ以外の場合：
    • remain := remain - 1
  • least_freq := 1 にリセット

Pythonでの実装例

それでは、実際の実装を見てみましょう。collections.OrderedDict を使うことで、各頻度グループ内の挿入順序を効率的に管理できます。

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

まとめ

この実装では、OrderedDict の性質を活かすことで、get・put の両操作をならし O(1) の時間計算量で実現しています。使用頻度ごとに要素をグループ化し、各グループ内では挿入順序を保持することで、「同頻度の場合は最も古い要素を削除する」というLFUの要件を満たしています。キャッシュアルゴリズムの理解を深める良い題材なので、ぜひ実際にコードを動かして挙動を確認してみてください。