1万件で100倍になることがあります。同じ処理をデータ量を変えて測り、O記法の意味を確かめます。
前回: 自分のOSがQEMUで起動する — OS自作の到達作品 これは【番外編】です。 このサイトの本筋は roadmap.sh に沿った段階で、計算量そのものを扱う回はそこにありません。 読まなくても順路は繋がります。飛ばして構いません。 それでも書いているのは、これまで「索引を張ると速い」「二重ループはやめる」と何度も書いてきたのに、どのくらい違うのかを一度も数字で出していないからです。 この記事のコマンドは、すべてVMの中(Ubuntu Server)で打ちます。 新しく入れるものはありません。使うのは
nodeだけです。
「このページ、遅いんですけど」と言われたことにします。
このとき、遅さには2種類あるという話を、まだ一度もしていません。
| 種類 | 起きること | どうなるか |
|---|---|---|
| どんなデータ量でも一定に遅い | 200ms が 400ms になる | 困るが、致命傷ではない。倍のマシンを買えば戻る |
| データが増えると加速して遅くなる | 1000件で 3ms、1万件で 300ms、10万件で 30秒 | マシンを倍にしても間に合わない。作り直しになる |
この2つはまったく別の問題です。 そして、開発中は絶対に区別できません。 手元のテストデータは100件しかないからです。100件では、どちらも一瞬で終わります。
区別できるようになるのが、この記事の目的です。
そのための道具が O記法(オーダー記法、O(n) みたいなやつ)です。見たことはあると思います。でも、たぶんこうなっているはずです。
O(n)は線形時間で、O(n²)は二乗時間で……(それで、結局どのくらい違うのか?)
この記事では、その「結局どのくらい」を先に出します。 説明はそのあとです。
- 数学は1つも使いません。 証明もしません
- 全部、自分のVMで測ります。 出てくる数字は全部、実際に
nodeを走らせた結果です - グラフと表で納得できたところで、初めてO記法の読み方を後付けで説明します
似たタイトルの記事があります。役割が違います。 この記事は1つの処理を、データ量を変えて測るを扱います。計算量とO記法|データ量が10倍で処理時間が100倍になる理由 は6種類の計算量を並べて実測し、表にするを扱います。
対象レベル: 中級 / 区分: 必要に応じて読む
この記事でわかること
- 「遅い」には2種類あること。倍遅いのと、データが増えると桁で遅くなるのは別問題だということ
MapやSetに変えると速くなるのは、コツではなく計算量が変わっていること。自作データベースの回で書いた索引と、まったく同じ話だということ- O記法が定数を無視する理由。「2倍」は環境で動くが、「件数に比例する」は動かないこと
- 計算量が良いほうが速いとは限らないこと。件数が小さいとき、
O(n²)がO(n)に勝つ(実測します) - 速さはメモリと交換して買っていること。索引はタダではないこと
この記事でやること
- 配列から1件探す処理を、1000 / 1万 / 10万 / 100万件で測る。 時間が件数に比例することを表で見る
- 同じ探索を
Mapでやって、件数を増やしても時間が変わらないことを見る - 重複検出の二重ループを測り、1000件から1万件で100倍になるところを出す。
Setで書き換えて測り直す - 二分探索にカウンタを入れて、100万件を何回の比較で終えるか数える
- 件数を小さくして測り直し、
O(n²)のほうが速い範囲があることを確かめる
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 計算量 | 「データが n 件のとき、処理の手間がどう増えるか」の見積もり。実行時間そのものではありません |
| O記法 | その増え方の書き方。O(n) は「件数に比例して増える」。読みは「オーダー n」 |
n | データの件数。この記事では配列の要素数のこと |
| 線形探索 | 先頭から1つずつ見ていって、目的のものが出たら止める探し方。for を回すだけ |
| 二分探索 | 並んでいるデータの真ん中を見て、半分を捨てる、を繰り返す探し方 |
| 最悪の場合 | 一番手間がかかるデータが来たとき。計算量は普通これで言います(理由は後述) |
Map / Set | JavaScript に最初から入っている入れ物。Map はキーと値の対、Set は重複しない値の集まり |
| ベンチマーク | 実際に動かして時間を測ること。この記事の中身はほぼこれです |
| 空間計算量 | 時間ではなくメモリがどう増えるかの見積もり |
準備 — 測る場所を作る
VMの中で、作業用のフォルダだけ作ります。
v22.14.0
バージョンは違って構いません。 v18 以降なら、この記事のコードはそのまま動きます。
注意: この記事の数字は、そのまま出ません。 CPUもメモリも違うからです。 大事なのは絶対値ではなく、件数を10倍にしたときに時間が何倍になるかです。 そこだけ見てください。
[スクリーンショット: 01_node確認.png] VMの中で node -v を実行し、バージョンが返っている画面を撮ってください。
同じ処理を、データ量を変えて測る
一番よく書くコードから始めます。 配列の中から、名前で1件探すだけです。
function makeUsers(n) {
const users = [];
for (let i = 1; i <= n; i++) users.push({ id: i, name: `user${i}` });
return users;
}
// 先頭から1つずつ見る(線形探索)
function findByName(users, name) {
for (let i = 0; i < users.length; i++) {
if (users[i].name === name) return users[i];
}
return null;
}
console.log("件数 1回あたり 1件あたり");
for (const n of [1000, 10000, 100000, 1000000]) {
const users = makeUsers(n);
const target = `user${n}`; // 一番最後 = 最後まで見ることになる
const TRIES = Math.max(20, Math.round(20000000 / n));
for (let i = 0; i < TRIES; i++) findByName(users, target); // 準備運転
const t0 = process.hrtime.bigint();
for (let i = 0; i < TRIES; i++) findByName(users, target);
const ms = Number(process.hrtime.bigint() - t0) / 1e6 / TRIES;
console.log(
`${String(n).padStart(9)} ${ms.toFixed(3).padStart(9)} ms ${(ms * 1e6 / n).toFixed(2).padStart(7)} ns`
);
}
書いていることを1つずつ確認します。
- 探す相手を
user${n}(一番最後)にしています。 途中で見つかると、運が良かっただけの数字が出るからです。ここが後で出てくる「最悪の場合」です process.hrtime.bigint()はナノ秒(10億分の1秒)まで測れる時計です。Date.now()はミリ秒までしか分からないので、この用途では使えませんTRIES回まわして割っています。 1回だけ測ると、他のプロセスに邪魔された1回を掴んでしまいます- 同じループを2回書いているのは書き間違いではありません。 1回目は「準備運転」です。理由は「つまずいたところ」に書きます
件数 1回あたり 1件あたり
1000 0.002 ms 2.13 ns
10000 0.019 ms 1.92 ns
100000 0.531 ms 5.31 ns
1000000 5.754 ms 5.75 ns
この表を、じっくり見てください。
| 件数 | 1回あたり | 前の行の何倍か |
|---|---|---|
| 1,000 | 0.002 ms | — |
| 10,000 | 0.019 ms | 約10倍 |
| 100,000 | 0.531 ms | 約28倍 |
| 1,000,000 | 5.754 ms | 約11倍 |
件数を10倍にすると、時間も約10倍になっています。 100,000 のところだけ28倍に飛んでいますが、それは後で説明します(そこが面白いところです)。
もっとはっきり見えるのは右の列です。
1件あたりの時間は、件数を1000倍にしても 2ns 〜 6ns の範囲に収まっています。
これが「比例している」の中身です。 1件を調べるコストは変わらない。だから全体の時間は、調べる件数でそのまま決まる。
この形を O(n) と書きます。 それだけです。
O(n)= 「件数が10倍になったら、時間も10倍になる」
100万件でも一瞬に見えることに注意する
5.754 ms です。 100万件を全部見て、6ミリ秒。
「じゃあ全然問題ないじゃないか」と思ったなら、それが罠です。 これが1リクエストにつき1回なら問題ありません。でも、
- 1リクエストで50回呼ぶ(一覧の各行で1回ずつ探す)なら 288ms
- 同時に10人が来たら、CPUはその10倍働く
遅さは、単体では出てきません。 パフォーマンスの回で「体感の遅さは1箇所で決まる」と書いたのは、これのことです。
Map にすると、件数が消える
同じ「名前で1件探す」を、Map でやります。
function makeUsers(n) {
const users = [];
for (let i = 1; i <= n; i++) users.push({ id: i, name: `user${i}` });
return users;
}
console.log("件数 索引の構築 1回あたり");
for (const n of [1000, 10000, 100000, 1000000]) {
const users = makeUsers(n);
// 「名前 -> ユーザー」の対応表をあらかじめ作る
const t0 = process.hrtime.bigint();
const byName = new Map();
for (const u of users) byName.set(u.name, u);
const buildMs = Number(process.hrtime.bigint() - t0) / 1e6;
const target = `user${n}`;
const TRIES = 2000000;
for (let i = 0; i < TRIES; i++) byName.get(target); // 準備運転
const t1 = process.hrtime.bigint();
for (let i = 0; i < TRIES; i++) byName.get(target);
const ms = Number(process.hrtime.bigint() - t1) / 1e6 / TRIES;
console.log(
`${String(n).padStart(9)} ${buildMs.toFixed(1).padStart(8)} ms ${ms.toFixed(6).padStart(10)} ms`
);
}
件数 索引の構築 1回あたり
1000 0.5 ms 0.000011 ms
10000 2.6 ms 0.000008 ms
100000 18.7 ms 0.000008 ms
1000000 548.5 ms 0.000007 ms
右の列が動いていません。
| 件数 | 線形探索 | Map | 差 |
|---|---|---|---|
| 1,000 | 0.002 ms | 0.000011 ms | 約180倍 |
| 10,000 | 0.019 ms | 0.000008 ms | 約2,400倍 |
| 100,000 | 0.531 ms | 0.000008 ms | 約66,000倍 |
| 1,000,000 | 5.754 ms | 0.000007 ms | 約82万倍 |
注目するのは「82万倍」ではありません。 そこは件数を変えれば動きます。注目するのは、差が件数と一緒に開いていくことです。
Map.get() は、件数が1000件でも100万件でも 7〜11ナノ秒です。 中身がどれだけ増えても、探す手間が増えません。
この形を O(1) と書きます。
O(1)= 「件数が何倍になっても、時間は変わらない」
「1回で終わる」という意味ではありません。 中では計算をしています(キーからハッシュ値を作って、その番地を見る)。その計算が、件数に関係ないというだけです。
[スクリーンショット: 02_線形とMap.png] node bench-linear.js と node bench-map.js の出力が、2つ並んで写るように撮ってください。
これは、データベースの索引とまったく同じ話
いま起きたことに、見覚えがあるはずです。
自作データベースの回で、こういうことをやりました。
- ファイルを先頭から読んでキーを探す → 遅い
- メモリ上に「キー → ファイルの何バイト目か」の
Mapを作る → 桁が変わる
あのとき足したのは Map です。 いまここで足したのも Map です。同じものです。
そして、パフォーマンスの回で EXPLAIN を見たとき、こうなりました。
| 索引 | EXPLAIN の rows | 意味 |
|---|---|---|
| 無し | 200000 | 20万行ぜんぶ見る = O(n) |
| 有り | 1 | 1行だけ見る = ほぼ O(1) |
EXPLAINのrowsは、その問い合わせの計算量を数字で出したものです。
「索引を張ると速い」の正体は、これです。 O(n) を O(1)(正確には索引の構造によって O(log n))に落とし替えている。魔法ではなく、いまこの記事で自分で作ったものと同じ仕組みです。
もう1つ、大事な副産物があります。
Map の構築に 548ms かかっています。 索引はタダではありません。100万件の索引を1回作るのに、線形探索95回ぶんの時間がかかっています。
索引は「1回作って、何度も引く」ときにだけ得をします。 1回しか引かないなら、素直に全部見たほうが速い。 これが、データベースで「索引を張りすぎると
INSERTが遅くなる」と言われる理由です。 書くたびに索引も直すからです。
二重ループを測る
次が本題です。 配列の中に重複があるか調べる、素朴な実装を測ります。
function makeIds(n) {
const ids = [];
for (let i = 1; i <= n; i++) ids.push(`id-${i}`);
return ids; // 重複なし = 最後まで比べることになる(最悪の場合)
}
// 素朴なやり方: 全部の組み合わせを比べる
function findDuplicatesSlow(ids) {
const dups = [];
for (let i = 0; i < ids.length; i++) {
for (let j = i + 1; j < ids.length; j++) {
if (ids[i] === ids[j]) dups.push(ids[i]);
}
}
return dups;
}
// 準備運転
for (let k = 0; k < 20; k++) findDuplicatesSlow(makeIds(500));
console.log("件数 二重ループ");
for (const n of [1000, 2000, 5000, 10000, 20000, 40000]) {
const ids = makeIds(n);
const t0 = process.hrtime.bigint();
findDuplicatesSlow(ids);
const ms = Number(process.hrtime.bigint() - t0) / 1e6;
console.log(`${String(n).padStart(8)} ${ms.toFixed(1).padStart(10)} ms`);
}
このコードは、たぶん一度は書いたことがあるはずです。 「配列の中の重複を探す」を素直に書くと、こうなります。動きます。バグもありません。
件数 二重ループ
1000 2.5 ms
2000 7.6 ms
5000 56.9 ms
10000 258.9 ms
20000 855.9 ms
40000 4321.8 ms
倍率を出します。
| 件数 | 時間 | 1000件の何倍か | 件数は何倍か |
|---|---|---|---|
| 1,000 | 2.5 ms | ×1 | ×1 |
| 2,000 | 7.6 ms | ×3 | ×2 |
| 5,000 | 56.9 ms | ×23 | ×5 |
| 10,000 | 258.9 ms | ×104 | ×10 |
| 20,000 | 855.9 ms | ×342 | ×20 |
| 40,000 | 4,321.8 ms | ×1,729 | ×40 |
件数を10倍にすると、時間は約100倍になりました。
40倍にしたら、約1,700倍です。 40 × 40 = 1,600。ほぼ「件数の2乗」で増えています。
この形を O(n²) と書きます。
O(n²)= 「件数が10倍になったら、時間は100倍になる」
ここが、この記事で一番言いたいところです。
1000件のとき、2.5ms です。誰も気付きません。 テストデータが1000件しかないうちは、このコードは「速いコード」に見えます。
そして本番でデータが4万件になると、4.3秒になります。 4万件は、少ないほうです。
- 1000件のときの2.5msを見て「問題ない」と判断した人は、間違っていません
- 間違っていたのは、「データ量が増えたらどうなるか」を測らなかったことです
なぜ2乗になるのか(数式は使いません)
外側のループが n 回まわり、その中で内側が最大 n 回まわります。 だから比較の回数は「n × n」。それだけです。
実際に数えれば、目で見えます。 if の行を数えるだけです。
| 件数 | 比較した回数 |
|---|---|
| 1,000 | 499,500 回 |
| 10,000 | 49,995,000 回 |
| 40,000 | 799,980,000 回 |
1000件を調べるのに50万回、4万件を調べるのに8億回比べています。「配列の中に重複があるか」を知りたいだけなのに、8億回です。
Set で書き換える
やることを変えます。 「全部の組み合わせを比べる」のをやめて、「1回通り過ぎながら、見たものを覚えておく」に変えます。
function makeIds(n) {
const ids = [];
for (let i = 1; i <= n; i++) ids.push(`id-${i}`);
return ids;
}
function findDuplicatesSlow(ids) {
const dups = [];
for (let i = 0; i < ids.length; i++) {
for (let j = i + 1; j < ids.length; j++) {
if (ids[i] === ids[j]) dups.push(ids[i]);
}
}
return dups;
}
// 1回通るだけ。見たものは Set に入れておく
function findDuplicatesFast(ids) {
const seen = new Set();
const dups = [];
for (const id of ids) {
if (seen.has(id)) dups.push(id);
else seen.add(id);
}
return dups;
}
// 準備運転
for (let k = 0; k < 20; k++) {
findDuplicatesSlow(makeIds(500));
findDuplicatesFast(makeIds(500));
}
console.log("件数 二重ループ Set");
for (const n of [1000, 2000, 5000, 10000, 20000, 40000]) {
const ids = makeIds(n);
let t0 = process.hrtime.bigint();
findDuplicatesSlow(ids);
const slow = Number(process.hrtime.bigint() - t0) / 1e6;
t0 = process.hrtime.bigint();
findDuplicatesFast(ids);
const fast = Number(process.hrtime.bigint() - t0) / 1e6;
console.log(`${String(n).padStart(8)} ${slow.toFixed(1).padStart(10)} ms ${fast.toFixed(2).padStart(7)} ms`);
}
件数 二重ループ Set
1000 2.5 ms 0.10 ms
2000 7.6 ms 0.23 ms
5000 56.9 ms 1.06 ms
10000 258.9 ms 1.16 ms
20000 855.9 ms 2.19 ms
40000 4321.8 ms 5.92 ms
右の列を見てください。 件数を40倍にして、時間は約60倍。比例しています。O(n) です。
そして、差が閉じていません。開いていきます。
| 件数 | 差 |
|---|---|
| 1,000 | 25倍 |
| 10,000 | 223倍 |
| 40,000 | 730倍 |
内側のループが、Set.has() に置き換わっただけです。 「探す」を O(n) から O(1) に変えたので、全体が O(n²) から O(n) になりました。山場①でやったことと、同じ操作です。
O(n²)を見つけたら、たいてい内側のループが「探している」だけです。 そこをMapかSetにできないか、をまず考える。それだけで桁が変わります。
[スクリーンショット: 03_二重ループとSet.png] node bench-dup2.js の出力全体(40000件の行まで)が写るように撮ってください。
測った結果から、O記法を後付けで読む
ここまでで、3つの形を実際に見ました。 ここで初めて、記法の説明をします。説明が後なのは、順番として正しいからです。
O は「何倍か」しか言っていない
O記法は、実行時間を予測するものではありません。
O(...)が言っているのは「データが増えたときの、増え方の形」だけです。
だから、次のことは全部言いません。
- 何ミリ秒かかるか
- どのCPUで動かすか
- あなたのコードが、他人のコードより速いか
言うのは「件数を10倍にしたら、何倍になるか」だけです。
なぜ定数を無視するのか
O(2n) とか O(n + 5) とは書きません。 全部 O(n) です。理由は、実測を見れば分かります。
山場①の表を、もう一度見てください。
| 件数 | 1件あたり |
|---|---|
| 1,000 | 2.13 ns |
| 10,000 | 1.92 ns |
| 100,000 | 5.31 ns |
| 1,000,000 | 5.75 ns |
10万件のところで、1件あたりが 1.9ns から 5.3ns に、いきなり2.8倍になっています。
バグではありません。 配列がCPUのキャッシュに収まらなくなって、メモリを取りに行く回数が増えただけです。512バイトの回で扱ったメモリの話が、そのまま速度に出ています。
つまり、「1件あたり何ナノ秒か」という定数は、同じCPUの同じプログラムでも、途中で勝手に3倍になります。
定数は環境で動く。だから約束にならない。 「件数に比例する」は、CPUが変わっても、言語が変わっても動かない。だから約束になる。
O記法が定数を捨てているのは、雑だからではありません。 「どうせ当てにならないもの」を最初から書かないようにしているだけです。
その代わり、こういう事故が起きます。
O(n)のコードAと、O(n)のコードB。Bのほうが100倍遅いことは普通にある- O記法が同じなら、あとは測るしかありません
なぜ「最悪の場合」を言うのか
山場①で、探す相手をわざと一番最後にしました。 先頭を探せば、線形探索は O(1) に見えます。
でも、それは「運が良かったとき」の話です。
| 言い方 | 線形探索の場合 | 使い道 |
|---|---|---|
| 最良の場合 | 1回(先頭にあった) | ほぼ役に立たない |
| 平均の場合 | n / 2 回 | 統計を取れるなら意味がある |
| 最悪の場合 | n 回(最後にあった/無かった) | これで設計する |
最悪の場合で言うのは、「一番ひどいときにどうなるか」を知りたいからです。
サービスが落ちるのは、平均のときではありません。 一番条件が悪いデータが来たときです。平均が速いことは、何の保証にもなりません。
正規表現を自作した回で、「ほとんどの入力では一瞬なのに、ある入力で固まる」ものを実際に作りました。 あれが「平均は速いが、最悪が壊滅的」の実物です。 攻撃者は、その最悪のほうを狙って送ってきます。
覚えるのは、この5つだけ
アルゴリズムの本には20種類くらい出てきます。 実務で判断に使うのは、この5つです。
| 記法 | 呼び方 | 件数を10倍にすると | 代表例 | 100万件で |
|---|---|---|---|---|
O(1) | 定数時間 | 変わらない | Map.get / Set.has / 配列の [i] | 一瞬 |
O(log n) | 対数時間 | ほんの少し増える | 二分探索 / データベースの索引 | 一瞬(後で数えます) |
O(n) | 線形時間 | 10倍 | for で全部見る / includes / filter | 数ミリ秒〜 |
O(n log n) | — | 10倍より少し多い | sort | 1秒未満 |
O(n²) | 二乗時間 | 100倍 | 二重ループ | 現実的でない |
判断の基準は、実質1本の線です。
O(n log n)までは、100万件でもだいたい通る。O(n²)は通らない。
O(n²) を見つけたときだけ、真面目に書き直す。 それ以外は、まず測る。それで足ります。
O(log n) を体感する
O(log n) だけは、表を見てもピンときません。 数えて確かめます。
二分探索です。 並んでいるデータの真ん中を見て、目的の値より大きければ後ろ半分を捨てる。それを繰り返すだけです。
function binarySearch(sorted, target) {
let low = 0;
let high = sorted.length - 1;
let count = 0; // 何回比べたかを数える
while (low <= high) {
count++;
const mid = Math.floor((low + high) / 2);
if (sorted[mid] === target) return { index: mid, count };
if (sorted[mid] < target) low = mid + 1; // 前半を捨てる
else high = mid - 1; // 後半を捨てる
}
return { index: -1, count };
}
function linearCount(arr, target) {
for (let i = 0; i < arr.length; i++) if (arr[i] === target) return i + 1;
return arr.length;
}
console.log("件数 線形探索の回数 二分探索の回数");
for (const n of [1000, 10000, 100000, 1000000]) {
const sorted = [];
for (let i = 1; i <= n; i++) sorted.push(i); // すでに並んでいる
const target = n; // 一番最後 = 最悪の場合
const r = binarySearch(sorted, target);
console.log(
`${String(n).padStart(9)} ${String(linearCount(sorted, target)).padStart(12)} 回 ${String(r.count).padStart(9)} 回`
);
}
時間ではなく、回数を数えています。 時間はCPUで変わりますが、回数は誰がやっても同じ数字が出ます。
件数 線形探索の回数 二分探索の回数
1000 1000 回 10 回
10000 10000 回 14 回
100000 100000 回 17 回
1000000 1000000 回 20 回
100万件から探すのに、20回です。
件数を1000倍(1000 → 100万)にして、回数は10回から20回。2倍にしかなっていません。
理由は1行で言えます。
1回比べるたびに、残りが半分になるからです。
100万 → 50万 → 25万 → 12.5万 → …… と半分にしていくと、20回で1になります。
| 件数 | 半分にする回数 |
|---|---|
| 1,000 | 10回 |
| 100万 | 20回 |
| 10億 | 30回 |
件数が1000倍になっても、10回しか増えません。 これが O(log n) です。
O(log n)= 「件数が桁で増えても、手間は少ししか増えない」
log を計算できる必要はありません。 「半分にしていくと何回で終わるか」だと理解しておけば、実務では困りません。
ただし、並んでいなければ使えない
上のコードは push(i) で作ったので、最初から並んでいます。 本物のデータは並んでいません。
並べ替えてから二分探索する、という手が浮かびます。数字を出します。
| 件数 | 並べ替え(sort) | 二分探索1回 |
|---|---|---|
| 1,000 | 0.5 ms | 10回の比較 |
| 10,000 | 2.5 ms | 14回の比較 |
| 100,000 | 28.2 ms | 17回の比較 |
| 1,000,000 | 368.8 ms | 20回の比較 |
100万件を並べ替えるのに369ms。 線形探索1回が5.75msだったので、64回ぶんです。
1回だけ探すなら、並べ替えるだけ損です。 素直に全部見たほうが速い。 並べ替えが得になるのは、同じ配列を何度も探すときだけです。
これは、さっき Map の構築で出たのと同じ結論です。 そして、データベースが索引を「あらかじめ作って持っておく」理由でもあります。 問い合わせのたびに並べ替えていたら、間に合いません。
[スクリーンショット: 04_二分探索の回数.png] node bench-binary.js の出力(100万件で20回になっている行まで)を撮ってください。
並べ替えは自分で書かない
上で sort を使いました。中身の話を少しだけします。
function makeIds(n) {
const a = [];
for (let i = 0; i < n; i++) a.push(Math.floor(Math.random() * n * 10));
return a;
}
console.log("件数 並べ替え 1件あたり");
for (const n of [1000, 10000, 100000, 1000000]) {
const a = makeIds(n);
const t0 = process.hrtime.bigint();
a.sort((x, y) => x - y);
const ms = Number(process.hrtime.bigint() - t0) / 1e6;
console.log(`${String(n).padStart(9)} ${ms.toFixed(1).padStart(8)} ms ${(ms * 1e6 / n).toFixed(0).padStart(7)} ns`);
}
件数 並べ替え 1件あたり
1000 0.5 ms 465 ns
10000 2.5 ms 247 ns
100000 28.2 ms 282 ns
1000000 368.8 ms 369 ns
件数を10倍にすると、時間は10〜13倍。 O(n) より少しだけ大きい。これが O(n log n) です。
Array.prototype.sort は O(n log n) です。 そして、これより速い並べ替えは、一般には存在しません(値を比べて並べる限り)。
並べ替えのアルゴリズムを自分で書く必要はありません。 バブルソートもクイックソートも、書けなくても実務で困りません。
sortは各処理系がすでに最適化済みのものを持っています。自分で書くと、遅くて、バグります。
知っておくべきなのは1つだけです。
sortはO(n log n)。 100万件で0.4秒くらいかかる- だから、ループの中で
sortを呼んではいけません。 それだけでO(n² log n)になります
sort にはもう1つ落とし穴があります。
[10, 9, 100].sort(); // → [10, 100, 9] 文字列として比べている
[10, 9, 100].sort((a, b) => a - b); // → [9, 10, 100]
比較関数を渡さないと、文字列として並べ替えます。 JavaScriptの基本の回で見た「"1" と 1」の問題が、ここにも出ています。
計算量が全てではない
ここまで読むと、こう思うはずです。
二重ループを見つけたら、全部
Setに書き換えればいい。
違います。測ります。
function findDuplicatesSlow(ids) {
const dups = [];
for (let i = 0; i < ids.length; i++)
for (let j = i + 1; j < ids.length; j++)
if (ids[i] === ids[j]) dups.push(ids[i]);
return dups;
}
function findDuplicatesFast(ids) {
const seen = new Set();
const dups = [];
for (const id of ids) {
if (seen.has(id)) dups.push(id);
else seen.add(id);
}
return dups;
}
function makeIds(n) {
const a = [];
for (let i = 1; i <= n; i++) a.push(`id-${i}`);
return a;
}
const TRIES = 200000;
console.log("件数 二重ループ Set 速いのは");
for (const n of [5, 10, 20, 50, 100, 300]) {
const ids = makeIds(n);
for (let i = 0; i < 10000; i++) { findDuplicatesSlow(ids); findDuplicatesFast(ids); }
let t0 = process.hrtime.bigint();
for (let i = 0; i < TRIES; i++) findDuplicatesSlow(ids);
const slow = Number(process.hrtime.bigint() - t0) / 1e6 / TRIES * 1000;
t0 = process.hrtime.bigint();
for (let i = 0; i < TRIES; i++) findDuplicatesFast(ids);
const fast = Number(process.hrtime.bigint() - t0) / 1e6 / TRIES * 1000;
console.log(
`${String(n).padStart(5)} ${slow.toFixed(2).padStart(8)} us ${fast.toFixed(2).padStart(8)} us ${slow < fast ? "二重ループ" : "Set"}`
);
}
us はマイクロ秒(100万分の1秒)です。 件数が小さいのでミリ秒では0になってしまい、測れません。
件数 二重ループ Set 速いのは
5 0.08 us 0.28 us 二重ループ
10 0.29 us 0.53 us 二重ループ
20 0.88 us 1.33 us 二重ループ
50 6.13 us 2.41 us Set
100 35.82 us 6.16 us Set
300 263.54 us 20.32 us Set
20件までは、O(n²) の二重ループのほうが速い。
5件のときは3.5倍速いです。 理由も当たり前です。new Set() を作る手間があるからです。 5件を比べる回数は10回しかないので、入れ物を作るコストのほうが大きい。
この記事で見つけた線は、ここです。
50件のあたりで逆転する。
そして、この「50件」という数字に意味はありません。 CPUでも、要素の中身でも、処理系のバージョンでも動きます。意味があるのは、逆転する点が存在するという事実のほうです。
だから、結論はパフォーマンスの回とまったく同じになります。
計算量は「どこを疑うか」を教えてくれる。「直すべきか」を決めるのは実測。
- 件数が数十件で固定なら、
O(n²)のままで構いません - 件数が外から来る(ユーザーが増える、データが溜まる)なら、
O(n²)は時限爆弾です
判断の基準は、速さではなく「n が誰に決められるか」です。
速さは、メモリと交換して買っている
時間だけを見てきました。もう1つの軸があります。
山場①の Map は、どこかにデータを持っています。 測ります。
function mb() { return process.memoryUsage().heapUsed / 1024 / 1024; }
const n = 1000000;
const before = mb();
const users = [];
for (let i = 1; i <= n; i++) users.push({ id: i, name: `user${i}` });
const afterArray = mb();
const byName = new Map();
for (const u of users) byName.set(u.name, u);
const afterMap = mb();
console.log(`配列だけ : ${(afterArray - before).toFixed(1)} MB`);
console.log(`索引(Map)を足す : +${(afterMap - afterArray).toFixed(1)} MB`);
console.log(`合計 : ${(afterMap - before).toFixed(1)} MB`);
配列だけ : 87.1 MB
索引(Map)を足す : +61.9 MB
合計 : 149.0 MB
探索を82万倍速くした代金が、62MBです。
メモリの増え方も、同じ記法で書きます。これを空間計算量と呼びます。
| やり方 | 時間 | メモリ |
|---|---|---|
| 線形探索 | O(n) | O(1)(何も足さない) |
Map の索引 | O(1) | O(n)(件数ぶん増える) |
多くの高速化は、この交換です。
そして、交換には限度があります。 自作データベースの回で書いた「索引がメモリに載らなくなったら終わり」が、そのままここに出ます。O(1) は、メモリに載っている間だけの O(1) です。
実務でどこに出るか
この記事の話が、実際に牙を剥く場所を3つ挙げます。
① APIの応答が、件数に比例して遅くなる
一覧を返すAPIは、ほぼ必ず O(n) です。 件数が10倍になれば10倍遅くなる。これは正常です。
問題は、O(n) を O(n²) にしてしまう書き方です。
// ⚠️ 各タスクに、担当者の名前を付けたい
const result = tasks.map(task => ({
...task,
userName: users.find(u => u.id === task.userId).name // ← ここが O(n)
}));
map が n 回まわり、その中の find が n 回まわります。 O(n²) です。タスク100件・ユーザー100件なら一瞬。両方1万件になると止まります。
直し方は、この記事でやったことそのままです。
const byId = new Map(users.map(u => [u.id, u])); // 1回だけ作る
const result = tasks.map(task => ({
...task,
userName: byId.get(task.userId)?.name // O(1)
}));
find / includes / indexOf が map や for の中にあったら、赤信号です。 これらは全部 O(n) です。
② N+1問題
パフォーマンスの回で潰したあれです。 一覧100件のために問い合わせが101回飛ぶやつ。
あれも、形は同じ O(n) です。 ただし、1回のコストがメモリアクセスではなくネットワーク往復です。
O(n) の中身 | 1回のコスト | 100万件だと |
|---|---|---|
| 配列を見る | 約5 ns | 約6 ms |
| データベースに問い合わせる | 約1 ms | 約17分 |
同じ
O(n)でも、定数が20万倍違います。 これが「O記法だけでは判断できない」の一番はっきりした例です。 計算量は、比べる対象の1回のコストが同じときにだけ、比較の道具になります。
③ 部分一致検索
全文検索の回で「部分一致は索引が効かない」と書きました。
理由が、いま言えるようになっています。
- 索引(並んでいる表)は、「先頭が一致するもの」なら二分探索できる →
O(log n) - 「途中に含まれるもの」は、先頭が手がかりにならないので、全部見るしかない →
O(n)
LIKE '%キーワード%' が遅いのは、書き方が下手だからではありません。 索引という道具が使える形になっていないからです。だから別の索引(転置索引)を持つエンジンを足すことになります。
やりすぎない
ここで止めます。理由を書きます。
アルゴリズムの本を最初から読み始めると、たいてい2週間で止まります。 ソートの種類を10個覚えて、木構造に入って、そこで力尽きる。そして、覚えたものを1つも使いません。
Webの仕事で実際に効くのは、この記事で測った範囲です。
| やること | 理由 |
|---|---|
O(n²) に気付ける | 桁で違うのはここだけ。気付けば Map か Set で直せる |
Map / Set / sort を正しく使える | 自分で書くより速く、バグらない |
| 測ってから判断する | O記法は当たりを付ける道具で、判定はしない |
逆に、後回しでいいものです。
- ソートアルゴリズムの実装(
sortがある) - 木構造やグラフの探索(必要になったときに読めば足ります)
- 正確な計算量の証明(この記事では1回もしていません)
この記事の後に本を読むなら、「必要になってから、その章だけ」です。 最初から順に読む本ではありません。
つまずいたところ
測っているつもりで、測れていませんでした。 3つ書きます。
① 1000件のほうが、1件あたり遅く出た
最初のベンチマークは、こう書いていました。
// ⚠️ 最初に書いたもの(間違い)
const t0 = process.hrtime.bigint();
for (let i = 0; i < TRIES; i++) findByName(users, target);
const ms = Number(process.hrtime.bigint() - t0) / 1e6 / TRIES;
結果がこうなりました。
1000 0.011 ms 11.41 ns ← 1件あたりが一番遅い
10000 0.020 ms 1.95 ns
1000件のほうが、1件あたり6倍遅い。 「小さいほうが遅い」は、どう考えてもおかしい。
原因は、JavaScriptの実行のされ方でした。 最初の数千回は「とりあえず動く形」で実行され、同じ関数が何度も呼ばれると、途中で速い形に作り直されます(JITコンパイル)。
1000件の測定は、その「作り直される前」を掴んでいました。
直したのは1行です。同じループを、測る前にもう1回まわしました。
for (let i = 0; i < TRIES; i++) findByName(users, target); // 準備運転(捨てる)
const t0 = process.hrtime.bigint();
for (let i = 0; i < TRIES; i++) findByName(users, target); // これを測る
この記事の全部のスクリプトに「準備運転」が入っているのは、これが理由です。
1回目の測定は捨てる。 言語を問わず、ベンチマークの基本でした。
② 10万件のところだけ、時間が28倍に飛んだ
バグを疑って30分探しました。バグではありませんでした。
配列がCPUのキャッシュに収まらなくなり、メモリ本体を読みに行く回数が増えただけです。 1件あたり 1.9ns が 5.3ns になったのは、そのぶんです。
そして、これが O記法 が定数を捨てる理由の実例になりました。 つまずいたおかげで、記事の中身が1つ増えています。
③ 4万件のベンチマークが、返ってこないと思った
4321.8 ms の行が出るまで、画面が止まります。 4秒です。
8万件を足したときは30秒近く止まりました。 止まったのではなく、O(n²) が仕事をしていただけです。
Ctrl + Cを押す前に、少し待ってください。 そして、この「待たされている感じ」こそがO(n²)の正体です。 本番で起きるのは、まさにこれです。
④ 「速いのは」の判定が、実行のたびに入れ替わった
bench-small.js の 20件と50件の境目は、走らせるたびに動きました。 30件が Set になったり二重ループになったりします。
マイクロ秒の測定は、それくらいぶれます。 ここで「正確な逆転点」を出そうとしても意味がありません。
測るときは、桁が変わるところを探す。 1割の差を追いかけない。
後片づけ
作ったのはスクリプトだけです。 消すのも1行です。
残しておいても数KBです。 この先「これ O(n²) かもしれない」と思ったときに、bench-dup2.js の形をそのまま流用できます。残すほうをおすすめします。
メモリの測定(bench-memory.js)を走らせた直後だけ、VMの空きが減っていることがあります。
プロセスは終わっているので、数字は戻っているはずです。 戻っていなければ、node が残っていないか見てください。
まとめ
- 「遅い」には2種類ある。 一定に遅いのは金で解決できる。データが増えると桁で遅くなるのは、作り直しになる
O記法は実行時間を言っていない。 言っているのは「件数を10倍にしたら何倍になるか」だけ- 線形探索は
O(n)。 100万件を全部見て5.75ms。1件あたりの時間は件数によらずほぼ一定(実測) Map.getはO(1)。 1000件でも100万件でも 7〜11ns。100万件では線形探索の82万倍速かった- ただし索引はタダではない。 100万件の
Mapを作るのに548ms。1回しか引かないなら、全部見たほうが速い - これがデータベースの索引と同じ話。
EXPLAINのrowsが 200000 から 1 になるのは、O(n)がO(1)に落ちたということ - 二重ループの重複検出は
O(n²)。 1000件で2.5ms、1万件で259ms(104倍)、4万件で4.3秒(1,729倍) Setに書き換えるとO(n)になる。 4万件で 4321.8ms → 5.92ms。730倍O(n²)を見つけたら、内側のループは「探している」だけのことが多い。 そこをMap/Setにする- 定数を無視するのは、定数が当てにならないから。 同じCPUの同じコードでも、キャッシュに載らなくなった瞬間に2.8倍になった(実測)
- 最悪の場合で言うのは、サービスが落ちるのが最悪のときだから。 平均が速いことは保証にならない
- 二分探索は
O(log n)。 100万件から探すのに20回、10億件でも30回。半分にしていくと何回で終わるか、という意味 - 二分探索には並んでいることが要る。 100万件の
sortに369ms。1回だけ探すなら、並べ替えるだけ損 sortはO(n log n)。自分で書かない。 ただしループの中で呼ばない。比較関数を省くと文字列として並ぶ- 計算量が良い=速い、ではない。 20件までは
O(n²)のほうが速かった(実測)。逆転点は環境で動く - 判断の基準は速さではなく「
nを誰が決めるか」。 外から来るならO(n²)は時限爆弾、固定なら放っておいてよい - 速さはメモリで買っている。 82万倍の代金が62MB。索引がメモリに載っている間だけの
O(1) - 同じ
O(n)でも、1回が5nsか1msかで20万倍違う。 N+1が致命的なのはそれ。O記法だけで比べない - 最後は測る。 これはパフォーマンスの回の結論とまったく同じ
- アルゴリズムの本を最初から読まない。 効くのは「
O(n²)に気付ける」「Map・Set・sortを使える」の2つ
参考リンク
- roadmap.sh — Computer Science
- MDN — Map
- MDN — Set
- MDN — Array.prototype.sort
- MDN — Array.prototype.includes
- Node.js — process.hrtime.bigint
- V8 — Getting things sorted in V8
- Big-O Cheat Sheet
次に読む
この記事は 【番外編】roadmap.sh の外 の 34 / 35 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 自分のOSがQEMUで起動する — OS自作の到達作品 |
| → 次の記事 | 配列は先頭への挿入が遅い — データ構造を自作する |
ここは番外編です。 本筋から外れているので、飛ばして構いません。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
【番外編】計算量。roadmap.sh の Computer Science 側の話で、本筋の範囲外。

コメント