0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Karentia

O(1)で追い出すLFU Cache：頻度リストとminFreqの更新

0
Posted at

原文の背景メモ: https://www.aceround.app/ja/blog/backend-developer-interview-ai

この記事は、バックエンド面接でよく出るキャッシュ設計を、Qiita向けに LFU Cache の O(1) 実装 として再構成したものです。前回の LRU Cache の続きです。

LFU Cache の2枚のマップ。key→node と freq→双方向リスト、minFreq=1

結論

LFU をヒープで書くと、挿入・参照・追い出しがすべて O(log n) になります。面接で求められるのは、だいたい次の形です。

  • get / put を 平均 O(1) にする
  • 頻度が最小のキーを捨てる
  • 最小頻度が複数あるときは、その中の LRU を捨てる

定数時間にするには、マップを2枚持つのが最短です。

役割 構造
キーからノードへ行く Map<K, Node>
同じ頻度の順序を保つ Map<number, 双方向リスト>
捨てるバケットを指す minFreq

ヒープは使いません。捨てる対象は、常に freq.get(minFreq) の末尾です。

LRU との差

LRU は「最近使った順」だけです。リストが1本あれば足ります。

LFU は「使った回数」が先です。回数が同じときだけ、最近使った順で決めます。全キーの頻度が 1 のあいだは、LFU は LRU と同じ動きになります。

LeetCode 460 の仕様もこれです。get も put の更新も、どちらも使用回数に数えます。

問題設定

容量 capacity のキャッシュを作ります。

const cache = new LFUCache<number, number>(2);
cache.put(1, 1); // {1: freq1}
cache.put(2, 2); // {1: freq1, 2: freq1}
cache.get(1);    // 1 の頻度が 2 になる
cache.put(3, 3); // 頻度1の 2 を捨てる

返す API は LRU と同じです。

get(key): value | undefined
put(key, value): void

見つからない get は undefined です。使用回数は増やしません。

不変条件

コードを書く前に、次の4つだけ決めます。壊れた実装のほとんどは、このどれかを破っています。

  1. map にあるノードは、必ずどれか1つの頻度リストに属する
  2. 各頻度リストの head.next が most recent、tail.prev が least recent
  3. minFreq は、いまキャッシュに残っている最小頻度を指す
  4. 新規キーの頻度は必ず 1。入れた直後の minFreq は 1

番兵ノードを置く理由は LRU と同じです。空リスト、先頭、末尾の分岐を消すためです。

TypeScript 実装

type LfuNode<K, V> = {
  key?: K;
  value?: V;
  freq: number;
  prev: LfuNode<K, V> | null;
  next: LfuNode<K, V> | null;
};

class FreqList<K, V> {
  private readonly head: LfuNode<K, V> = { freq: 0, prev: null, next: null };
  private readonly tail: LfuNode<K, V> = { freq: 0, prev: null, next: null };
  size = 0;

  constructor() {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get empty(): boolean {
    return this.size === 0;
  }

  addToFront(node: LfuNode<K, V>): void {
    const first = this.head.next;
    if (!first) throw new Error("broken list: head.next is missing");
    node.prev = this.head;
    node.next = first;
    first.prev = node;
    this.head.next = node;
    this.size++;
  }

  remove(node: LfuNode<K, V>): void {
    if (!node.prev || !node.next) {
      throw new Error("broken list: node is detached");
    }
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
    this.size--;
  }

  popLeastRecent(): LfuNode<K, V> {
    const lru = this.tail.prev;
    if (!lru || lru === this.head || lru.key === undefined) {
      throw new Error("broken list: LRU node is missing");
    }
    this.remove(lru);
    return lru;
  }
}

class LFUCache<K, V> {
  private readonly map = new Map<K, LfuNode<K, V>>();
  private readonly freq = new Map<number, FreqList<K, V>>();
  private minFreq = 0;

  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError("capacity must be a positive integer");
    }
  }

  get size(): number {
    return this.map.size;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.bump(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.bump(existing);
      return;
    }

    if (this.map.size === this.capacity) this.evict();

    const node: LfuNode<K, V> = { key, value, freq: 1, prev: null, next: null };
    this.map.set(key, node);
    this.list(1).addToFront(node);
    this.minFreq = 1;
  }

  private list(freq: number): FreqList<K, V> {
    let bucket = this.freq.get(freq);
    if (!bucket) {
      bucket = new FreqList<K, V>();
      this.freq.set(freq, bucket);
    }
    return bucket;
  }

  private bump(node: LfuNode<K, V>): void {
    const from = this.list(node.freq);
    from.remove(node);
    if (from.empty && this.minFreq === node.freq) this.minFreq++;
    node.freq++;
    this.list(node.freq).addToFront(node);
  }

  private evict(): void {
    const bucket = this.freq.get(this.minFreq);
    if (!bucket || bucket.empty) {
      throw new Error("broken cache: minFreq list is empty");
    }
    const victim = bucket.popLeastRecent();
    this.map.delete(victim.key as K);
  }
}

