ヒープとLRUキャッシュ — 10件欲しいだけで100万件ソート

ヒープとLRUキャッシュ。優先するデータカードと段状のデータ模型、最近使ったカードの収納箱。

上位10件が欲しいだけで、100万件を並べ替える必要はありません。ヒープとLRUキャッシュを作って確かめます。

前回: バランス木とB木 — 100万件が3段で届く

これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で配列と連結リストまでやった人が、「では、順番を全部そろえずに『一番大きいものだけ』を速く出すには何を使うのか」を知るための記事です。飛ばしても本線は進みます。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。node -v で v20 以上が出れば大丈夫です。 作業場所は ~/cslab/heap/ です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私の環境の数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、条件を変えたときに何倍になるかです。


対象レベル: 中級〜上級 / 区分: 発展

目次

「人気ランキング上位10件」で、私は100万件を並べ替えていた

自分のサイトのアクセスログから、「よく読まれた記事の上位10件」を出そうとしたときの話です。

書いたコードは、こういう形でした。

// アクセス数の配列 counts から、上位10件を取る
counts.sort((a, b) => b - a);
const top10 = counts.slice(0, 10);

2行です。動きます。 何もおかしいと思いませんでした。

おかしいと思わなかった理由は、はっきりしています。私は「上位10件を取る」という問題を、「全部を順番に並べる」という問題に、無意識で置き換えていたのです。

並べ替えてから上から10個取れば、それは確かに上位10件です。正しい。

ただ、よく考えると、私は 10件のために、残りの999,990件を丁寧に並べ替えているわけです。

11位と12位のどちらが上かは、一切知る必要がありません。 500,000位と500,001位の順序も要りません。それでも sort は全部そろえます。そういう関数だからです。

件数が1,000件のときは、これで何も困りませんでした。100万件になったときに、目に見えて待たされるようになりました。

このとき私が調べて出てきた答えが、ヒープでした。そして読んで、2つのことに驚きました。

驚いた1つ目:ヒープは「木」なのに、配列1本で持てる。 連結リストのときに出てきたポインタ(次のノードへの参照)が、1つも要りません。 親と子は添字の計算だけで分かります。

驚いた2つ目:ヒープは、ソートされていない。 「一番小さいものが先頭にある」だけです。2番目がどこにいるかは決まっていません。 それでも上位10件は正しく出ます。

そして、この記事の後半でもう1つ驚きました。同じ話が、キャッシュの「何を捨てるか」に直結していたことです。

Redis の設定に maxmemory-policy という項目があります。私はここに allkeys-lru と書いてありましたが、なぜ lru なのか、lfu を選ぶと何が変わるのかを、まったく説明できませんでした。

この記事では、LRU を自分で書いて、LFU も書いて、同じアクセス列で走らせて、負けるほうを数字で見ます。 見たあとは、設定ファイルのその1行が、ただの呪文ではなくなります。

この記事でわかること

  • 「上位10件が欲しい」は、ソートの問題ではないこと。100万件の全ソートが 358ms、サイズ10のヒープなら 13.4ms(実測で 約26倍)。しかも結果は完全に一致する
  • ヒープは木なのに、ポインタが1つも要らないこと。完全二分木だから、親は (i-1)>>1、子は 2i+1 と 2i+2 という添字の計算だけで辿れる。配列1本で足りる
  • ヒープはソートされていないこと。条件は「親が子より小さい」だけで、左右のどちらが小さいかは決まっていない。内部配列を表示すると 1 3 2 5 9 8 7 のようにきれいに並んでいない
  • ヒープソートは V8 の sort より遅いこと。同じ O(n log n) でも実測で 1.2〜1.6倍遅い。O記法が同じでも速さは同じにならない
  • 素朴に書いた LRU キャッシュは、容量を増やすほど遅くなること。容量200で 728ms、容量1600で 8368ms(容量8倍で約11.5倍)。ハッシュマップ+双方向連結リストに直すと容量1600でも 37ms で、容量を増やしても遅くならない
  • JavaScript の Map は挿入順を保つので、Map だけで LRU が10行書けること。delete してから set し直すだけ
  • LFU(使われた回数が少ない順に捨てる)は、条件によって LRU に大負けすること。流行が入れ替わると、ヒット率が LRU 44.8% に対して LFU 21.1% まで落ちる。原因は「昔たくさん使われたもの」が25件、最後まで居座り続けたこと

この記事でやること

  1. ~/cslab/heap/ を作り、100万件の上位10件を「全ソート版」と「サイズ10のヒープ版」の2通りで書いて実測する
  2. 配列1本を木として読む表を出力し、同じ木を「図」と「配列」で並べて見比べる
  3. 二分ヒープ(push / pop / peek)を書き、内部配列を毎回表示して「ソートされていない」ことを目で確かめる
  4. ヒープソートを書いて Array.prototype.sort と競走させ、負けることを正直に測る
  5. 優先度付きキューにして、ジョブの追い越しが起きるところを出力で見る
  6. LRUキャッシュを素朴な O(n) 版で書いて遅さを測り、O(1) 版に直して比べ、容量を変えながらヒット率を表にする
  7. LRU・LFU・MFU・FIFO・ランダムを同じアクセス列で走らせ、LFU が居座りで負ける瞬間を出してから全部消す

先に知る言葉

基本的な言葉は用語集にもまとめてあります。ここではこの記事を読むのに必要な最小限だけ書きます。

言葉1〜2行の説明
ヒープ「親が子より小さい(または大きい)」という条件だけを守った木。一番小さい(大きい)1件を速く取り出すための道具。全体はソートされていない
完全二分木上の段から左詰めで隙間なく埋まっている二分木。隙間が無いから、配列に順番に詰めるだけで木になる
最小ヒープ / 最大ヒープ根(先頭)に最小が来るのが最小ヒープ、最大が来るのが最大ヒープ。条件の向きを逆にするだけで、実装はほぼ同じ
sift-up / sift-down追加した要素を親と比べながら上へ登らせるのが sift-up、根に置いた要素を子と比べながら下へ沈めるのが sift-down。日本語では「上方修正 / 下方修正」とも
優先度付きキュー「次に処理すべきもの」を優先度で取り出す入れ物。中身はほぼ必ずヒープ。名前にキューと入っているが追い越しが起きる
キャッシュ一度計算・取得した結果を、次に同じものを聞かれたとき用に手元に置いておく仕組み。置き場所は有限なので、埋まったら何かを捨てる
ヒット率聞かれたものがキャッシュに入っていた割合。ヒット ÷ (ヒット + ミス)。キャッシュの成績表
追い出し(eviction)容量が埋まったときに、どれを捨てるかを決めて捨てること。この記事の後半はここだけの話
LRULeast Recently Used。最後に使われたのが一番古いものから捨てる
LFULeast Frequently Used。使われた回数が一番少ないものから捨てる

① 上位10件のために、100万件を全部ソートしていた

まず作業場所を作ります。VMの中で打ちます。

bash
$ mkdir -p ~/cslab/heap
$ cd ~/cslab/heap
$ node -v

v20 以上が出れば大丈夫です。私の環境では v22.14.0 でした。

測定を再現できるようにする

最初に、毎回同じ乱数列が出る乱数を作ります。Math.random() を使うと実行するたびに違う数字になり、比べても意味が分からなくなるからです。

bash
$ cat > rnd.mjs <<'EOF'
  // mulberry32 — 毎回同じ列が出る乱数(測定を再現できるようにするため)
  export function makeRnd(seed) {
    return function () {
      seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
      let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
      t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
      return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
    };
  }
  EOF

中身の式は理解しなくて大丈夫です。「seed を渡すと、いつでも同じ乱数列を出してくれる関数」が返ってくるだけです。

ヒープを1つ書く

先に、この記事でずっと使う最小ヒープを作ってしまいます。中身の説明は②と③でやります。 ここでは動かすために置きます。

bash
$ cat > heap.mjs <<'EOF'
  // heap.mjs — 最小ヒープ(親が子より小さい)
  export class MinHeap {
    constructor() {
      this.a = [];          // これだけ。ポインタは1つも無い
    }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
  
    push(v) {
      this.a.push(v);             // まず末尾に置く
      let i = this.a.length - 1;
      while (i > 0) {             // 上へ登る(sift-up)
        const p = (i - 1) >> 1;   // 親の添字
        if (this.a[p] <= this.a[i]) break;
        [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
        i = p;
      }
    }
  
    pop() {
      if (this.a.length === 0) return undefined;
      const top = this.a[0];
      const last = this.a.pop();
      if (this.a.length === 0) return top;
      this.a[0] = last;           // 末尾を根に持ってくる
      let i = 0;
      const n = this.a.length;
      while (true) {              // 下へ沈む(sift-down)
        const l = 2 * i + 1, r = 2 * i + 2;
        let m = i;
        if (l < n && this.a[l] < this.a[m]) m = l;
        if (r < n && this.a[r] < this.a[m]) m = r;
        if (m === i) break;
        [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
        i = m;
      }
      return top;
    }
  }
  EOF

30行ちょっとです。 これで全部です。

2通りで上位10件を出す

bash
$ cat > 01-topk.mjs <<'EOF'
  import { MinHeap } from './heap.mjs';
  import { makeRnd } from './rnd.mjs';
  
  const N = 1_000_000, K = 10;
  const rnd = makeRnd(20261002);
  const data = [];
  for (let i = 0; i < N; i++) data.push(Math.floor(rnd() * 1e9));
  
  // A: 全部ソートしてから、上位10件だけ取る
  {
    const copy = data.slice();
    const t = performance.now();
    copy.sort((x, y) => y - x);
    const top = copy.slice(0, K);
    console.log('A 全部ソート     :', (performance.now() - t).toFixed(1), 'ms', top.slice(0, 3));
  }
  
  // B: サイズ10の最小ヒープを1回通すだけ
  {
    const t = performance.now();
    const h = new MinHeap();
    for (let i = 0; i < N; i++) {
      if (h.size() < K) h.push(data[i]);
      else if (data[i] > h.peek()) { h.pop(); h.push(data[i]); }
    }
    const top = [];
    while (h.size()) top.push(h.pop());
    top.reverse();
    console.log('B ヒープ(size10) :', (performance.now() - t).toFixed(1), 'ms', top.slice(0, 3));
  }
  EOF
$ node 01-topk.mjs

私の環境での出力です。

A 全部ソート     : 358.3 ms [ 999992357, 999991652, 999990398 ]
B ヒープ(size10) : 13.4 ms [ 999992357, 999991652, 999990398 ]

26倍です。そして結果は完全に一致しています。

なぜB版が速いのか

B版の中心は、この3行です。

if (h.size() < K) h.push(data[i]);
else if (data[i] > h.peek()) { h.pop(); h.push(data[i]); }

日本語にすると、こうです。

  1. ヒープに10件たまるまでは、とりあえず入れる
  2. 11件目以降は、「いま入っている10件の中で一番小さいもの」より大きいかだけを見る
  3. 大きければ、その一番小さいものを捨てて、新しいものを入れる
  4. 小さければ、何もしない

ここで 「いま入っている10件の中で一番小さいもの」を1回の操作で見られることが要点です。それが peek() です。配列の先頭を見るだけなので、比較は1回です。

これが「最小ヒープで上位10件を取る」の言い回しが最初ひっくり返って見える理由です。 上位(大きいほう)が欲しいのに、最小ヒープを使います。 ヒープに入っているのは「いまの暫定トップ10」で、そこから捨てたいのはその10件のうち一番弱いものです。だから最小を速く出せる入れ物が要る、という順序です。

O記法で言うと

計算量の書き方は本線の計算量とO記法の回でやりました。ここに当てはめると、こうなります。

版計算量100万件だと
A 全部ソートO(n log n)log₂(1,000,000) ≒ 20。100万 × 20 = 2000万 の比較オーダー
B サイズKのヒープO(n log K)log₂(10) ≒ 3.3。100万 × 3.3 = 330万 の比較オーダー

log の中身が n から K に変わっただけです。それだけで6倍。実測ではさらに、sort が要求する配列全体のコピーと書き戻しが無くなる分も乗って26倍になりました。

K を変えて確かめる

log K が効いているなら、K を増やすと遅くなるはずです。測ります。

bash
$ cat > 01b-varyk.mjs <<'EOF'
  import { MinHeap } from './heap.mjs';
  import { makeRnd } from './rnd.mjs';
  const N = 1_000_000;
  const rnd = makeRnd(20261002);
  const data = [];
  for (let i = 0; i < N; i++) data.push(Math.floor(rnd() * 1e9));
  for (const K of [Number(process.argv[2])]) {
    const t = performance.now();
    const h = new MinHeap();
    for (let i = 0; i < N; i++) {
      if (h.size() < K) h.push(data[i]);
      else if (data[i] > h.peek()) { h.pop(); h.push(data[i]); }
    }
    console.log('K=' + String(K).padStart(6), (performance.now() - t).toFixed(1).padStart(7) + 'ms');
  }
  EOF
$ for k in 10 100 1000 10000; do node 01b-varyk.mjs $k; done
K=    10    21.1ms
K=   100    22.9ms
K=  1000    24.2ms
K= 10000    48.9ms

K を1000倍にしても、2.3倍しか増えていません。 これが log K です。

この測定は、最初は失敗しました。 1つのプロセスの中で4つの K を続けて測ったら、K=1000 が一番速いという結果が出ました。詳しくは「つまずいたところ」に書きます。測定の順番で結果が変わるので、こういう比較はプロセスを分けて測る必要がありました。

📷 スクリーンショット01: node 01-topk.mjs の出力(A版とB版のミリ秒が2行並んでいるところ)。26倍の差が1画面に収まっているのがこの記事の出発点です。


② 木なのに、配列1本で持てる

ここが、私がこの記事を書きたくなった理由です。

前の回で連結リストを書いたとき、ノードごとに「次はどこか」を持たせました。 木にするなら、当然「左の子はどこか」「右の子はどこか」を持たせるものだと思っていました。

ヒープには要りません。

理由は「隙間が無い」から

ヒープが載っている木は完全二分木です。上の段から、左詰めで、隙間なく埋まっています。

            1              ← 添字 0
         /     \
       3         5          ← 添字 1, 2
      / \       / \
     7   9     8   6        ← 添字 3, 4, 5, 6

これを上の段から左から順に、配列に詰めると、こうなります。

添字:  0   1   2   3   4   5   6
値  :  1   3   5   7   9   8   6

隙間が無いので、「どこに入るか」に迷いがありません。 だから、添字だけで親子が計算できます。

知りたいもの計算式JavaScript
添字 i の親(i − 1) ÷ 2 の小数切り捨て(i - 1) >> 1
添字 i の左の子2i + 12 * i + 1
添字 i の右の子2i + 22 * i + 2
その子が存在するか添字が配列の長さ未満かl < a.length

>> 1 はビットを1つ右にずらす書き方で、2で割って小数を捨てるのと同じです。Math.floor((i - 1) / 2) と書いても同じ結果になります。

実際に確かめます。

bash
$ cat > 02-index.mjs <<'EOF'
  // 配列1本を「木」として読む練習。ポインタは1つも無い
  const a = [1, 3, 5, 7, 9, 8, 6];
  
  const parent = (i) => (i - 1) >> 1;
  const left   = (i) => 2 * i + 1;
  const right  = (i) => 2 * i + 2;
  
  console.log('配列:', a.join(' '));
  console.log('添字 | 値 | 親の添字 | 親の値 | 左の子 | 右の子');
  for (let i = 0; i < a.length; i++) {
    const p = parent(i), l = left(i), r = right(i);
    console.log(
      String(i).padStart(4),
      String(a[i]).padStart(3),
      String(i === 0 ? '-' : p).padStart(9),
      String(i === 0 ? '-' : a[p]).padStart(7),
      String(l < a.length ? `${l}(${a[l]})` : '-').padStart(8),
      String(r < a.length ? `${r}(${a[r]})` : '-').padStart(8),
    );
  }
  
  // 親が子より小さいか、全部の添字で確かめる
  let ok = true;
  for (let i = 1; i < a.length; i++) if (a[parent(i)] > a[i]) ok = false;
  console.log('ヒープの条件を満たしているか:', ok);
  EOF
$ node 02-index.mjs
配列: 1 3 5 7 9 8 6
添字 | 値 | 親の添字 | 親の値 | 左の子 | 右の子
   0   1         -       -     1(3)     2(5)
   1   3         0       1     3(7)     4(9)
   2   5         0       1     5(8)     6(6)
   3   7         1       3        -        -
   4   9         1       3        -        -
   5   8         2       5        -        -
   6   6         2       5        -        -
ヒープの条件を満たしているか: true

上の図と、この表を見比べてください。同じ木です。 図のほうが分かりやすいのは私も同意ですが、メモリに乗っているのは配列のほうだけです。

これが嬉しい理由は3つある

嬉しいこと中身
メモリが小さいノードごとのオブジェクトも参照も要らない。値を並べるだけ
キャッシュに乗りやすい隣の添字はメモリの上でも隣。連結リストのようにあちこちに散らない
バグが減る「参照の付け替えを忘れて木が壊れる」が起きない。壊れようがない(添字は計算で出る)

ただし、逆向きの制約もあります。 完全二分木でないものは、この持ち方ができません。 途中に隙間ができると添字の計算が合わなくなるからです。 ヒープの push が必ず末尾に足す、pop が必ず末尾を根に持ってくるのは、隙間を作らないためです。これは効率の工夫ではなく、この持ち方を成立させるための必須条件です。


③ 二分ヒープを書く — 登って、沈む

①で置いた heap.mjs の中身を見ます。やっていることは2つだけです。

push は「末尾に置いて、上へ登る」

push(v) {
  this.a.push(v);             // まず末尾に置く(隙間を作らない)
  let i = this.a.length - 1;
  while (i > 0) {             // 上へ登る(sift-up)
    const p = (i - 1) >> 1;   // 親の添字
    if (this.a[p] <= this.a[i]) break;   // 親が自分以下なら、もう条件を満たしている
    [this.a[p], this.a[i]] = [this.a[i], this.a[p]];   // 親と入れ替える
    i = p;
  }
}

親と比べて、自分のほうが小さいなら入れ替えて上がる。 それを親が自分以下になるまで繰り返すだけです。

登る回数は木の高さを超えません。高さは要素数 n に対して log₂ n です。100万件でも20回です。

pop は「末尾を根に持ってきて、下へ沈む」

pop() {
  const top = this.a[0];          // 返す値(最小)
  const last = this.a.pop();      // 末尾を抜く(ここで隙間が消える)
  if (this.a.length === 0) return top;
  this.a[0] = last;               // 末尾を根に置く(この時点で条件は壊れている)
  let i = 0;
  const n = this.a.length;
  while (true) {                  // 下へ沈む(sift-down)
    const l = 2 * i + 1, r = 2 * i + 2;
    let m = i;
    if (l < n && this.a[l] < this.a[m]) m = l;
    if (r < n && this.a[r] < this.a[m]) m = r;
    if (m === i) break;           // 自分が2人の子より小さいなら終わり
    [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
    i = m;
  }
  return top;
}

pop で「小さいほうの子」と入れ替えるのが要点です。 大きいほうの子と入れ替えてしまうと、入れ替えた先で条件が壊れます(新しい親が、もう一方の子より大きくなってしまう)。私はここを一度間違えて、pop の順番がぐちゃぐちゃになりました。

沈む回数も木の高さまで。push も pop も O(log n) です。

動かして、内部配列を全部見る

ここが一番見てほしいところです。

bash
$ cat > 03-run.mjs <<'EOF'
  import { MinHeap } from './heap.mjs';
  
  const h = new MinHeap();
  for (const v of [5, 3, 8, 1, 9, 2, 7]) {
    h.push(v);
    console.log('push', String(v).padStart(2), '→ 内部配列:', h.a.join(' '));
  }
  console.log('---');
  console.log('peek():', h.peek(), '(最小。ここだけは必ず正しい)');
  console.log('内部配列はソートされているか:',
    h.a.every((v, i) => i === 0 || h.a[i - 1] <= v));
  console.log('---');
  const out = [];
  while (h.size()) {
    const v = h.pop();
    out.push(v);
    console.log('pop →', String(v).padStart(2), '残り:', h.a.join(' ') || '(空)');
  }
  console.log('---');
  console.log('取り出した順:', out.join(' '));
  EOF
$ node 03-run.mjs
push  5 → 内部配列: 5
push  3 → 内部配列: 3 5
push  8 → 内部配列: 3 5 8
push  1 → 内部配列: 1 3 8 5
push  9 → 内部配列: 1 3 8 5 9
push  2 → 内部配列: 1 3 2 5 9 8
push  7 → 内部配列: 1 3 2 5 9 8 7
---
peek(): 1 (最小。ここだけは必ず正しい)
内部配列はソートされているか: false
---
pop →  1 残り: 2 3 7 5 9 8
pop →  2 残り: 3 5 7 8 9
pop →  3 残り: 5 8 7 9
pop →  5 残り: 7 8 9
pop →  7 残り: 8 9
pop →  8 残り: 9
pop →  9 残り: (空)
---
取り出した順: 1 2 3 5 7 8 9

最後の内部配列を見てください。

1 3 2 5 9 8 7

ソートされていません。 3 の次に 2 が来ています。

でもヒープの条件は全部満たしています。

            1
         /     \
       3         2
      / \       / \
     5   9     8   7
  • 添字0(値1)の子は 添字1(値3)と 添字2(値2)。1 < 3 かつ 1 < 2。OK
  • 添字1(値3)の子は 添字3(値5)と 添字4(値9)。3 < 5 かつ 3 < 9。OK
  • 添字2(値2)の子は 添字5(値8)と 添字6(値7)。2 < 8 かつ 2 < 7。OK

ヒープの条件は「親が子より小さい」だけです。 左の子と右の子のどちらが小さいかは、一切決まっていません。 ここが二分探索木との決定的な違いです。 二分探索木は「左 < 自分 < 右」なので、中順に辿ればソート済みの列が出ます。 ヒープは出ません。 逆に言うと、ヒープは守る約束が少ない。だから push も pop も安く済みます。

そして、pop を繰り返した「取り出した順」は 1 2 3 5 7 8 9 で、ちゃんと昇順です。

中はぐちゃぐちゃなのに、取り出す順番だけは正しい。 これがヒープです。

📷 スクリーンショット02: node 03-run.mjs の出力全体。内部配列が 1 3 2 5 9 8 7(ソートされていない)なのに、取り出した順が 1 2 3 5 7 8 9 になっているところが見えるように撮ります。


④ ヒープソートは、入れて出すだけ

前節の最後で、pop を繰り返すと昇順に出てきました。 ということは、これだけでソートになります。

function heapSort(src) {
  const h = new MinHeap();
  for (const v of src) h.push(v);              // 全部入れる
  const out = new Array(src.length);
  for (let i = 0; i < out.length; i++) out[i] = h.pop();   // 全部出す
  return out;
}

5行です。 n 回の push(各 O(log n))と n 回の pop(各 O(log n))なので、O(n log n)。sort と同じオーダーです。

しかも追加のメモリがほぼ要りません(元の配列の中でやる書き方にすれば、本当にゼロにできます)。

では、sort と同じくらい速いのでしょうか。 測ります。

bash
$ cat > 04-heapsort.mjs <<'EOF'
  import { MinHeap } from './heap.mjs';
  import { makeRnd } from './rnd.mjs';
  
  function heapSort(src) {
    const h = new MinHeap();
    for (const v of src) h.push(v);
    const out = new Array(src.length);
    for (let i = 0; i < out.length; i++) out[i] = h.pop();
    return out;
  }
  
  for (const N of [100_000, 200_000, 400_000, 800_000]) {
    const rnd = makeRnd(777 + N);
    const data = [];
    for (let i = 0; i < N; i++) data.push(Math.floor(rnd() * 1e9));
  
    const t1 = performance.now();
    const a = heapSort(data);
    const heapMs = performance.now() - t1;
  
    const copy = data.slice();
    const t2 = performance.now();
    copy.sort((x, y) => x - y);
    const sortMs = performance.now() - t2;
  
    const same = a.every((v, i) => v === copy[i]);
    console.log(
      'N=' + String(N).padStart(7),
      'ヒープソート', heapMs.toFixed(1).padStart(7) + 'ms',
      '| V8 sort', sortMs.toFixed(1).padStart(6) + 'ms',
      '| 比', (heapMs / sortMs).toFixed(2) + '倍',
      '| 結果一致', same
    );
  }
  EOF
$ node 04-heapsort.mjs
N= 100000 ヒープソート    42.6ms | V8 sort   26.2ms | 比 1.62倍 | 結果一致 true
N= 200000 ヒープソート    65.7ms | V8 sort   54.8ms | 比 1.20倍 | 結果一致 true
N= 400000 ヒープソート   156.7ms | V8 sort  131.5ms | 比 1.19倍 | 結果一致 true
N= 800000 ヒープソート   342.0ms | V8 sort  254.1ms | 比 1.35倍 | 結果一致 true

負けました。 1.2〜1.6倍遅いです。

これは「O記法が同じなら速さも同じ」ではないことの、はっきりした例です。 どちらも O(n log n) です。それでも定数倍で負けます。

負ける理由は、②で「嬉しいこと」として挙げたキャッシュの効きが、ここでは逆に働くからです。

  • sift-down は、添字 i から 2i+1 へ、そこから 4i+3 へと倍々で飛びます。n が大きいと、この飛び先はメモリの上でどんどん遠くなります
  • CPU はメモリからまとまった塊(キャッシュライン)で読み込むので、近くを順に読む処理は速く、遠くへ飛ぶ処理は遅い
  • V8 の sort は内部で TimSort(既にそろっている部分を見つけて活かす、隣同士をまとめる方式)を使っていて、メモリの読み方が素直です

では、ヒープソートを使う場面は無いのか。 そうでもありません。

ヒープソートが選ばれる理由中身
追加メモリがほぼゼロマージソートは作業用の配列が別に必要。組み込みなどメモリが厳しい所で効く
最悪ケースでも O(n log n)クイックソートは運が悪いと O(n²) に落ちる。ヒープソートは落ちない
途中で止められる「上位 k 件だけ欲しい」ならk 回 pop したところで打ち切れる。①がこれ

そして、①で26倍勝ったのは、まさに3つ目です。全部そろえないなら、ヒープのほうが強い。全部そろえるなら、sort に任せる。 この線引きが実測で出ました。

実務での結論はシンプルです。「ソートしたいだけなら sort を使う」。 自作のヒープソートを本番に入れる理由は、ほぼありません。ヒープを自作する価値は、sort にできないこと(上位k件・優先度・追い出し)にあります。


⑤ 「優先度付きキュー」の正体

前の回で、私は「優先度付きキューはキューではない」と書きました。名前にキューと入っているのに追い越しが起きるからです。

その中身が、いまここで書いたヒープです。

数字ではなくオブジェクトを入れられるように、比較の仕方を外から渡せる形に書き直します。

bash
$ cat > 05-pq.mjs <<'EOF'
  // 優先度付きキュー:数字ではなくオブジェクトを入れる
  class PriorityQueue {
    constructor(cmp) { this.a = []; this.cmp = cmp; }   // cmp(x,y) < 0 なら x が先
    get size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(v) {
      this.a.push(v);
      let i = this.a.length - 1;
      while (i > 0) {
        const p = (i - 1) >> 1;
        if (this.cmp(this.a[p], this.a[i]) <= 0) break;
        [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
        i = p;
      }
    }
    pop() {
      const top = this.a[0], last = this.a.pop();
      if (this.a.length) {
        this.a[0] = last;
        let i = 0; const n = this.a.length;
        for (;;) {
          const l = 2 * i + 1, r = 2 * i + 2; let m = i;
          if (l < n && this.cmp(this.a[l], this.a[m]) < 0) m = l;
          if (r < n && this.cmp(this.a[r], this.a[m]) < 0) m = r;
          if (m === i) break;
          [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
          i = m;
        }
      }
      return top;
    }
  }
  
  // 優先度が小さいほど先。同じ優先度なら、先に入れたほうが先(seq で決着)
  let seq = 0;
  const pq = new PriorityQueue((x, y) => x.pri - y.pri || x.seq - y.seq);
  const add = (name, pri) => pq.push({ name, pri, seq: seq++ });
  
  add('日次バッチ', 5);
  add('メール送信', 3);
  add('画像リサイズ', 3);
  add('障害アラート', 1);
  add('ログ圧縮', 9);
  console.log('投入順   : 日次バッチ(5) メール送信(3) 画像リサイズ(3) 障害アラート(1) ログ圧縮(9)');
  process.stdout.write('取り出し順: ');
  const out = [];
  while (pq.size) { const j = pq.pop(); out.push(`${j.name}(${j.pri})`); }
  console.log(out.join(' '));
  
  // 途中で「もっと急ぎの仕事」が飛び込んでくる場合
  console.log('---');
  seq = 0;
  const pq2 = new PriorityQueue((x, y) => x.pri - y.pri || x.seq - y.seq);
  [['A', 5], ['B', 5], ['C', 5]].forEach(([n, p]) => pq2.push({ name: n, pri: p, seq: seq++ }));
  console.log('1件処理:', pq2.pop().name);
  pq2.push({ name: '緊急', pri: 0, seq: seq++ });
  console.log('緊急を投入。以降の順:', [pq2.pop().name, pq2.pop().name, pq2.pop().name].join(' '));
  EOF
$ node 05-pq.mjs
投入順   : 日次バッチ(5) メール送信(3) 画像リサイズ(3) 障害アラート(1) ログ圧縮(9)
取り出し順: 障害アラート(1) メール送信(3) 画像リサイズ(3) 日次バッチ(5) ログ圧縮(9)
---
1件処理: A
緊急を投入。以降の順: 緊急 B C

最後に入れた「障害アラート」が、最初に出てきました。 キューなら最後です。

|| x.seq - y.seq を入れた理由

比較関数の2つ目の条件が、地味に大事です。

(x, y) => x.pri - y.pri || x.seq - y.seq

x.pri - y.pri が 0(優先度が同じ)のとき、|| の右側が使われて投入した順番(seq)で決着します。

これを入れないと、優先度が同じ2件の順序が「ヒープの内部の都合」で決まります。 ③で見たとおり、ヒープは左右の順序を保証しません。 だから投入順も保証されません。 出力で メール送信(3) が 画像リサイズ(3) より先に出ているのは、seq を入れたからです。入れなければ逆になることもあります。「同じ優先度なら先に来た順」を守りたいなら、自分で書く必要があります。これは安定ソートの話とまったく同じ構造です。

この形が使われている場所

場所何を優先度にしているか
ジョブキュー「障害アラートは日次バッチより先」のような業務上の緊急度。待たせるAPIをキューに逃がす話は本線でも扱いました
ダイクストラ法「いまわかっている最短距離」を優先度にして、一番近い地点から順に確定していく最短経路の求め方。カーナビや経路検索の基礎
イベントスケジューラ発生時刻を優先度にする。ゲームやシミュレーションで「次に起きるイベント」を取り出す
A* 探索ダイクストラ法に「ゴールまでの推定距離」を足したもの。ゲームの経路探索
ハフマン符号出現頻度の低い2つを取り出して合体させる、を繰り返す。ZIP などの圧縮の基礎

5つとも「次に処理すべき1件を速く取り出したい」だけです。同じ道具です。


⑥ LRUキャッシュを書く — 容量が埋まったら何を捨てるか

ここからが山場です。

キャッシュ自体は本線のRedisの回で入れました。「一度取ったものを手元に置いておく」という話です。

そのときに私が考えていなかったのが、「置き場所が埋まったらどうするのか」です。

Redis の設定にはこう書きます。

maxmemory 100mb
maxmemory-policy allkeys-lru

この2行目が、この節と次の節の全部です。

まず素朴に書く

「一番古いものを捨てる」を、思いついたまま書きます。

bash
$ cat > 06-lru-naive.mjs <<'EOF'
  // 素朴なLRU:配列に「使った時刻」を持ち、追い出すとき全部見る
  class NaiveLRU {
    constructor(cap) { this.cap = cap; this.items = []; this.clock = 0; }
    get(k) {
      const it = this.items.find((x) => x.k === k);   // ここが O(n)
      if (!it) return undefined;
      it.used = ++this.clock;
      return it.v;
    }
    set(k, v) {
      const it = this.items.find((x) => x.k === k);   // ここも O(n)
      if (it) { it.v = v; it.used = ++this.clock; return; }
      if (this.items.length >= this.cap) {
        let worst = 0;                                // ここも O(n)
        for (let i = 1; i < this.items.length; i++) {
          if (this.items[i].used < this.items[worst].used) worst = i;
        }
        this.items.splice(worst, 1);                  // splice も O(n)
      }
      this.items.push({ k, v, used: ++this.clock });
    }
  }
  
  for (const cap of [200, 400, 800, 1600]) {
    const c = new NaiveLRU(cap);
    const OPS = 200_000;
    const t = performance.now();
    for (let i = 0; i < OPS; i++) {
      const k = 'k' + (i % (cap * 4));
      if (c.get(k) === undefined) c.set(k, i);
    }
    console.log('容量', String(cap).padStart(5), '20万回:', (performance.now() - t).toFixed(1).padStart(8) + 'ms');
  }
  EOF
$ node 06-lru-naive.mjs
容量   200 20万回:    727.7ms
容量   400 20万回:   2652.3ms
容量   800 20万回:   4348.4ms
容量  1600 20万回:   8368.3ms

容量を8倍にしたら、11.5倍遅くなりました。

これは直感に反します。「キャッシュを大きくしたら速くなる」はずですよね。 逆でした。この実装では、キャッシュを大きくするほど1回の操作が遅くなるのです。 find は先頭から順に探すので中身が多いほど遅い。「一番古いものを探す」ループも中身を全部見る。splice は抜いたあとを全部ずらす。1回の get / set が O(n) です。

キャッシュは「速くするために入れるもの」なので、キャッシュ自体が遅いのは本末転倒です。直します。

ハッシュマップ+双方向連結リストで O(1) にする

遅い原因は、2つの「探す」です。

遅い操作いまどうしたいか
キーから値を探す配列を先頭から find一発で引く
一番古いものを探す全部の used を比べる探さずに、そこにある

1つ目はハッシュマップ(JavaScript の Map)で解けます。キーから一発で引くための道具です。

2つ目は、「使った順に並んだリスト」を持っておけば、探す必要がありません。 一番古いものは必ず末尾です。

そのリストは、双方向連結リストにします。前の回で書いたあれです。

なぜ双方向(前と次の両方を持つ)なのか。 リストの真ん中にあるノードを、O(1) で抜きたいからです。 片方向リストだと「抜きたいノードの1つ前」を知るために先頭から探し直しになり、O(n) に戻ります。前へのポインタを持っているから、その場で抜けるのです。 連結リストが「配列より速いことがある」のはこういう場面で、詳しくは配列と連結リストの回でやりました。ここで効いてきます。

書きます。

bash
$ cat > lru.mjs <<'EOF'
  // ハッシュマップ + 双方向連結リスト の LRU。get も set も O(1)
  export class LRU {
    constructor(cap) {
      this.cap = cap;
      this.map = new Map();               // key -> ノード
      this.head = { k: null, v: null };   // 番兵(新しい側)
      this.tail = { k: null, v: null };   // 番兵(古い側)
      this.head.next = this.tail;
      this.tail.prev = this.head;
      this.hit = 0; this.miss = 0; this.evicted = 0;
    }
    #unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }
    #toFront(n) {
      n.next = this.head.next; n.prev = this.head;
      this.head.next.prev = n; this.head.next = n;
    }
    get(k) {
      const n = this.map.get(k);
      if (!n) { this.miss++; return undefined; }
      this.hit++;
      this.#unlink(n); this.#toFront(n);   // 使ったので先頭へ移す
      return n.v;
    }
    set(k, v) {
      let n = this.map.get(k);
      if (n) { n.v = v; this.#unlink(n); this.#toFront(n); return; }
      if (this.map.size >= this.cap) {
        const old = this.tail.prev;        // 一番古い=末尾。探さない
        this.#unlink(old);
        this.map.delete(old.k);
        this.evicted++;
      }
      n = { k, v };
      this.map.set(k, n);
      this.#toFront(n);
    }
    keysNewToOld() {
      const out = [];
      for (let n = this.head.next; n !== this.tail; n = n.next) out.push(n.k);
      return out;
    }
  }
  EOF

head と tail の2つの番兵(sentinel)が、この実装を読みやすくしています。

番兵は「値を持たないダミーのノード」です。 これを両端に置くと、#unlink の中に if (n.prev === null) のような場合分けが1つも要らなくなります。 番兵が無いと、「先頭を抜くとき」「末尾を抜くとき」「1件しか無いとき」で3通りの分岐が必要になります。私は最初それを書いて、1件のときにリストが壊れました。 番兵を置いたら分岐が全部消えました。

動きを目で見て、それから測ります。

bash
$ cat > 06b-lru-o1.mjs <<'EOF'
  import { LRU } from './lru.mjs';
  
  // まず動きを目で見る(容量3)
  const c = new LRU(3);
  c.set('A', 1); c.set('B', 2); c.set('C', 3);
  console.log('新しい→古い:', c.keysNewToOld().join(' '));
  console.log('get(A) =', c.get('A'), '→', c.keysNewToOld().join(' '));
  c.set('D', 4);
  console.log('set(D) → 追い出されたのは B。中身:', c.keysNewToOld().join(' '));
  console.log('get(B) =', c.get('B'), '(もう無い)');
  console.log('hit=' + c.hit, 'miss=' + c.miss, 'evicted=' + c.evicted);
  
  console.log('---');
  for (const cap of [200, 400, 800, 1600]) {
    const cache = new LRU(cap);
    const OPS = 200_000;
    const t = performance.now();
    for (let i = 0; i < OPS; i++) {
      const k = 'k' + (i % (cap * 4));
      if (cache.get(k) === undefined) cache.set(k, i);
    }
    console.log('容量', String(cap).padStart(5), '20万回:', (performance.now() - t).toFixed(1).padStart(8) + 'ms');
  }
  EOF
$ node 06b-lru-o1.mjs
新しい→古い: C B A
get(A) = 1 → A C B
set(D) → 追い出されたのは B。中身: D A C
get(B) = undefined (もう無い)
hit=1 miss=1 evicted=1
---
容量   200 20万回:     47.3ms
容量   400 20万回:     49.7ms
容量   800 20万回:     37.1ms
容量  1600 20万回:     37.4ms

前半で、LRU の動きがそのまま見えています。

  • A B C を入れた直後、新しい順は C B A。一番古いのは A
  • そこで get('A') をすると、A が先頭に移る(A C B)。一番古いのは B になった
  • set('D') で容量オーバー。捨てられたのは B。A は直前に使ったので生き残った

「最後に使われたのが一番古いもの」を捨てる。これが LRU です。

そして後半の数字。

容量素朴な版O(1) 版差
200727.7ms47.3ms15倍
4002652.3ms49.7ms53倍
8004348.4ms37.1ms117倍
16008368.3ms37.4ms224倍

見てほしいのは倍率ではなく、O(1) 版の列が横一直線であることです。 容量を8倍にしても時間が増えていません。 むしろ少し減っています(容量が大きいとヒットが増えて set の回数が減るため)。 これが O(1) の意味です。「速い」ではなく「中身の数に左右されない」。

おまけ:Map だけで LRU が10行で書ける

ここまで50行ほど書きましたが、JavaScript には抜け道があります。

JavaScript の Map は、キーの挿入順を保ちます。 つまり Map 自体が、すでに順序付きのリストを内側に持っています。 それを使えば、連結リストを自分で書く必要がありません。

bash
$ cat > 06c-lru-map.mjs <<'EOF'
  // Map は挿入順を保つ。それだけで LRU になる
  class MapLRU {
    constructor(cap) { this.cap = cap; this.m = new Map(); }
    get(k) {
      if (!this.m.has(k)) return undefined;
      const v = this.m.get(k);
      this.m.delete(k);        // いったん消して
      this.m.set(k, v);        // 入れ直す → 挿入順の末尾(=最新)になる
      return v;
    }
    set(k, v) {
      if (this.m.has(k)) this.m.delete(k);
      else if (this.m.size >= this.cap) this.m.delete(this.m.keys().next().value); // 先頭=最古
      this.m.set(k, v);
    }
  }
  
  const c = new MapLRU(3);
  c.set('A', 1); c.set('B', 2); c.set('C', 3);
  console.log('古い→新しい:', [...c.m.keys()].join(' '));
  c.get('A');
  console.log('get(A) 後   :', [...c.m.keys()].join(' '));
  c.set('D', 4);
  console.log('set(D) 後   :', [...c.m.keys()].join(' '), '(Bが消えた)');
  
  console.log('---');
  for (const cap of [200, 1600]) {
    const cache = new MapLRU(cap);
    const OPS = 200_000;
    const t = performance.now();
    for (let i = 0; i < OPS; i++) {
      const k = 'k' + (i % (cap * 4));
      if (cache.get(k) === undefined) cache.set(k, i);
    }
    console.log('Map版 容量', String(cap).padStart(5), '20万回:', (performance.now() - t).toFixed(1).padStart(7) + 'ms');
  }
  EOF
$ node 06c-lru-map.mjs
古い→新しい: A B C
get(A) 後   : B C A
set(D) 後   : C A D (Bが消えた)
---
Map版 容量   200 20万回:    80.3ms
Map版 容量  1600 20万回:   228.0ms

動きは同じです。 追い出されたのは B。

要はこの2行です。

this.m.delete(k);   // いったん消す
this.m.set(k, v);   // 入れ直すと、挿入順の末尾に来る

「使ったキーを最新にする」を、delete してから set で実現しています。

そして一番古いキーは this.m.keys().next().value、つまりイテレータの1個目です。

ただし、速さは自作の連結リスト版に負けます。 容量200で 80.3ms(自作は47.3ms)、容量1600で 228.0ms(自作は37.4ms)。容量を増やすと遅くなっています。 Map の delete は、内部で削除済みの穴を作り、それが溜まると詰め直し(rehash)が走ります。get のたびに delete + set をしているので、穴を作り続けているわけです。 実務ではこの差はほぼ問題になりません。 「50行の自作」より「10行の Map」のほうがバグが入らないので、私は Map 版を選びます。自作版の価値は、中で何が起きているか分かることです。

ヒット率を測る — キャッシュを何%用意すればいいのか

ここまでは「速さ」の話でした。キャッシュの本当の成績は、ヒット率です。

現実のアクセスは一部のものに集中します(人気記事だけがよく読まれる)。それに近い形のアクセス列を作って、容量を変えながらヒット率を測ります。

bash
$ cat > 06d-hitrate.mjs <<'EOF'
  import { LRU } from './lru.mjs';
  import { makeRnd } from './rnd.mjs';
  
  // 現実に近いアクセス列を作る:一部の記事だけがよく読まれる(Zipfっぽい偏り)
  const KEYS = 1000, ACCESS = 100_000;
  const rnd = makeRnd(4242);
  const trace = [];
  for (let i = 0; i < ACCESS; i++) {
    // KEYS の r 乗にすると、番号の小さい「人気記事」に強く集中する(Zipf則の形)
    const r = rnd();
    trace.push('a' + (Math.ceil(Math.pow(KEYS, r)) - 1));
  }
  
  // 偏りの確認(上位10キーが全体の何%か)
  const count = new Map();
  for (const k of trace) count.set(k, (count.get(k) ?? 0) + 1);
  const top10 = [...count.values()].sort((a, b) => b - a).slice(0, 10)
    .reduce((s, v) => s + v, 0);
  console.log('異なるキー数:', count.size, '/ アクセス', ACCESS);
  console.log('上位10キーが占める割合:', (top10 / ACCESS * 100).toFixed(1) + '%');
  console.log('---');
  console.log('容量 | 全体に対する割合 | ヒット | ミス | ヒット率 | 追い出し回数');
  for (const cap of [1, 5, 10, 25, 50, 100, 200, 500, 1000]) {
    const c = new LRU(cap);
    for (const k of trace) { if (c.get(k) === undefined) c.set(k, 1); }
    const rate = c.hit / (c.hit + c.miss) * 100;
    console.log(
      String(cap).padStart(4),
      (String((cap / KEYS * 100).toFixed(1)) + '%').padStart(17),
      String(c.hit).padStart(7),
      String(c.miss).padStart(6),
      (rate.toFixed(1) + '%').padStart(9),
      String(c.evicted).padStart(13),
    );
  }
  EOF
$ node 06d-hitrate.mjs
異なるキー数: 999 / アクセス 100000
上位10キーが占める割合: 34.9%
---
容量 | 全体に対する割合 | ヒット | ミス | ヒット率 | 追い出し回数
   1              0.1%    2168  97832      2.2%         97831
   5              0.5%    9399  90601      9.4%         90596
  10              1.0%   16568  83432     16.6%         83422
  25              2.5%   30122  69878     30.1%         69853
  50              5.0%   41778  58222     41.8%         58172
 100             10.0%   54248  45752     54.2%         45652
 200             20.0%   67180  32820     67.2%         32620
 500             50.0%   85252  14748     85.3%         14248
1000            100.0%   99001    999     99.0%         0

表にすると、こうです。

キャッシュ容量全1000件に対する割合ヒット率
1件0.1%2.2%
10件1.0%16.6%
25件2.5%30.1%
100件10.0%54.2%
200件20.0%67.2%
500件50.0%85.3%
1000件100.0%99.0%

私がこの表で一番驚いたのは、10%のところです。

全体の10%しかキャッシュしていないのに、アクセスの54%がヒットしています。 1%(10件)でも16.6%。 100倍のデータのうち1%を手元に置くだけで、6回に1回は当たる。

これが「キャッシュは全部持たなくていい」の実物です。アクセスが偏っているからです。上位10キーだけで全アクセスの34.9%を占めていました。

もう1つ。容量1000(全部入る)にしても、ヒット率は 99.0% で 100% にはなりません。

ミスが 999 回残っています。これは「初めてアクセスされたとき」のミスで、どんなキャッシュでも避けられません。コールドミスと呼ばれます。1000種類のキーがあるので、ちょうど 999〜1000 回です。

キャッシュのヒット率を100%にはできません。 「初回は必ずミス」だからです。「ヒット率が上がらない」と悩む前に、上限がどこにあるかを計算するべきでした。

キャッシュを「どこに、いくつ置くか」という設計の話は、深掘りのキャッシュ層の回と更新の戦略の回でも扱っています。この節でやったのは、その1つの層の中身です。

📷 スクリーンショット03: node 06d-hitrate.mjs の表全体。容量10%でヒット率54.2%の行が見えるように撮ります。


⑦ 追い出し方は5種類ある — LFUが居座る話

さて、⑥では「最後に使われたのが古いもの」を捨てました。それが LRU です。

捨て方は他にもあります。 全部書いて、同じアクセス列で走らせて比べます。

方式何を捨てるか記録するもの
LRU最後に使われたのが一番古いもの最後に使った時刻
LFU使われた回数が一番少ないもの使われた回数
MFU使われた回数が一番多いもの使われた回数
FIFO入れたのが一番古いもの(使ったかは見ない)入れた時刻
ランダムくじ引き何も記録しない

MFU(多い順に捨てる)は一見あり得ませんが、「一度読んだら二度と読まない」種類のデータ(ログの流し読みなど)では理屈が立ちます。この記事では比較のための下限として置きます。

FIFO と LRU の違いは、「使ったときに順番を更新するかどうか」だけです。 FIFO は入れた順のまま。LRU は使うたびに先頭へ戻します。 ⑥の出力で get('A') が A を先頭に移していたのが、まさにその1行の差です。

5つを同じ形で書きます。違うのは「誰を捨てるか」を返す1行だけにします。

bash
$ cat > 07-policies.mjs <<'EOF'
  import { makeRnd } from './rnd.mjs';
  
  // 5つの追い出し方を、同じ形で並べる。違うのは「誰を捨てるか」だけ
  function makeCache(policy, cap, rnd) {
    const m = new Map();           // key -> { freq, used, added }
    let clock = 0;
    const worstBy = (score) => {
      let worstK = null, worstS = Infinity;
      for (const [k, e] of m) { const s = score(e); if (s < worstS) { worstS = s; worstK = k; } }
      return worstK;
    };
    const pickVictim = () => {
      switch (policy) {
        case 'LRU':    return worstBy((e) => e.used);        // 最後に使ったのが古い順
        case 'LFU':    return worstBy((e) => e.freq);        // 使われた回数が少ない順
        case 'MFU':    return worstBy((e) => -e.freq);       // 回数が多い順(=多いほど捨てる)
        case 'FIFO':   return worstBy((e) => e.added);       // 入れたのが古い順
        case 'RANDOM': { const ks = [...m.keys()]; return ks[Math.floor(rnd() * ks.length)]; }
        case 'LFU-DECAY': return worstBy((e) => e.freq);     // freq を定期的に半分にする
      }
    };
    let hit = 0, miss = 0, n = 0;
    return {
      access(k) {
        clock++;
        if (policy === 'LFU-DECAY' && ++n % 1000 === 0) {
          for (const e of m.values()) e.freq = Math.floor(e.freq / 2);  // 減衰
        }
        const e = m.get(k);
        if (e) { hit++; e.freq++; e.used = clock; return; }
        miss++;
        if (m.size >= cap) m.delete(pickVictim());
        m.set(k, { freq: 1, used: clock, added: clock });
      },
      get rate() { return hit / (hit + miss) * 100; },
      keys: () => [...m.keys()],
    };
  }
  
  const POLICIES = ['LRU', 'LFU', 'MFU', 'FIFO', 'RANDOM', 'LFU-DECAY'];
  
  function run(name, trace, cap) {
    console.log(`【${name}】 容量 ${cap} / アクセス ${trace.length}`);
    for (const p of POLICIES) {
      const rnd = makeRnd(99);
      const c = makeCache(p, cap, rnd);
      for (const k of trace) c.access(k);
      console.log('  ', p.padEnd(10), 'ヒット率', c.rate.toFixed(1).padStart(5) + '%');
    }
  }
  
  // (1) 偏りが変わらない、素直なアクセス列
  {
    const rnd = makeRnd(4242);
    const trace = [];
    for (let i = 0; i < 30_000; i++) trace.push('a' + (Math.ceil(Math.pow(1000, rnd())) - 1));
    run('人気が変わらない場合', trace, 100);
  }
  
  console.log();
  
  // (2) 途中で流行が入れ替わる列。LFU が居座りで負ける
  {
    const CAP = 30;
    // 前半:old0〜old24 だけを3万回読む(回数を思いきり稼がせる)
    const phase1 = [];
    for (let i = 0; i < 30_000; i++) phase1.push('old' + (i % 25));
    // 後半:old は一度も出てこない。new0〜new299 に偏って移る
    const rnd2 = makeRnd(31337);
    const phase2 = [];
    for (let i = 0; i < 30_000; i++) phase2.push('new' + (Math.ceil(Math.pow(300, rnd2())) - 1));
  
    console.log(`【途中で流行が入れ替わる場合】 容量 ${CAP}`);
    console.log('   方式        後半3万回のヒット率 / 最後まで居座った old の数');
    for (const p of POLICIES) {
      const rnd = makeRnd(99);
      const c = makeCache(p, CAP, rnd);
      for (const k of phase1) c.access(k);       // 前半(ここは全方式ほぼ100%)
      let hit = 0;
      for (const k of phase2) {
        if (c.keys().includes(k)) hit++;
        c.access(k);
      }
      console.log('  ', p.padEnd(10),
        (hit / phase2.length * 100).toFixed(1).padStart(14) + '%',
        String(c.keys().filter((k) => k.startsWith('old')).length).padStart(22));
    }
  }
  EOF
$ node 07-policies.mjs
【人気が変わらない場合】 容量 100 / アクセス 30000
   LRU        ヒット率  54.1%
   LFU        ヒット率  63.5%
   MFU        ヒット率  34.3%
   FIFO       ヒット率  48.5%
   RANDOM     ヒット率  47.9%
   LFU-DECAY  ヒット率  62.2%

【途中で流行が入れ替わる場合】 容量 30
   方式        後半3万回のヒット率 / 最後まで居座った old の数
   LRU                  44.8%                      0
   LFU                  21.1%                     25
   MFU                  30.7%                      0
   FIFO                 39.3%                      0
   RANDOM               39.4%                      0
   LFU-DECAY            52.9%                      0

1つ目の結果 — 人気が変わらないなら LFU が強い

方式ヒット率
LFU63.5%
LFU-DECAY62.2%
LRU54.1%
FIFO48.5%
ランダム47.9%
MFU34.3%

LFU が LRU に約9ポイント勝ちました。

理由は素直です。人気の順位が変わらないなら、「たくさん使われた」は「これからも使われる」の良い予測になります。LRU は一度きりのアクセスが1件来ただけで、人気記事を追い出してしまうことがあります。LFU は回数で見るので動じません。

そして FIFO とランダムがほぼ同じなのも面白いところです。FIFO は「何も見ていない」のと大差ないわけです。

2つ目の結果 — 流行が入れ替わると LFU が半分に落ちる

こちらが本題です。わざと LFU が負けるアクセス列を作りました。

  • 前半3万回: old0 〜 old24 の25件だけを、ひたすら読む(各1200回ずつ)
  • 後半3万回: old は一度も出てこない。 完全に別の new0 〜 new299 に移る
  • 容量は30件

結果です。

方式後半のヒット率最後まで居座った old の数
LFU-DECAY52.9%0
LRU44.8%0
FIFO39.3%0
ランダム39.4%0
MFU30.7%0
LFU21.1%25

LFU が最下位です。LRU の半分以下(21.1% 対 44.8%)。 右の列が原因です。old の25件が、最後まで1件も追い出されずに残っていました。

理由は簡単です。old の回数は1200回ずつ。新しく入る new は最初1回。 LFU は「回数が少ないもの」を捨てるので、捨てられるのは常に新入りです。 容量30のうち25が化石に占領され、実際に使えるのは5件だけでした。

これが LFU の弱点、「キャッシュ汚染(cache pollution)」です。

昔たくさん使われたものが、永久に居座る。 一度スターになったキーは、二度と使われなくなっても追い出せません。

対策 — 回数を減衰させる

対策は「回数を、時間が経つと減らす」です。表の一番上、LFU-DECAY がそれです。

やっていることはこの2行だけです。

if (++n % 1000 === 0) {
  for (const e of m.values()) e.freq = Math.floor(e.freq / 2);  // 全部半分にする
}

1000回アクセスごとに、全キーの回数を半分にする。 それだけです。

すると old の 1200 回は、1000アクセスごとに 600 → 300 → 150 → … と減っていき、やがて新入りの回数に追い抜かれて追い出されます。 右の列が 0 になっているのがその結果です。

そしてヒット率は 52.9% で、LRU の 44.8% より上になりました。「回数で見る」の強さを残したまま、居座りだけを消せたわけです。

Redis の設定は、まさにこの選択だった

ここまで書いたものが、そのまま Redis の設定項目です。

maxmemory 100mb
maxmemory-policy allkeys-lru

maxmemory-policy に指定できるものを、この記事で書いたものと並べます。

Redis の値この記事で書いたもの
noeviction捨てない。 容量を超えたら書き込みをエラーにする(読みは通る)
allkeys-lru⑥で書いた LRU。全キーが対象
allkeys-lfu⑦の LFU。しかも減衰付き(lfu-decay-time)
allkeys-random⑦のランダム
volatile-lru / volatile-lfu / volatile-random同じだが、有効期限(TTL)が付いているキーだけを対象にする
volatile-ttl残り時間が一番短いものから捨てる

私の設定にあった allkeys-lru は、⑥で自分で書いたあれでした。

そして公式ドキュメントを読み直すと、2つ、自分の実装と違うことが書いてありました。

1つ目:Redis の LRU は、正確な LRU ではありません。 ⑥では全キーを順序リストで正確に並べていました。Redis はやりません。キーを数件ランダムに抜き出し(既定5件)、その中で一番古いものを捨てるという近似です。 理由はメモリです。全キーを双方向連結リストで並べると、キー1つあたりのポインタ2本が丸ごと無駄になります。抜き出す件数は maxmemory-samples で増やせて、10 にするとほぼ正確な LRU に近づくとドキュメントに書かれています。

2つ目:Redis の LFU も近似で、しかも減衰が最初から入っています。 回数を正確に数えるのではなく、数バイトの確率的なカウンタで数え、lfu-decay-time(既定1分)ごとに減らします。⑦で私が2行足した減衰が、最初から仕様として入っているわけです。理由も同じで、「過去に人気だったものを、いつまでも人気扱いしないため」とはっきり書いてあります。

設定ファイルの1行の裏に、この記事で書いたものが全部入っていました。

判断表 — どれを選ぶか

状況選ぶもの理由
迷ったらLRU(allkeys-lru)ほとんどの現実のアクセスは偏っていて、しかも流行が変わる。 LRU は流行の変化に自動で付いていく。公式も「他を選ぶ理由が無ければこれ」と書いている
人気の順位がほぼ固定(マスタデータ、設定値)LFU(allkeys-lfu)回数のほうが良い予測になる。Redis の LFU は減衰付きなので、居座りも対策済み
全キーが同じくらいの頻度で、順に一巡するランダム(allkeys-random)順序を記録するコストが丸ごと無駄。LRU は一巡アクセスで最悪になる(毎回、次に必要なものを捨てる)
TTL を丁寧に付けているvolatile-ttlどれが要らないかをアプリ側が知っているなら、それに従うのが一番賢い
キャッシュではなくデータストアとして使っているnoeviction勝手に消えたら困るデータを、キャッシュ設定で消してはいけない。 エラーで気づくほうが良い
自分でコードに書くときMap 10行の LRU自作の連結リスト版は速いが、バグが入る。 差が問題になるまで Map で足りる

そして、どの方式を選んでも「測る」以外に答えはありません。 この記事の2つの実験で、同じ LFU が 63.5% と 21.1% になりました。 アクセス列が変わっただけです。 Redis の INFO stats は keyspace_hits と keyspace_misses を返します。hits ÷ (hits + misses) が、⑥で自分で計算したヒット率と同じものです。設定を変えたら、これを見る。 推測で選んで終わりにしない、というのは本線のパフォーマンス改善の回と同じ話です。


つまずいたところ

1. 「最小ヒープで最大10件を取る」が、頭で3回ひっくり返った

上位(大きいほう)が欲しいのに、最小ヒープを使う。 ここで完全に混乱して、最大ヒープで書き始めて動かなくなりました。

整理できたのは、ヒープに入っているものに名前を付けてからです。

  • ヒープの中身は「最終結果」ではなく、「いまのところの暫定トップ10」
  • 新しい候補が来たとき捨てたいのは、その10件の中で一番弱いもの
  • だから最小を速く出す入れ物が要る

「何を速く取り出したいか」で向きが決まる。 最大ヒープで書くと、暫定トップ10の中の最大が先頭に来てしまい、捨てるべき最弱を探すのに10件全部見ることになります。

2. 2 * i + 1 を 2 * i と書いて、無限ループになった

添字を1から始める書き方(2i / 2i+1、親は i/2)を先にどこかで見ていて、0から始める配列に混ぜてしまいました。

i = 0 のとき 2 * 0 = 0 で、自分が自分の子になります。 while が終わりません。

添字が0から始まるなら 2i+1 と 2i+2、1から始めて添字0を空けるなら 2i と 2i+1。 どちらでもいいが、混ぜると壊れます。 私は0から始める形(2i+1)に統一しました。

3. pop で「大きいほうの子」と入れ替えて、順番が壊れた

sift-down で、比較を1つしか書いていませんでした。

// 間違い:左の子とだけ比べていた
if (l < n && this.a[l] < this.a[i]) { 入れ替え; i = l; }

これだと、左が自分より大きく、右が自分より小さいときに何も起きずに終わります。

正しくは「自分・左・右の3つの中で一番小さいもの」を選んで入れ替えます。heap.mjs の let m = i; から始まる3行がそれです。候補を変数 m に持ってから1回だけ入れ替える書き方にすると、間違えにくくなりました。

4. K を変えた測定で、K=1000 が一番速いという結果が出た

①の最後の測定です。最初は1つのプロセスの中で4つの K を順に測りました。 結果がこれです。

K=    10    15.5ms
K=   100    25.3ms
K=  1000     6.9ms
K= 10000    22.3ms

K=1000 が K=10 の半分以下。 理屈に合いません。

原因はJITコンパイラとGCです。

  • Node.js(V8)は、同じコードが何度も呼ばれると、途中で機械語にコンパイルし直します。 3回目・4回目の測定は「温まった」状態で走ります
  • GC(メモリの掃除)は、いつ走るか分かりません。 1回目の測定中に走れば1回目だけ遅くなります

プロセスを分けたら、素直な結果になりました。

bash
$ for k in 10 100 1000 10000; do node 01b-varyk.mjs $k; done

「1回のプロセスの中で、A→B の順に測る」は、それだけで結果を歪めます。 後から測ったほうが速く出やすい。 ①のA/B比較(354ms と 13.4ms)は差が26倍なので順番の影響では説明できませんが、1.2倍のような差を測るときは、プロセスを分ける必要がありました。④のヒープソート対決も、比が 1.62 → 1.20 → 1.19 → 1.35 と揺れています。「1.2倍から1.6倍のあいだで負ける」までしか言えません。

5. 番兵を置かずに双方向連結リストを書いて、1件のときに壊れた

⑥の #unlink を、番兵なしで書いたときのコードです。

// 番兵が無いと、こうなる
if (n.prev) n.prev.next = n.next; else this.head = n.next;
if (n.next) n.next.prev = n.prev; else this.tail = n.prev;

分岐が2つ。 そして1件しか無いとき(prev も next も無い)に head と tail の両方を更新する必要があり、そこを書き忘れて、消したはずのノードが残りました。

番兵(値を持たないダミーノード)を両端に置くと、prev と next が絶対に null にならないので、分岐が全部消えます。

#unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }

1行になりました。 番兵は「メモリを2ノード余分に使って、バグを何個も消す」取引です。

6. Map 版 LRU で delete を忘れて、順番が更新されなかった

Map 版の get で、最初こう書きました。

// 間違い:delete していない
get(k) {
  if (!this.m.has(k)) return undefined;
  const v = this.m.get(k);
  this.m.set(k, v);        // これだけでは順番が変わらない
  return v;
}

動きます。値も正しく返ります。 ただ LRU として機能していません。

Map の set は、すでに存在するキーに対しては「値を上書きするだけ」で、挿入順を変えません。 順番を最後に持っていくには、いったん delete して、新しいキーとして set する必要があります。

これに気づいたのは、⑥のヒット率が LRU として不自然に低かったからです。keysNewToOld() のような中身を表示する関数を先に用意しておいたから気づけました。キャッシュは「動いているけど賢くない」状態になりやすく、エラーが出ません。

7. LFU が負ける例を作るのに、3回失敗した

⑦の2つ目の実験です。「LFU が居座りで負ける」を見せたいのに、最初の3回は LFU が勝ってしまいました。

試した条件結果なぜ失敗したか
old 10件 / new 50件を順に一巡 / 容量60全方式 99.9%容量が足りていた。 10 + 50 = 60 で追い出しが起きない
old 10件 / new 50件を順に一巡 / 容量30LRU が 0%一巡アクセスは LRU の最悪ケースで、LFU 以前に LRU が壊れる
old 10件 / new 300件に偏り / 容量30LFU が 47.0% で勝ち居座りは10件だけ。 残り20件で偏りを吸収できてしまった
old 25件 / new 300件に偏り / 容量30LFU 21.1% で最下位容量30のうち25が占領され、使えるのが5件だけになった

「弱点がある」と読んで納得するのと、「弱点が出る条件」を作れるのは別のことでした。 3回目までは、弱点はあるのに数字に出ていなかっただけです。old が何件残っているかを表示する列を足したら、1回目から居座りは起きていたことが分かりました。症状が出ていないだけで、原因はあったわけです。

そして2回目の失敗も、それ自体が学びでした。一巡アクセス(1,2,3,…,50,1,2,3,…)では、容量が1件足りないだけで LRU のヒット率が 0% になります。 次に必要になるものを、毎回ちょうど捨てるからです。Redis の公式が「一巡するアクセスなら allkeys-random」と書いている理由がこれでした。

8. performance.now() を Date.now() で書いて、0ms が並んだ

短い測定を Date.now() でやると、0 や 1 ばかり出ました。

Date.now() はミリ秒単位の整数しか返しません。13.4ms のようなものは測れず、13 か 14 になります。 数ミリ秒の測定だとほぼ意味のない数字になります。

performance.now() は小数点以下も返す高精度タイマーで、Node.js では追加の import なしで使えます(グローバルに performance があります)。

const t = performance.now();
// 測りたい処理
console.log((performance.now() - t).toFixed(1), 'ms');

後片づけ

作ったものは ~/cslab/heap/ の中だけです。丸ごと消します。

まず、消す前に何があるかを見ます。

bash
$ ls -la ~/cslab/heap/
01-topk.mjs  01b-varyk.mjs  02-index.mjs  03-run.mjs  04-heapsort.mjs
05-pq.mjs    06-lru-naive.mjs  06b-lru-o1.mjs  06c-lru-map.mjs
06d-hitrate.mjs  07-policies.mjs  heap.mjs  lru.mjs  rnd.mjs

14ファイル、全部この記事で作ったものです。 node_modules はありません(外部パッケージを1つも使っていないので npm install をしていません)。

消します。

bash
$ rm -rf ~/cslab/heap
$ ls ~/cslab

~/cslab が空になったなら、それも消します。

bash
$ rmdir ~/cslab 2>/dev/null
$ ls ~

rm -rf は確認を出さずに消します。 打つ前にパスを目で読んでください。 ~/cslab/heap です。先頭の ~/ を打ち忘れて相対パスになっていないか、pwd で今どこにいるかを確かめてからにします。

残るものは何もありません。 システムの設定も、パッケージも、サービスも触っていません。


まとめ — 理解できたこと

  • 「上位10件が欲しい」は、ソートの問題ではなかった。 100万件の全ソートが 358ms、サイズ10のヒープが 13.4ms で、結果は完全に一致した。 私は10件のために999,990件を並べ替えていた
  • sort を呼ぶ前に「本当に全部そろえる必要があるか」を聞く。 全部そろえるなら sort が最速。一部だけならヒープが勝つ。この線引きが実測で出た
  • ヒープは木なのに、ポインタが1つも要らない。 完全二分木で隙間が無いから、親は (i-1)>>1、子は 2i+1 と 2i+2 という添字の計算だけで辿れる。配列1本で足りる
  • push が必ず末尾に足し、pop が必ず末尾を根に持ってくるのは、効率の工夫ではない。 隙間を作らないための必須条件で、隙間ができたら添字の計算が成立しなくなる
  • ヒープはソートされていない。 条件は「親が子より小さい」だけで、左右の順序は決まっていない。内部配列は 1 3 2 5 9 8 7 のように並んでいないのに、pop を繰り返すと 1 2 3 5 7 8 9 と昇順に出る。守る約束が少ないから安い
  • だから優先度付きキューは、同じ優先度の順序を保証しない。 投入順を守りたいなら、比較関数に連番を自分で足す(x.pri - y.pri || x.seq - y.seq)
  • O記法が同じでも速さは同じにならない。 ヒープソートと V8 の sort はどちらも O(n log n) だが、実測で 1.2〜1.6倍負けた。sift-down が添字を倍々で飛ぶので、メモリの読み方が不利
  • 素朴に書いた LRU は、容量を増やすほど遅くなった。 容量200で 728ms、容量1600で 8368ms。キャッシュを大きくすると遅くなるキャッシュを私は書いていた
  • ハッシュマップ+双方向連結リストにすると、容量1600でも 37ms で横一直線になった。 O(1) の意味は「速い」ではなく「中身の数に左右されない」
  • 双方向にする理由は「真ん中のノードを O(1) で抜くため」。 片方向だと1つ前を探し直しで O(n) に戻る。番兵を両端に置くと #unlink が1行になり、場合分けが全部消える
  • JavaScript の Map は挿入順を保つので、Map だけで LRU が10行書ける。 delete してから set し直すだけ。自作版より遅いが、実務ではこれを選ぶ(バグが入らない)
  • 全体の10%しかキャッシュしていないのに、ヒット率は54.2%になった。 1%でも16.6%。キャッシュは全部持たなくていい。アクセスが偏っているから
  • ヒット率は100%にはならない。 全部入る容量でも 99.0% で止まり、残りは初回アクセスのミス(コールドミス)。上限を先に計算する
  • 同じ LFU が、条件によって 63.5% と 21.1% になった。 人気が固定なら LRU に9ポイント勝ち、流行が入れ替わると LRU の半分以下に落ちる。方式の優劣はアクセス列が決める
  • LFU が負けた原因は「昔たくさん使われた25件が、最後まで1件も追い出されなかった」こと。 容量30のうち25が化石に占領され、使えるのは5件だけだった(キャッシュ汚染)
  • 対策は「回数を定期的に半分にする」の2行。 それで居座りが消え、ヒット率が 52.9% になって LRU を超えた。Redis の allkeys-lfu には、この減衰が最初から入っている(lfu-decay-time)
  • Redis の LRU は正確な LRU ではなく、数件を抜き出して比べる近似だった。 全キーをリストで並べるとポインタの分だけメモリを食うから。maxmemory-samples で精度を上げられる
  • 迷ったら LRU。 現実のアクセスは偏っていて、しかも流行が変わる。LRU は変化に自動で付いていく。公式も「他を選ぶ理由が無ければこれ」と書いている
  • ただし、キャッシュではなくデータストアとして使っているなら noeviction。 消えたら困るデータを、キャッシュの設定で消してはいけない
  • 測定は、順番だけで結果が歪む。 1プロセスで4つ続けて測ったら K=1000 が最速という嘘が出た。JIT と GC のせい。プロセスを分けて測り直す
  • 短い時間は Date.now() では測れない。 ミリ秒の整数しか返らないので、13.4ms が 13 になる。performance.now() を使う

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 10 / 25 本目です。

記事
← 前の記事バランス木とB木 — 100万件が3段で届く
→ 次の記事ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Heap & Cache Eviction
  • ヒープは配列で持てる
  • LRU を O(1) にする

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次