FreqList は「同じ頻度の LRU リスト」です。LFUCache 本体は、キー検索と minFreq の更新だけを担当します。

get で頻度を上げる

get の本体は bump です。既存キーの put も同じ関数を通ります。

get でノードを freq=f から外し、freq=f+1 の先頭へ移す流れ

private bump(node: LfuNode<K, V>): void {
  const from = this.list(node.freq);
  from.remove(node);
  if (from.empty && this.minFreq === node.freq) this.minFreq++;
  node.freq++;
  this.list(node.freq).addToFront(node);
}

ここが一番壊れやすいです。

minFreq を上げてよいのは、「いま外したリストが空になった」かつ「その頻度が最小だった」ときだけです。同じ頻度に他のキーが残っているなら、minFreq はそのままです。上の図だと、B を動かしても C が freq=1 に残るので、minFreq は 1 のままです。

新しいキーを入れたあとに minFreq = 1 へ戻すのも、同じ理由です。新規キーの頻度は必ず 1 なので、最小値は 1 に戻ります。

追い出し

満杯のときに新しいキーを入れると、minFreq のリスト末尾を捨てます。

if (this.map.size === this.capacity) this.evict();

走査しません。最小頻度のバケットは変数で指してあり、その中の LRU は tail.prev です。

同頻度の順序は、リストの付け替えだけで決まります。get や更新のたびに先頭へ移しているので、末尾が「その頻度のなかで一番使われていないキー」になります。

LeetCode 460 を手で追う

公式例を、頻度リストの中身まで書きます。左が most recent です。

put(1,1)  freq1: 1                 minFreq=1
put(2,2)  freq1: 2 - 1             minFreq=1
get(1)    freq1: 2
          freq2: 1                 minFreq=1
put(3,3)  freq1 の末尾 2 を捨てる
          freq1: 3
          freq2: 1                 minFreq=1
get(3)    freq2: 3 - 1             minFreq=2
put(4,4)  同頻度なので LRU の 1 を捨てる
          freq1: 4
          freq2: 3                 minFreq=1

put(4,4) の直前、1 と 3 はどちらも頻度 2 です。3 のほうが後から触っているので、捨てるのは 1 です。

動かして確認する

const cache = new LFUCache<number, number>(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1

cache.put(3, 3);
console.log(cache.get(2)); // undefined
console.log(cache.get(3)); // 3

cache.put(4, 4);
console.log(cache.get(1)); // undefined
console.log(cache.get(3)); // 3
console.log(cache.get(4)); // 4

同頻度の追い出しと、容量 1 も別ケースにします。

const tie = new LFUCache<string, number>(2);
tie.put("A", 1);
tie.put("B", 2);
tie.put("C", 3);
console.log(tie.get("A")); // undefined
console.log(tie.get("B")); // 2

const cap1 = new LFUCache<string, number>(1);
cap1.put("A", 1);
cap1.put("B", 2);
console.log(cap1.get("A")); // undefined
console.log(cap1.get("B")); // 2

Bun なら、クラス定義と同じファイルに置いて実行できます。

bun lfu-cache.ts

計算量

操作 時間 理由
get 平均 O(1) Map 検索 + リストの付け替え
put 更新 平均 O(1) 値の上書き + bump
put 新規 平均 O(1) 必要なら末尾削除 + freq=1 へ挿入
空間 O(capacity) ノードと、高々 capacity 本の頻度リスト

JavaScript の Map は平均 O(1) として話します。面接では「平均」と添えると正確です。

ヒープ版は実装が短いですが、put / get が O(log n) になります。定数時間が条件なら、この2枚マップのほうが説明しやすいです。

よくあるバグ

minFreq を走査で求め直す

空になったバケットを見たあと、1 から数え直す実装をときどき見ます。それだと追い出しが O(n) に戻ります。空になった瞬間に minFreq++ すれば足ります。頻度は 1 ずつしか増えないからです。

新規 put のあと minFreq を戻し忘れる

キャッシュ内のキーが全部頻度 3 になっていても、新しいキーは頻度 1 です。ここで minFreq を 1 に戻さないと、次の追い出しが頻度 3 側を切ってしまいます。

ヒットなのにリストを動かさない

LFU の同頻度タイブレークは LRU です。get で先頭へ移さないと、よく読んでいるキーが誤って捨てられます。LRU 単体と同じ罠です。

map だけ消してリストに残す

evict はリストから外したあと、必ず map.delete します。片方だけ更新すると、次の get が切り離されたノードを触ります。

面接で先に話す順番

コードより先に、この順で口に出すと通りやすいです。

  1. キー検索は HashMap
  2. 頻度ごとの順序は双方向リスト
  3. 捨てるバケットは minFreq
  4. 同頻度はリスト末尾が LRU
  5. 頻度は 1 ずつしか増えないので、空になったら minFreq++ で足りる

これが見えていれば、実装中にポインタで少し詰めても、設計は追ってもらえます。

容量 0 は仕様によって戻り値が違います。LeetCode は capacity = 0 を許しますが、ここでは正の整数に限定しています。問題文を先に確認してください。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?