並べ替えたら10が2の前に来ました。ソートアルゴリズム6種を実装し、辞書順と数値順の違いまで確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 本線の計算量とO記法の回で「1万件で100倍になる」ところまでやった人が、「その100倍を、実際に自分の手で作って測る」ための記事です。飛ばしても本線は進みます。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。
node -vで v20 以上が出れば大丈夫です。 作業場所は~/cslab/sort/です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私のVMの数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、件数を2倍にしたときに何倍になるかと、同じ件数でも並び方で何倍変わるかです。
対象レベル: 中級〜上級 / 区分: 発展
3件の配列で30分潰した話
自分の書いたコードを疑って30分溶かした話から始めます。
在庫の数を集計する小さなスクリプトを書いていました。数量の配列を小さい順に並べ替えて、真ん中の値を取りたかっただけです。
const nums = [1, 2, 10];
console.log(nums.sort());
返ってきたのはこれです。
[ 1, 10, 2 ]
私は、自分がどこかで文字列を混ぜたのだと思いました。 上流のAPIが数値を文字列で返しているのだろう、と。それで typeof を仕込み、Number() を挟み、JSON.parse の前後にログを足し、30分かけて「全部ちゃんと数値である」ことを確認しました。
バグはありませんでした。
JavaScript の
sort()は、比較関数を渡さないと、要素を文字列に変換して辞書順で並べます。 これは不具合ではなく仕様です。だから1と2と10は、"1""2""10"として比べられ、"10"は"2"より前に来ます。 1文字目が1と2なので、"10"のほうが小さいのです。
このとき私は、もっと恥ずかしいことに気づきました。
私はそれまで「ソートアルゴリズム」を、面接で聞かれるやつとして理解していました。バブルソートの名前は知っている。「O(n²) だから遅い」も言える。でも書いたことは一度もない。そして、毎日使っている sort が中で何をしているのかも、まったく知りませんでした。
[1, 10, 2] を見て30分潰したのは、「sort が何をする関数なのか」を一度も考えたことがなかったからです。名前だけ知っている状態は、知らない状態より危ないことがあります。
だからこの記事では、逆から行きます。
sort の仕様を暗記するのではなく、並べ替えという仕事を自分で6通り書いて、同じデータで測ります。 そのうえで最後に「では本物の sort は何をしているのか」を見ます。
先に結論を言っておきます。この記事を読み終わったあと、皆さんが自分でソートを書くことは、たぶん一生ありません。 それでいいのです。この記事の目的は書けるようになることではなく、次の3つに即答できるようになることです。
- なぜ、すでに並んでいるデータは速く並べ替えられるのか
- なぜ、同点の人の順番が保たれる(ときと保たれないとき)があるのか
- なぜ、「うちのデータでは速かった」が信用できないのか
この3つは、ライブラリを使うときにこそ効いてきます。
この記事でわかること
sort()に比較関数を渡さないと、要素は文字列にされて辞書順に並ぶこと。[1,2,10].sort()が[1,10,2]になるのは仕様で、sort((a,b)=>a-b)を書くのが正しい直し方- 日本語やファイル名は
a - bでも<でも正しく並ばないこと。localeCompareが必要で、file10.txtをfile9.txtの後ろに置くには{ numeric: true }が要る。しかもlocaleCompareを比較関数の中で毎回呼ぶと 9360ミリ秒、Intl.Collatorを1個作って使い回すと 353ミリ秒(26倍) - 「同じ O(n²)」の3つは、実測ではまったく別物であること。n=2000 のとき比較回数はどれも約200万回で並ぶのに、書き込み回数はバブル 199万・挿入 100万・選択 3992回。選択ソートは「並び方が何であっても回数が変わらない」唯一の1つ
- 挿入ソートは、すでに並んでいるデータなら比較 1999回で終わること(n=2000)。O(n²) のはずが O(n) になる。 これが後で出てくる本物の
sortの速さの正体です - クイックソートは、すでに並んでいるデータで先頭を軸にすると O(n²) になり、しかも落ちること。n=6000 では通り、n=8000 で
Maximum call stack size exceeded。「遅くなる」で済まず、例外で止まります - 軸の選び方を直したら、別のデータで今度は落ちたこと。中央値を軸にしても、同じ値が大量にあるデータでは再帰の深さが 5446 段になって溢れます。 直すには分け方そのものを3分割に変える必要がありました
- 「安定なソート」は、同点のときに元の順番が保たれるという意味で、選択ソートとクイックソートとヒープソートは保たれないこと。3件の配列で実際に入れ替わるところを出力で見ます。JavaScript の
sortは ES2019 から仕様で安定 - V8 の
sortは TimSort(マージソートと挿入ソートの組み合わせ)で、すでに並んでいる区間を見つけて再利用すること。同じ n=200000 で、ランダムなら 53ミリ秒、整列済みなら 3.4ミリ秒。同じ関数・同じ件数で15倍違う - 自作が V8 に勝つ場面もあること(n=200000 のランダムな整数で、自作クイック 19.5ミリ秒 対 V8 55.3ミリ秒)。理由は V8 が比較のたびに私の渡したJS関数を呼んでいるから。 それでも自作を採用してはいけない理由を最後に書きます
この記事でやること
~/cslab/sort/を作り、まず罠を踏む。[1,2,10].sort()を実際に出し、比較関数で直し、日本語とファイル名では別の道具が必要なことを実演する- 測る土台を作る。 4種類のデータ(ランダム / 整列済み / 逆順 / 同値多数)を作る関数と、比較回数・交換回数・書き込み回数を数える仕組みを用意する
- O(n²) の3つを書く(バブル・選択・挿入)。回数を数えて、「同じ O(n²)」の中身がまったく違うことを表にする
- O(n log n) の2つを書く(マージ・クイック)。追加メモリの差を実測する
- 山場。 すでに並んでいるデータで自作クイックソートを落とし、軸の選び方を4通り実装して、再帰の深さと比較回数で直ったことを確かめる。 そして直したはずが別のデータで落ちるところまで行く
- 安定性を出力で見る。 同点の8人を点数で並べ替えて、6つのうちどれで順番が壊れるかを目で確認する
- ヒープソートを足して6つにし、V8 の
sortと同じデータで測り比べる。 TimSort が何を見ているかを、並びの壊れ具合を変えた7種類のデータで確かめる - 1枚の総括表にまとめて、
~/cslab/を消す
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| ソート(sort) | 決めた順番に並べ替えること。「並べ替え」と書いたほうが分かりやすいので、この記事では両方使います |
| 比較関数(comparator) | 2つを渡すと「どちらが先か」を返す関数。負の数なら前者が先、正の数なら後者が先、0 なら同じ。(a, b) => a - b がこれ |
| 安定(stable) | 同じ順位のものが、元の順番を保つという性質。「壊れない」という意味の安定ではありません |
| その場で並べ替える(in-place) | 元の配列を直接書き換え、別の配列を作らないやり方。追加メモリがほぼ要らない |
| 軸(pivot) | クイックソートで「これより小さい組」「これより大きい組」に分けるための基準にする1個。この選び方だけで速度が桁で変わります |
| 再帰の深さ | 関数が自分を呼び、その中でまた自分を呼び…と何段積み上がったか。前回のコールスタックの回で数えたあれです |
| run | 配列の中で、すでに昇順(または降順)に並んでいる連続した区間。本物の sort はこれを探しています |
| TimSort | マージソートと挿入ソートを組み合わせた並べ替え方。Python と Java と V8(Chrome・Node.js)が使っています |
| O(n²) / O(n log n) | 件数が増えたときに手間がどう増えるか。n が2倍なら前者は4倍、後者は2倍と少し。 本線の計算量の回と、深掘りのO記法の回でやりました |
performance.now() | ミリ秒を小数で返す時計。Date.now() より細かく測れる |
① まず罠を踏む
作業場所を作ります。
v22.14.0
v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。
この記事では npm install を1回もしません。ライブラリは使いません。 使ったら、正体を確かめるという目的が消えます。
package.json を1枚だけ置きます。import を使うためです。
{ "type": "module" }
では、私が30分溶かしたものを再現します。
const nums = [1, 2, 10];
console.log('sort() :', nums.slice().sort());
console.log('sort((a,b)=>a-b):', nums.slice().sort((a, b) => a - b));
const more = [3, 25, 100, 9, 80, 1];
console.log('---');
console.log('既定 :', more.slice().sort());
console.log('比較関数あり :', more.slice().sort((a, b) => a - b));
console.log('---');
console.log('文字列にすると :', more.map(String).sort());
const names = ['さくら', 'あさひ', 'イチロー', 'ずんだ', 'Apple', 'apple', 'Banana'];
console.log('---');
console.log('既定 :', names.slice().sort());
console.log('localeCompare :', names.slice().sort((a, b) => a.localeCompare(b, 'ja')));
console.log('---');
console.log('undefined混在 :', [3, undefined, 1, 2].sort((a, b) => a - b));
.slice() を挟んでいるのは、sort が元の配列を書き換えてしまうからです。これも後で確かめます。
sort() : [ 1, 10, 2 ]
sort((a,b)=>a-b): [ 1, 2, 10 ]
---
既定 : [ 1, 100, 25, 3, 80, 9 ]
比較関数あり : [ 1, 3, 9, 25, 80, 100 ]
---
文字列にすると : [ '1', '100', '25', '3', '80', '9' ]
---
既定 : [
'Apple', 'Banana',
'apple', 'あさひ',
'さくら', 'ずんだ',
'イチロー'
]
localeCompare : [
'apple', 'Apple',
'Banana', 'あさひ',
'イチロー', 'さくら',
'ずんだ'
]
---
undefined混在 : [ 1, 2, 3, undefined ]
1行ずつ読みます。
[ 1, 100, 25, 3, 80, 9 ] と [ '1', '100', '25', '3', '80', '9' ] を見比べてください。引用符が付いているかどうかしか違いません。
既定の
sort()は、内部で要素を文字列にしてから比べています。 だから数値の配列を文字列の配列にしてから並べた結果と、完全に一致します。sort()は「並べ替えを失敗した」のではなく、指示された通りに文字列として並べたのです。
これは本線のJavaScriptの基本の回でやった「"1" と 1 は等しい」と同じ話です。言語が勝手に型を変える場面が、また1つあったということです。
日本語のほうも見てください。
既定では あさひ さくら ずんだ の後ろに イチロー が来ています。「カタカナが全部ひらがなの後ろ」になっています。
これは文字コードの順番です。ひらがなの あ は U+3042、カタカナの ア は U+30A2 なので、カタカナのほうが数字として大きいのです。ここは深掘りの文字コードの回でやった話がそのまま出てきています。
localeCompare(b, 'ja') を渡すと あさひ イチロー さくら ずんだ になります。ひらがなとカタカナを同じ音として扱った五十音順です。
日本語を「あいうえお順」に並べたいなら、
<やa - bでは絶対に無理です。localeCompareを使ってください。 文字コードの数字の大小は、人間の期待する順番とは別のものです。
最後の undefined混在 の行も覚えておいてください。undefined は比較関数を無視して必ず末尾に行きます。 これも仕様です。私は一度これで「なぜか最後の1件だけ並ばない」と悩みました。
ファイル名を人間の期待通りに並べる
もう1つ、実務で必ず出るものをやります。
const files = ['file10.txt', 'file9.txt', 'file1.txt', 'file100.txt', 'file2.txt'];
console.log('既定のsort ', files.slice().sort().join(' '));
console.log('localeCompare', files.slice().sort((a, b) => a.localeCompare(b)).join(' '));
console.log('numeric: true', files.slice().sort((a, b) => a.localeCompare(b, undefined, { numeric: true })).join(' '));
console.log('');
const kana = ['さくら', 'あさひ', 'ずんだ', 'イチロー', 'ばなな', 'パンダ'];
console.log('既定 ', kana.slice().sort().join(' '));
console.log('ja で比較 ', kana.slice().sort((a, b) => a.localeCompare(b, 'ja')).join(' '));
console.log('');
// Intl.Collator を1回作って使い回すほうが速い
const coll = new Intl.Collator('ja', { numeric: true });
const many = [];
for (let i = 0; i < 50000; i++) many.push('file' + ((i * 7919) % 50000) + '.txt');
let t = performance.now();
many.slice().sort((a, b) => a.localeCompare(b, 'ja', { numeric: true }));
const slow = performance.now() - t;
t = performance.now();
many.slice().sort(coll.compare);
const fast = performance.now() - t;
console.log('localeCompare を毎回 ', slow.toFixed(1), 'ms');
console.log('Intl.Collator を使い回す ', fast.toFixed(1), 'ms');
既定のsort file1.txt file10.txt file100.txt file2.txt file9.txt
localeCompare file1.txt file10.txt file100.txt file2.txt file9.txt
numeric: true file1.txt file2.txt file9.txt file10.txt file100.txt
既定 あさひ さくら ずんだ ばなな イチロー パンダ
ja で比較 あさひ イチロー さくら ずんだ ばなな パンダ
localeCompare を毎回 9360.4 ms
Intl.Collator を使い回す 353.9 ms
3つ、重要なことが出ています。
1つ目。localeCompare を渡しただけでは file10.txt は file2.txt の前のままです。{ numeric: true } が必要でした。これは「文字列の中の数字の並びを、数として比べる」という指定です。
2つ目。私は最初、これを「localeCompare を使えば直る」と覚えていました。違いました。 直すのは numeric: true のほうで、localeCompare はロケール(言語ごとの規則)を持ち込むための入口です。
3つ目。そして遅い。
localeCompareを比較関数の中で毎回呼ぶと、5万件で 9360ミリ秒(9.4秒)かかりました。Intl.Collatorを1個作ってcoll.compareを渡すと 353ミリ秒。26倍の差です。 理由は、localeCompare(b, 'ja', {numeric:true})を呼ぶたびに「日本語で、数字は数として」という比較器を作り直しているからです。5万件の並べ替えなら比較は約80万回起きるので、80万回作り直していたことになります。
これは本線のパフォーマンス改善の回で言った「速くする前に必ず測る」の、いちばん分かりやすい形です。26倍の差が、書き方だけで出ています。
[スクリーンショット: 01_文字列として並ぶ.png] — node trap.js の出力全体を撮ります。[ 1, 100, 25, 3, 80, 9 ] と [ '1', '100', '25', '3', '80', '9' ] の2行が同じ画面に写っていることが大事です。この2行が同じ順番であることが、この記事の出発点です。
元の配列は壊れる
罠をもう1つだけ潰しておきます。
const original = [3, 1, 2];
const result = original.sort((a, b) => a - b);
console.log('original :', original);
console.log('result :', result);
console.log('同じもの? :', original === result);
const orig2 = [3, 1, 2];
const copy = orig2.toSorted((a, b) => a - b);
console.log('---');
console.log('orig2 :', orig2);
console.log('toSorted :', copy);
// 比較関数が矛盾していると結果が壊れる
const bad = [5, 3, 9, 1, 7, 2, 8, 4, 6, 0];
console.log('---');
console.log('でたらめな比較関数:', bad.slice().sort(() => Math.random() - 0.5));
console.log('true を返すだけ :', bad.slice().sort(() => true));
original : [ 1, 2, 3 ]
result : [ 1, 2, 3 ]
同じもの? : true
---
orig2 : [ 3, 1, 2 ]
toSorted : [ 1, 2, 3 ]
---
でたらめな比較関数: [
2, 4, 6, 0, 8,
1, 9, 3, 7, 5
]
true を返すだけ : [
5, 3, 9, 1, 7,
2, 8, 4, 6, 0
]
3つ、確認できました。
sortは元の配列を書き換えます。 しかも返ってくるのは同じ配列です(original === resultがtrue)。「並べ替えた新しい配列をもらった」と思って元を使い続けると、静かに壊れます- 元を残したいなら
toSortedを使います(Node.js 20 以降)。元は[3, 1, 2]のままです - 比較関数がでたらめだと、結果もでたらめになります。
() => trueは「常に後者が先」と言い続けるので、1つも動きません。Math.random() - 0.5でシャッフルするのは間違いです。 偏りが出るうえ、実装が変わると結果も変わります
② 測る土台を作る
ここからが本題です。先に「測る道具」を作ります。 アルゴリズムより先です。
理由があります。私は最初、アルゴリズムを6つ書いてから測ろうとして失敗しました。 データが毎回違う乱数だったので、「バブルが遅い」のか「今回のデータが悪かった」のか区別できなかったのです。
必要なものは2つです。
- 毎回まったく同じデータが出てくること(そうでないと比べられない)
- 時間だけでなく、比較の回数と書き込みの回数を数えられること
2番目が特に大事です。
時間はマシンで変わりますが、比較回数は変わりません。 私のVMで測った 858ミリ秒は皆さんの環境では別の数字になります。でも「n=2000 のバブルソートは比較を 1998010 回した」は、どのマシンでも同じです。アルゴリズムの性質を見たいなら、時間より回数を見るべきです。
// 毎回同じ乱数が出るようにする(測定を比べるため)
export function makeRandom(n, seed = 12345) {
let s = seed;
const a = [];
for (let i = 0; i < n; i++) {
s = (s * 1103515245 + 12345) & 0x7fffffff;
a.push(s % (n * 10));
}
return a;
}
export function makeSorted(n) {
const a = [];
for (let i = 0; i < n; i++) a.push(i);
return a;
}
export function makeReversed(n) {
const a = [];
for (let i = n - 1; i >= 0; i--) a.push(i);
return a;
}
export function makeFewUnique(n, seed = 999) {
let s = seed;
const a = [];
for (let i = 0; i < n; i++) {
s = (s * 1103515245 + 12345) & 0x7fffffff;
a.push(s % 5);
}
return a;
}
export function makeCounter() {
const c = { compares: 0, swaps: 0, writes: 0 };
return {
counts: c,
lt(a, b) { c.compares++; return a < b; },
gt(a, b) { c.compares++; return a > b; },
le(a, b) { c.compares++; return a <= b; },
swap(arr, i, j) { c.swaps++; c.writes += 2; const t = arr[i]; arr[i] = arr[j]; arr[j] = t; },
write(arr, i, v) { c.writes++; arr[i] = v; },
reset() { c.compares = 0; c.swaps = 0; c.writes = 0; },
};
}
makeRandom が Math.random() を使っていないのが要点です。
s = (s * 1103515245 + 12345) & 0x7fffffff という1行で、前の数から次の数を決めています。 最初の数(seed)が同じなら、出てくる列も毎回同じです。これを線形合同法と言いますが、名前は覚えなくていいです。「種を固定できる乱数」が要る、という理由だけ覚えてください。
makeCounter のほうが、この記事の心臓です。
比較を a < b と直接書かず、c.lt(a, b) と書くようにします。そうすると、比較のたびにカウンタが1つ増えます。 交換も書き込みも同じです。
4種類のデータを確認します。
import { makeRandom, makeSorted, makeReversed, makeFewUnique } from './data.js';
for (const [name, f] of [['ランダム', makeRandom], ['整列済み', makeSorted], ['逆順', makeReversed], ['同値多数', makeFewUnique]]) {
const a = f(10);
console.log(name.padEnd(9, ' '), JSON.stringify(a));
}
ランダム [6,8,36,36,16,8,76,68,8,28]
整列済み [0,1,2,3,4,5,6,7,8,9]
逆順 [9,8,7,6,5,4,3,2,1,0]
同値多数 [1,3,3,1,2,1,2,0,4,0]
この4種類を選んだ理由を言います。
| データ | なぜ必要か |
|---|---|
| ランダム | いちばん普通の状態。「平均的な速さ」がここに出る |
| 整列済み | 実務でいちばん多い形。DBから ORDER BY 付きで取った結果、日付順に並んだログ、追記されただけのファイル |
| 逆順 | 最悪ケースが出やすい。「新しい順」を「古い順」に直す場面 |
| 同値多数 | これも実務で多い。ステータスが5種類しかない列、都道府県、評価の星の数 |
「ランダムなデータだけで測って速いと言う」のがいちばん危ないということが、この記事の後半で3回起きます。
測るときはカウンタを外す
ここで1つ、気づいたことがあります。
import { makeCounter, makeRandom } from './data.js';
import { mergeSort } from './sorts.js';
const noop = { lt:(a,b)=>a<b, gt:(a,b)=>a>b, le:(a,b)=>a<=b,
swap:(arr,i,j)=>{const t=arr[i];arr[i]=arr[j];arr[j]=t;}, write:(arr,i,v)=>{arr[i]=v;} };
const c = makeCounter();
const N = 200000;
const src = makeRandom(N);
function median(xs){const s=xs.slice().sort((a,b)=>a-b);return s[s.length>>1];}
function bench(cc){const r=[];for(let i=0;i<5;i++){const a=src.slice();cc.reset&&cc.reset();const t=performance.now();mergeSort(a,cc);r.push(performance.now()-t);}return median(r);}
console.log('n =', N);
console.log('カウンタなし', bench(noop).toFixed(1), 'ms');
console.log('カウンタあり', bench(c).toFixed(1), 'ms');
(sorts.js は次の節で作ります。作ってから戻ってきてください。)
n = 200000
カウンタなし 35.0 ms
カウンタあり 82.1 ms
数えているだけで 2.3倍遅くなりました。 だからこの記事では、回数を数えるときと時間を測るときで、別のものを渡します。 カウンタの代わりに、何も数えない
noopを渡します。 「測るために入れた道具が測定結果を変える」のは、性能を測るときにいつでも起きる問題です。
③ O(n²) の3つを書く
3つ書きます。どれも20行以内です。
// バブルソート:隣を比べて、大きいほうを後ろへ送る
export function bubbleSort(a, c) {
const n = a.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (c.gt(a[j], a[j + 1])) { c.swap(a, j, j + 1); swapped = true; }
}
if (!swapped) break; // 1周して1回も交換しなければ、もう並んでいる
}
return a;
}
// 選択ソート:残りの中から最小を1つ選び、先頭に置く
export function selectionSort(a, c) {
const n = a.length;
for (let i = 0; i < n - 1; i++) {
let min = i;
for (let j = i + 1; j < n; j++) {
if (c.lt(a[j], a[min])) min = j;
}
if (min !== i) c.swap(a, i, min);
}
return a;
}
// 挿入ソート:手札を並べるように、左の並びへ差し込む
export function insertionSort(a, c) {
const n = a.length;
for (let i = 1; i < n; i++) {
const v = a[i];
let j = i - 1;
while (j >= 0 && c.gt(a[j], v)) { c.write(a, j + 1, a[j]); j--; }
if (j + 1 !== i) c.write(a, j + 1, v);
}
return a;
}
言葉で1回ずつ言い直します。
バブルソートは、隣り合う2つを見て、順番が逆なら入れ替える、これを配列の端から端まで繰り返します。1周すると、いちばん大きい値が必ず末尾に着きます(だから次の周は1つ短くできます)。名前は「大きい泡が浮かんでいくように見える」からです。
swapped のフラグを入れているのが大事な工夫です。1周まわって1回も交換しなかったなら、もう全部並んでいるので途中で抜けられます。
選択ソートは、残っている中でいちばん小さいものを探して、先頭に持ってくる。それを1つずつ確定させていきます。カードを配られて、机の上で「いちばん小さいのはこれ、次はこれ」とやるのに近いです。
挿入ソートは、手札を並べるのと同じです。左側はもう並んでいるとみなして、次の1枚を左に向かって差し込む場所を探します。差し込む場所が見つかるまで、途中の札を1つずつ右にずらします。
正しく並ぶか確認します。
import { makeCounter, makeRandom } from './data.js';
import { bubbleSort, selectionSort, insertionSort, mergeSort, quickSort, heapSort } from './sorts.js';
const c = makeCounter();
const src = makeRandom(200, 7);
const expected = src.slice().sort((x, y) => x - y);
const algos = [
['バブル', bubbleSort], ['選択', selectionSort], ['挿入', insertionSort],
['マージ', mergeSort], ['クイック', quickSort], ['ヒープ', heapSort],
];
for (const [name, fn] of algos) {
c.reset();
const a = src.slice();
fn(a, c);
const ok = JSON.stringify(a) === JSON.stringify(expected);
console.log(name.padEnd(5, ' '), ok ? 'OK ' : 'NG ', '比較', String(c.counts.compares).padStart(6), ' 交換', String(c.counts.swaps).padStart(6));
}
答え合わせの相手を sort((x,y)=>x-y) にしているのが要点です。自分の実装が正しいかどうかは、すでに正しいと分かっているものと比べるしかありません。
(6つ全部を書いてから走らせます。いま走らせると mergeSort が無いと言われます。)
6つ書き終わったあとの出力がこれです。
バブル OK 比較 19647 交換 9952
選択 OK 比較 19900 交換 191
挿入 OK 比較 10149 交換 0
マージ OK 比較 1295 交換 0
クイック OK 比較 1404 交換 1013
ヒープ OK 比較 2452 交換 1360
n=200 で、比較回数が 19647 と 1295 です。15倍違います。 これが O(n²) と O(n log n) の差です。
4種類のデータで回数を数える
ここが、この記事でいちばん見てほしい表です。
import { makeCounter, makeRandom, makeSorted, makeReversed, makeFewUnique } from './data.js';
import { bubbleSort, selectionSort, insertionSort } from './sorts.js';
const N = 2000;
const sets = [['ランダム', makeRandom(N)], ['整列済み', makeSorted(N)], ['逆順', makeReversed(N)], ['同値多数', makeFewUnique(N)]];
const algos = [['バブル', bubbleSort], ['選択', selectionSort], ['挿入', insertionSort]];
const c = makeCounter();
console.log(`n = ${N}(n² = ${N * N}、n²/2 = ${N * N / 2})`);
console.log('');
console.log('アルゴリズム データ 比較回数 書き込み回数');
for (const [an, fn] of algos) {
for (const [dn, data] of sets) {
c.reset();
fn(data.slice(), c);
console.log(an.padEnd(6, ' '), dn.padEnd(5, ' '), String(c.counts.compares).padStart(10), String(c.counts.writes).padStart(12));
}
console.log('');
}
n = 2000(n² = 4000000、n²/2 = 2000000)
アルゴリズム データ 比較回数 書き込み回数
バブル ランダム 1998010 1997750
バブル 整列済み 1999 0
バブル 逆順 1999000 3998000
バブル 同値多数 1917997 1607068
選択 ランダム 1999000 3992
選択 整列済み 1999000 0
選択 逆順 1999000 2000
選択 同値多数 1999000 3232
挿入 ランダム 1000869 1000869
挿入 整列済み 1999 0
挿入 逆順 1999000 2000999
挿入 同値多数 805532 805150
この表を1行ずつ読むと、教科書に書いてあることが全部出てきます。
まず「n²/2 = 2000000」という参考値と見比べてください。
ランダムなデータでの比較回数は、バブル 1998010、選択 1999000、挿入 1000869 です。バブルと選択が ほぼ 200万 = n²/2、挿入が ほぼ 100万 = n²/4 です。
O(n²) というのは、こういう意味です。 n=2000 のとき、比較の回数が n の2乗に比例した大きさになります。n²/2 なのか n²/4 なのかは O記法では区別しませんが、実測では2倍の差として出ます。
次に、書き込み回数の列を見てください。ここが本題です。
| アルゴリズム | ランダムでの比較 | ランダムでの書き込み |
|---|---|---|
| バブル | 1998010 | 1997750 |
| 選択 | 1999000 | 3992 |
| 挿入 | 1000869 | 1000869 |
同じ「O(n²) の遅いソート」なのに、書き込み回数が 199万 と 3992 で、500倍違います。 バブルソートは比べた回数とほぼ同じ回数、配列に書き込んでいます。 選択ソートは1周につき最大1回しか交換しないので、n回で終わります。
これは実務で意味を持つ差です。書き込みが高くつく相手(SSD、ネットワーク越しのデータ、フラッシュメモリ)では、比較回数が同じでも選択ソートのほうがましです。O記法だけ見ていると、この差は完全に見えません。
そして、いちばん重要な行がこれです。
挿入 整列済み 1999 0
挿入ソートは、すでに並んでいるデータなら、比較 1999回・書き込み 0回で終わります。 n=2000 で 1999回。つまり n-1 回です。O(n) です。 理由は実装を見れば分かります。
while (j >= 0 && c.gt(a[j], v))の条件が、1回目でいつも偽になるからです。左隣が自分より大きいことが一度もないので、ずらす処理に入りません。
この1行が、記事の後半で出てくる本物の sort の速さの正体です。 覚えておいてください。
もう1つ、選択ソートの列に注目してください。
選択 ランダム 1999000
選択 整列済み 1999000
選択 逆順 1999000
選択 同値多数 1999000
4種類のデータで、比較回数が完全に同じ 1999000 です。 選択ソートは「残りの中の最小を探す」ので、すでに並んでいても最後まで全部見ます。 手抜きができません。 最良でも最悪でも同じという性質は、予測しやすいという意味では長所です。でも、すでに並んでいるデータで一切速くならないという意味では短所です。
逆順のバブルソートの書き込み 3998000 も見てください。 ランダムの2倍です。逆順はすべての隣り合うペアが逆なので、毎回交換が起きます。 交換1回で2箇所書き込むので、比較 199万 × 2 = 398万 になっています。数字が理屈と一致しました。
バブルソートの「整列済み 1999回・書き込み0回」は、さきほど入れた swapped フラグの効果です。フラグを入れないバブルソートなら、整列済みでも 1999000 回比べます。 「バブルソートは何をしても O(n²)」と覚えていると、これを見落とします。
件数を2倍にして、増え方を見る
O記法が本当に増え方の話であることを、数字で確かめます。
import { makeCounter, makeRandom } from './data.js';
import { insertionSort, mergeSort, quickSort3, heapSort } from './sorts.js';
const c = makeCounter();
console.log('| n | 挿入(比較) | マージ(比較) | クイック(比較) | ヒープ(比較) | n²/4 | n·log2n |');
console.log('|---|---|---|---|---|---|---|');
for (const n of [1000, 2000, 4000, 8000]) {
const src = makeRandom(n, 77);
const out = [];
for (const fn of [insertionSort, mergeSort, (a, cc) => quickSort3(a, cc, null, 'median3'), heapSort]) {
c.reset(); fn(src.slice(), c); out.push(c.counts.compares);
}
console.log(`| ${n} | ${out.join(' | ')} | ${n * n / 4} | ${Math.round(n * Math.log2(n))} |`);
}
| n | 挿入(比較) | マージ(比較) | クイック(比較) | ヒープ(比較) | n²/4 | n·log2n |
|---|---|---|---|---|---|---|
| 1000 | 248731 | 8723 | 13056 | 16868 | 250000 | 9966 |
| 2000 | 996311 | 19406 | 29044 | 37725 | 1000000 | 21932 |
| 4000 | 3945136 | 42863 | 57138 | 83530 | 4000000 | 47863 |
| 8000 | 15804201 | 93617 | 129367 | 183041 | 16000000 | 103726 |
挿入ソートの列を上から順に読んでください。
248731 → 996311 → 3945136 → 15804201。n が2倍になるたび、ちょうど4倍です。そして右端の n²/4 の列とほぼ一致しています。
マージソートの列は 8723 → 19406 → 42863 → 93617。2.2倍ずつです。そして n·log2n の列(9966 / 21932 / 47863 / 103726)と、ほぼ同じ大きさです。
これがO記法の意味です。 「挿入ソートは O(n²)、マージソートは O(n log n)」は、この列の増え方の違いを言っています。 n=8000 では 15804201 対 93617 で、169倍の差になりました。n=1000 では 28倍でした。件数が増えるほど差が開きます。 これが「1万件で100倍になる」の中身です。
④ O(n log n) の2つを書く
sorts.js に足していきます。
// マージソート:半分に分けて、それぞれ並べて、統合する
export function mergeSort(a, c) {
const buf = new Array(a.length);
function sort(lo, hi) {
if (hi - lo < 2) return;
const mid = (lo + hi) >> 1;
sort(lo, mid); sort(mid, hi);
let i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (c.le(a[i], a[j])) buf[k++] = a[i++]; // <= が安定性のかなめ
else buf[k++] = a[j++];
}
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
for (let t = lo; t < hi; t++) c.write(a, t, buf[t]);
}
sort(0, a.length);
return a;
}
// クイックソート:軸を1つ決め、小さい組と大きい組に分ける
// pivotMode: 'first' | 'middle' | 'random' | 'median3'
export function quickSort(a, c, pivotMode = 'median3', stat = null) {
function choose(lo, hi) {
if (pivotMode === 'first') return lo;
if (pivotMode === 'middle') return (lo + hi) >> 1;
if (pivotMode === 'random') return lo + Math.floor(Math.random() * (hi - lo + 1));
// median3:先頭・中央・末尾の3つの中央値を軸にする
const mid = (lo + hi) >> 1;
const x = a[lo], y = a[mid], z = a[hi];
if ((x <= y && y <= z) || (z <= y && y <= x)) return mid;
if ((y <= x && x <= z) || (z <= x && x <= y)) return lo;
return hi;
}
function sort(lo, hi, depth) {
if (stat && depth > stat.maxDepth) stat.maxDepth = depth;
if (lo >= hi) return;
const p = choose(lo, hi);
c.swap(a, p, hi);
const pivot = a[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (c.lt(a[j], pivot)) { if (i !== j) c.swap(a, i, j); i++; }
}
c.swap(a, i, hi);
sort(lo, i - 1, depth + 1);
sort(i + 1, hi, depth + 1);
}
sort(0, a.length - 1, 1);
return a;
}
マージソートは、半分に割って、それぞれを並べて、並んだ2つを統合する。統合は、2つの先頭を見比べて小さいほうを取っていくだけです。
割るところは何もしていないのが最初は分かりにくいところです。sort(lo, mid); sort(mid, hi); の2行が「半分に割る」で、実際の仕事は統合のほうにあります。
クイックソートは逆です。先に軸を決めて、軸より小さい組と大きい組に分けてしまいます。 分けた時点で軸の位置は確定しているので、あとは左右をそれぞれ並べるだけです。分けるところが仕事で、統合には何もありません。
| 割る | 統合する | |
|---|---|---|
| マージ | 何もしない(真ん中で切るだけ) | ここが仕事(2つを見比べて取る) |
| クイック | ここが仕事(軸で振り分ける) | 何もしない(もう並んでいる) |
マージソートの c.le(<=)に付けたコメントを覚えておいてください。 ここを < にするか <= にするかで、⑥で見る「安定性」が変わります。1文字です。
追加メモリを実測する
マージソートの const buf = new Array(a.length) の行が、この2つのいちばん大きな違いです。
const N = 1000000;
const mb = (x) => (x / 1024 / 1024).toFixed(1) + 'MB';
global.gc();
const base = process.memoryUsage().heapUsed;
console.log('何も持っていないとき ', mb(base));
const a = new Array(N);
for (let i = 0; i < N; i++) a[i] = i;
global.gc();
const one = process.memoryUsage().heapUsed;
console.log('配列を1本持ったとき ', mb(one), ` 増えた分 ${mb(one - base)}`);
const buf = new Array(N);
for (let i = 0; i < N; i++) buf[i] = 0;
global.gc();
const two = process.memoryUsage().heapUsed;
console.log('作業用にもう1本 ', mb(two), ` 増えた分 ${mb(two - one)}`);
console.log(a.length, buf.length);
global.gc() を呼ぶには、Node.js に --expose-gc を付けて起動する必要があります。
何も持っていないとき 3.7MB
配列を1本持ったとき 11.6MB 増えた分 7.8MB
作業用にもう1本 19.2MB 増えた分 7.6MB
100万件の数値の配列は 7.8MB。マージソートはこれとほぼ同じ 7.6MB を、作業用にもう1本必要とします。 メモリ使用量がほぼ2倍になります。 クイックソートとヒープソートは
swapしかしないので、追加はほぼゼロです(クイックソートは再帰の分だけスタックを使いますが、うまくいけば log n 段です)。
これが「O(n log n) の中でどれを選ぶか」の判断材料の1つです。100万件なら 7.6MB は気になりませんが、メモリの少ない機械で大きな配列を扱うなら話が変わります。
測ろうとして失敗した話も書いておきます。 私は最初、setInterval で1ミリ秒ごとにメモリを見て「最大値」を取ろうとしました。1つも記録されませんでした。 JavaScript は1本のスレッドで動くので、ソートが走っている間、タイマーは1回も動けないのです。前回のイベントループの話の、実害の出た形です。
⑤ 直したはずが、別のデータで落ちた
ここが、この記事を書くきっかけになった部分です。
クイックソートは「平均 O(n log n) の速いやつ」として教わります。しかし条件が付きます。
軸の選び方を4通り用意したので、それぞれで比較回数と、再帰の深さを測ります。
import { makeCounter, makeRandom, makeSorted } from './data.js';
import { quickSort } from './sorts.js';
const c = makeCounter();
const N = 4000;
for (const mode of ['first', 'middle', 'random', 'median3']) {
for (const [dn, data] of [['ランダム', makeRandom(N)], ['整列済み', makeSorted(N)]]) {
c.reset();
const stat = { maxDepth: 0 };
const a = data.slice();
const t = performance.now();
quickSort(a, c, mode, stat);
const el = performance.now() - t;
console.log(
mode.padEnd(8, ' '), dn.padEnd(5, ' '),
'比較', String(c.counts.compares).padStart(9),
' 再帰の深さ', String(stat.maxDepth).padStart(5),
' ', el.toFixed(1).padStart(6), 'ms'
);
}
}
console.log('');
console.log(`参考: n=${N} のとき n²/2 = ${N * N / 2}、n*log2(n) = ${Math.round(N * Math.log2(N))}、log2(n) = ${Math.log2(N).toFixed(1)}`);
first ランダム 比較 56856 再帰の深さ 28 6.0 ms
first 整列済み 比較 7998000 再帰の深さ 4000 34.9 ms
middle ランダム 比較 56682 再帰の深さ 32 3.6 ms
middle 整列済み 比較 39917 再帰の深さ 12 2.3 ms
random ランダム 比較 60383 再帰の深さ 30 4.5 ms
random 整列済み 比較 56407 再帰の深さ 31 2.0 ms
median3 ランダム 比較 51908 再帰の深さ 30 3.5 ms
median3 整列済み 比較 39917 再帰の深さ 12 2.9 ms
参考: n=4000 のとき n²/2 = 8000000、n*log2(n) = 47863、log2(n) = 12.0
2行目です。
first 整列済み 比較 7998000 再帰の深さ 4000
比較 7998000 回。参考値の n²/2 = 8000000 とほぼ一致しています。 再帰の深さ 4000。n と同じです。 同じアルゴリズム・同じ件数で、ランダムなら 56856 回だったものが、すでに並んでいるだけで 7998000 回になりました。140倍です。
なぜこうなるかを、絵ではなく手順で説明します。
[0, 1, 2, 3, 4, ..., 3999] に対して、先頭(0)を軸に選びます。
- 軸は
0です。0より小さいものは1つもありません。 - だから「小さい組」は空、「大きい組」は残り 3999個全部になります
- 分けたはずが、1個しか減っていません
- 次も同じことが起きます。軸は
1、小さい組は空、大きい組は 3998個 - これが 4000回繰り返されます
クイックソートの速さは「半分ずつに分けられること」に完全に依存しています。 半分ずつなら 12段(log2(4000) ≒ 12)で終わりますが、1個ずつしか減らないと 4000段になり、各段で全部を見るので n × n になります。
深さ 12 と 4000。 これが middle の行と first の行の差です。
そして落ちる
深さ 4000 で通ったのは運が良かっただけです。件数を増やします。
import { makeSorted } from './data.js';
import { quickSort } from './sorts.js';
const noop = {
lt: (a, b) => a < b, gt: (a, b) => a > b, le: (a, b) => a <= b,
swap: (arr, i, j) => { const t = arr[i]; arr[i] = arr[j]; arr[j] = t; },
write: (arr, i, v) => { arr[i] = v; },
};
const N = Number(process.argv[2] || 20000);
const mode = process.argv[3] || 'first';
console.log(`n = ${N}、軸の選び方 = ${mode}、データ = 整列済み`);
try {
const t = performance.now();
quickSort(makeSorted(N), noop, mode);
console.log('成功:', (performance.now() - t).toFixed(1), 'ms');
} catch (e) {
console.log('失敗:', e.constructor.name + ':', e.message);
}
n = 20000、軸の選び方 = first、データ = 整列済み
失敗: RangeError: Maximum call stack size exceeded
n = 20000、軸の選び方 = median3、データ = 整列済み
成功: 20.1 ms
n = 200000、軸の選び方 = first、データ = 整列済み
失敗: RangeError: Maximum call stack size exceeded
n = 200000、軸の選び方 = median3、データ = 整列済み
成功: 24.1 ms
「遅くなる」では済みませんでした。例外で止まります。
Maximum call stack size exceededは前回の記事で自分で出したものと同じです。あのときは無限再帰でしたが、今回は「終わる処理」なのに深さが足りずに溢れています。 これは本番で起きたらいちばん困る形の障害です。 テストではランダムなデータで通り、本番でORDER BY付きのクエリ結果を渡した瞬間に落ちます。
境目を探します。
import { makeSorted } from './data.js';
import { quickSort } from './sorts.js';
const noop = {
lt: (a, b) => a < b, gt: (a, b) => a > b, le: (a, b) => a <= b,
swap: (arr, i, j) => { const t = arr[i]; arr[i] = arr[j]; arr[j] = t; },
write: (arr, i, v) => { arr[i] = v; },
};
for (const n of [4000, 6000, 8000, 10000, 12000, 14000, 16000]) {
let ok = true;
try { quickSort(makeSorted(n), noop, 'first'); } catch (e) { ok = false; }
console.log(String(n).padStart(6), ok ? '成功' : 'RangeError: Maximum call stack size exceeded');
}
4000 成功
6000 成功
8000 RangeError: Maximum call stack size exceeded
10000 RangeError: Maximum call stack size exceeded
12000 RangeError: Maximum call stack size exceeded
14000 RangeError: Maximum call stack size exceeded
16000 RangeError: Maximum call stack size exceeded
6000件では通り、8000件で落ちます。
「1万件くらいのデータで動いたから大丈夫」は、この境目の上か下かの運の話をしているだけです。 しかも、同じコードでも
--stack-sizeを変えれば境目が動きます。 つまり環境が変われば動いていたものが落ちます。
[スクリーンショット: 02_整列済みで落ちる.png] — node find-limit.js の出力全体を撮ります。6000で成功、8000で Maximum call stack size exceeded の2行が同じ画面に並んでいることが大事です。「すでに並んでいるデータのほうが危ない」が1枚で伝わります。
直し方3通り
さきほどの表を、もう一度読み直します。
| 軸の選び方 | やっていること | 整列済みでの比較回数 | 整列済みでの深さ |
|---|---|---|---|
first 先頭 | lo をそのまま使う | 7998000 | 4000 |
middle 中央 | (lo + hi) >> 1 | 39917 | 12 |
random 無作為 | 範囲内から1つ選ぶ | 56407 | 31 |
median3 3つの中央値 | 先頭・中央・末尾の真ん中の値 | 39917 | 12 |
3通りとも直りました。 それぞれの性質を言います。
middle(中央) は、整列済みに対しては完璧です。真ん中を取れば必ず半分に割れるので、深さ 12(= log2(4000))で終わります。ただし「中央が最小値になるようなデータ」を作れば、同じように壊せます。 攻撃者がいる場面では使えません。
random(無作為) は、どんなデータでも「たまたま毎回いちばん端を引く」確率がほぼゼロなので、悪意あるデータにも強いです。整列済みでの比較 56407 は middle の 39917 より多いですが、「必ず壊れる入力が存在しない」という点で質が違います。ただし結果が実行ごとに変わるので、測定と再現がしにくくなります。
median3(3つの中央値) は、追加のコストがほぼゼロで、整列済みと逆順の両方に効くという良いところ取りです。実際のライブラリでよく使われます。表でも middle と同じ 39917 / 12 になっています。
直したはずが、別のデータで落ちた
ここで私は「median3 にしておけばいい」と結論を出しました。間違いでした。
4種類のデータ全部でやり直したところ、これが出ました。
import { makeRandom, makeSorted, makeReversed, makeFewUnique } from './data.js';
import { quickSort } from './sorts.js';
const noop = { lt: (a,b)=>a<b, gt:(a,b)=>a>b, le:(a,b)=>a<=b,
swap:(arr,i,j)=>{const t=arr[i];arr[i]=arr[j];arr[j]=t;}, write:(arr,i,v)=>{arr[i]=v;} };
const N = 200000;
for (const [dn, d] of [['ランダム', makeRandom(N)], ['整列済み', makeSorted(N)], ['逆順', makeReversed(N)], ['同値多数', makeFewUnique(N)]]) {
const stat = { maxDepth: 0 };
try {
const t = performance.now();
quickSort(d.slice(), noop, 'median3', stat);
console.log(dn, 'OK', (performance.now()-t).toFixed(1), 'ms 深さ', stat.maxDepth);
} catch (e) { console.log(dn, 'NG', e.message, ' 深さ', stat.maxDepth); }
}
ランダム OK 36.4 ms 深さ 94
整列済み OK 19.5 ms 深さ 18
逆順 OK 17.7 ms 深さ 45
同値多数 NG Maximum call stack size exceeded 深さ 5446
同じ値が5種類しかないデータで、深さ 5446 まで積んで溢れました。 軸の選び方は直したのに、落ちました。
理由は軸の選び方ではなく、分け方にありました。
私の実装は「軸より小さいものを左に集める」だけです。軸と同じ値をどちらに入れるかを決めていません。 c.lt(a[j], pivot)(<)なので、軸と同じ値は全部「大きい組」に行きます。
データが [1,3,3,1,2,1,2,0,4,0, ...] のように5種類しかないと、20万件のうち4万件が軸と同じ値になります。その4万件が毎回「大きい組」に押し込まれるので、分割がまったく釣り合いません。
直し方は、軸と同じ値を真ん中に置いて、二度と触らないことです。3分割にします。
sorts.js に足します。
// クイックソート(3分割版):軸より小・軸と同じ・軸より大 の3つに分ける
export function quickSort3(a, c, stat = null, pivotMode = 'median3') {
function sort(lo, hi, depth) {
if (stat && depth > stat.maxDepth) stat.maxDepth = depth;
if (lo >= hi) return;
const mid = (lo + hi) >> 1;
const x = a[lo], y = a[mid], z = a[hi];
let p = mid;
if (pivotMode === 'random') p = lo + Math.floor(Math.random() * (hi - lo + 1));
else if ((x <= y && y <= z) || (z <= y && y <= x)) p = mid;
else if ((y <= x && x <= z) || (z <= x && x <= y)) p = lo;
else p = hi;
const pivot = a[p];
let lt = lo, i = lo, gt = hi;
while (i <= gt) {
if (c.lt(a[i], pivot)) c.swap(a, lt++, i++);
else if (c.gt(a[i], pivot)) c.swap(a, i, gt--);
else i++; // 軸と同じ値は真ん中に置いて、二度と触らない
}
sort(lo, lt - 1, depth + 1);
sort(gt + 1, hi, depth + 1);
}
sort(0, a.length - 1, 1);
return a;
}
else i++; の1行が要点です。 軸と同じ値は動かさず、lt と gt の間に残します。そして再帰は lt-1 までと gt+1 からなので、真ん中の塊は二度と処理されません。
軸の選び方も切り替えられるようにして、両方測ります。
import { makeRandom, makeSorted, makeReversed, makeFewUnique } from './data.js';
import { quickSort3 } from './sorts.js';
const noop = { lt:(a,b)=>a<b, gt:(a,b)=>a>b, le:(a,b)=>a<=b,
swap:(arr,i,j)=>{const t=arr[i];arr[i]=arr[j];arr[j]=t;}, write:(arr,i,v)=>{arr[i]=v;} };
const N = 200000;
for (const mode of ['median3','random']) {
for (const [dn, d] of [['ランダム', makeRandom(N)], ['整列済み', makeSorted(N)], ['逆順', makeReversed(N)], ['同値多数', makeFewUnique(N)]]) {
const stat = { maxDepth: 0 };
const a = d.slice();
const t = performance.now();
quickSort3(a, noop, stat, mode);
const ok = a.every((v,i)=> i===0 || a[i-1] <= v);
console.log(mode.padEnd(8), dn.padEnd(5,' '), ok?'OK':'NG', (performance.now()-t).toFixed(1).padStart(6), 'ms 深さ', stat.maxDepth);
}
}
median3 ランダム OK 46.0 ms 深さ 24
median3 整列済み OK 184.2 ms 深さ 471
median3 逆順 OK 123.9 ms 深さ 336
median3 同値多数 OK 5.1 ms 深さ 4
random ランダム OK 38.6 ms 深さ 31
random 整列済み OK 29.4 ms 深さ 45
random 逆順 OK 30.7 ms 深さ 44
random 同値多数 OK 5.5 ms 深さ 6
上の4行を見てください。
同値多数は 5.1ミリ秒・深さ4 で完全に直りました。 落ちていたものが、いちばん速いデータになりました。 同じ値の塊を1回で確定させているので当然です。 その代わり、整列済みが 19.5ミリ秒 → 184.2ミリ秒 と 9倍遅くなり、深さも 18 → 471 に増えました。
直したら別のところが壊れました。 これはよくあることなので、原因を書いておきます。
3分割の交換ループは c.swap(a, i, gt--) で、軸より大きい値を配列の末尾側へ飛ばします。 整列済みのデータでこれをやると、「並んでいる」という性質そのものを壊してしまいます。 その結果、次の段で「先頭・中央・末尾の中央値」を取っても、もう真ん中の値ではなくなっています。
下の4行が答えです。
random ランダム OK 38.6 ms 深さ 31
random 整列済み OK 29.4 ms 深さ 45
random 逆順 OK 30.7 ms 深さ 44
random 同値多数 OK 5.5 ms 深さ 6
3分割 + 無作為な軸。4種類すべてで 深さ 50以下、時間も 5〜39ミリ秒に収まりました。 どのデータでも壊れない形に、やっと着きました。
ここまでの経緯を並べます。
| 版 | 直したこと | 新しく出た問題 |
|---|---|---|
| 1. 先頭を軸 | — | 整列済みで O(n²)、8000件で落ちる |
| 2. 3つの中央値 | 整列済みが 深さ12 に | 同値多数で 深さ5446、落ちる |
| 3. 3分割 | 同値多数が 深さ4 に | 整列済みが 9倍遅く、深さ471 |
| 4. 3分割 + 無作為な軸 | 全部 深さ50以下 | (見つかっていない) |
4段階かかりました。しかも私は、4種類のデータで測るまで、2と3の問題に気づいていません。 これが「ソートは自分で書かない」の理由です。 「動いた」までは30分ですが、「どんなデータでも壊れない」までは、ここまでの全部が必要でした。 そして4番目にも、まだ私が試していないデータで壊れる可能性が残っています。
⑥ 安定性 — 同点の人の順番が入れ替わる
もう1つ、実務で刺される性質があります。
私は一度、受付順に並んだ参加者リストを点数の高い順に並べ替えて出したところ、「同点の2人の順番が、前回出した表と違う」と言われたことがあります。データは同じ、点数も同じ、同点の人の並びだけが違いました。
これが「安定なソート」の話です。
import { makeCounter } from './data.js';
import { bubbleSort, selectionSort, insertionSort, mergeSort, quickSort, heapSort } from './sorts.js';
// 8人。点数が同じ人が何組もいる。もとの順番(受付順)に意味がある
const people = [
{ name: 'あおい', score: 70 },
{ name: 'いつき', score: 90 },
{ name: 'うみ', score: 70 },
{ name: 'えいた', score: 80 },
{ name: 'おと', score: 90 },
{ name: 'かえで', score: 70 },
{ name: 'きよ', score: 80 },
{ name: 'くるみ', score: 90 },
];
// 比較のときだけ score を見る比較器
function scoreCounter() {
return {
counts: { compares: 0, swaps: 0, writes: 0 },
lt: (a, b) => a.score < b.score,
gt: (a, b) => a.score > b.score,
le: (a, b) => a.score <= b.score,
swap(arr, i, j) { const t = arr[i]; arr[i] = arr[j]; arr[j] = t; },
write(arr, i, v) { arr[i] = v; },
};
}
const show = (a) => a.map((p) => `${p.name}(${p.score})`).join(' ');
console.log('もとの順 ', show(people));
console.log('');
const algos = [
['バブル ', bubbleSort], ['選択 ', selectionSort], ['挿入 ', insertionSort],
['マージ ', mergeSort], ['クイック', (a, c) => quickSort(a, c, 'median3')], ['ヒープ ', heapSort],
];
for (const [name, fn] of algos) {
const a = people.slice();
fn(a, scoreCounter());
console.log(name, show(a));
}
console.log('V8 sort ', show(people.slice().sort((x, y) => x.score - y.score)));
もとの順 あおい(70) いつき(90) うみ(70) えいた(80) おと(90) かえで(70) きよ(80) くるみ(90)
バブル あおい(70) うみ(70) かえで(70) えいた(80) きよ(80) いつき(90) おと(90) くるみ(90)
選択 あおい(70) うみ(70) かえで(70) えいた(80) きよ(80) いつき(90) おと(90) くるみ(90)
挿入 あおい(70) うみ(70) かえで(70) えいた(80) きよ(80) いつき(90) おと(90) くるみ(90)
マージ あおい(70) うみ(70) かえで(70) えいた(80) きよ(80) いつき(90) おと(90) くるみ(90)
クイック うみ(70) かえで(70) あおい(70) えいた(80) きよ(80) いつき(90) おと(90) くるみ(90)
ヒープ かえで(70) あおい(70) うみ(70) きよ(80) えいた(80) おと(90) くるみ(90) いつき(90)
V8 sort あおい(70) うみ(70) かえで(70) えいた(80) きよ(80) いつき(90) おと(90) くるみ(90)
70点の3人を見てください。 もとの順番は あおい → うみ → かえで です。
| アルゴリズム | 70点の3人の順番 |
|---|---|
| バブル | あおい うみ かえで ← 元のまま |
| 選択 | あおい うみ かえで ← 元のまま |
| 挿入 | あおい うみ かえで ← 元のまま |
| マージ | あおい うみ かえで ← 元のまま |
| クイック | うみ かえで あおい ← 壊れた |
| ヒープ | かえで あおい うみ ← 壊れた |
| V8 sort | あおい うみ かえで ← 元のまま |
クイックソートとヒープソートは、点数が同じ人の順番を保ちません。 どちらも「正しく並べ替えている」のに、出力が違います。 点数だけを見れば全部正解です。 でも見る人には「順番が変わった」と見えます。
「安定」の意味を、もう一度はっきり言います。
安定(stable)とは、比較して同じだった2つの相対的な順番が、元と変わらないこと。 「安定して動く」「クラッシュしない」という意味ではまったくありません。 私は最初これを混同していました。
選択ソートも実は不安定
上の表で選択ソートは元のままでした。でもこれは、たまたまです。
import { selectionSort, bubbleSort, insertionSort, mergeSort } from './sorts.js';
function scoreCounter() {
return {
lt: (a, b) => a.score < b.score, gt: (a, b) => a.score > b.score, le: (a, b) => a.score <= b.score,
swap(arr, i, j) { const t = arr[i]; arr[i] = arr[j]; arr[j] = t; },
write(arr, i, v) { arr[i] = v; },
};
}
// 選択ソートの「不安定」を出すには、同点が先にあって、小さい値が後にある形
const data = [
{ name: 'A', score: 70 },
{ name: 'B', score: 70 },
{ name: 'C', score: 50 },
];
const show = (a) => a.map((p) => `${p.name}(${p.score})`).join(' ');
console.log('もとの順', show(data));
console.log('選択 ', show(selectionSort(data.slice(), scoreCounter())));
console.log('バブル ', show(bubbleSort(data.slice(), scoreCounter())));
console.log('挿入 ', show(insertionSort(data.slice(), scoreCounter())));
console.log('マージ ', show(mergeSort(data.slice(), scoreCounter())));
console.log('V8 sort ', show(data.slice().sort((x, y) => x.score - y.score)));
もとの順 A(70) B(70) C(50)
選択 C(50) B(70) A(70)
バブル C(50) A(70) B(70)
挿入 C(50) A(70) B(70)
マージ C(50) A(70) B(70)
V8 sort C(50) A(70) B(70)
たった3件で、選択ソートが
A BをB Aにしました。 起きたことは1行です。選択ソートは「先頭(A)」と「最小値(C)」を交換します。 そのとき A は C の場所(末尾)に飛ばされ、B より後ろに行きます。 「1回の交換で遠くまで飛ばす」アルゴリズムは、原理的に安定になれません。
これで判断基準が言えます。
隣同士しか交換しないなら安定になれる。遠くへ飛ばすなら安定になれない。 バブル(隣だけ)・挿入(1つずつずらす)・マージ(順番に取り出す)は安定。 選択・クイック・ヒープは遠くへ飛ばすので不安定です。
マージソートは1文字で不安定になる
マージソートに入れたコメントを回収します。
if (c.le(a[i], a[j])) buf[k++] = a[i++]; // <= が安定性のかなめ
c.le は <= です。左半分と右半分の先頭が同じ値だったとき、左を先に取ります。 左半分は元の配列で前にあった側なので、元の順番が保たれます。
ここを c.lt(<)に書き換えると、同じ値のとき右を先に取るので、マージソートは不安定になります。 1文字です。
安定であることは、アルゴリズムの名前で決まっているのではなく、実装の中のこの1文字で決まっています。 「マージソートは安定」と丸暗記していると、自分で書いたときに気づかずに壊せます。
安定でないと何が困るのか
「同点の順番なんて気にしない」と思うかもしれません。2段並べ替えをする場面で困ります。
たとえば「部署順に並べて、その中で点数順」にしたいとします。安定なソートなら、こうできます。
- まず点数順に並べる
- 次に部署順に並べる
安定なので、2回目の並べ替えでも、同じ部署の中は点数順のまま残ります。 これは実際によく使う手です。
不安定なソートでこれをやると、2回目で1回目の結果が壊れます。
ORDER BY を2列書けるSQLに慣れていると気づきにくいですが、アプリ側で並べ替えているときは、この性質に頼っているコードがよくあります。
JavaScript については、覚えることは1つです。
Array.prototype.sortは ES2019 から、仕様で安定であることが決まっています。 それ以前は「実装に任される」ことになっていて、同じコードがブラウザによって違う順番を返しました。 短い配列だけ安定、長い配列は不安定という実装もありました。 いまの Node.js と主要ブラウザでは、安定です。 ただし自分で書いたソートは、自分で保証するしかありません。
⑦ ヒープソートと、本物の sort
6つ目を書きます。
// ヒープソート:配列を二分ヒープと見なし、根(最大)を後ろへ運ぶ
export function heapSort(a, c) {
const n = a.length;
function siftDown(start, end) {
let root = start;
while (root * 2 + 1 <= end) {
const child = root * 2 + 1;
let big = child;
if (child + 1 <= end && c.lt(a[child], a[child + 1])) big = child + 1;
if (c.lt(a[root], a[big])) { c.swap(a, root, big); root = big; }
else return;
}
}
for (let i = (n - 2) >> 1; i >= 0; i--) siftDown(i, n - 1);
for (let end = n - 1; end > 0; end--) { c.swap(a, 0, end); siftDown(0, end - 1); }
return a;
}
ヒープソートは、配列を木として見るところが要点です。
a[i] の子は a[2i+1] と a[2i+2]。それだけです。 ポインタも別の配列も作りません。添字の計算で木の形を表現しています。
その木を「親は必ず子より大きい」状態(ヒープ)に整えると、根(a[0])が最大値になります。あとは根を末尾と交換して、末尾を確定させ、範囲を1つ縮めてまた整える。これを繰り返します。
ヒープソートの長所は「予測しやすさ」です。
- 最悪でも O(n log n)。 クイックソートのように O(n²) に落ちる入力が存在しません
- 追加メモリがほぼゼロ。 マージソートのように n 本もう1本要りません
- 再帰していません。
whileとforだけなので、スタックが溢れません
にもかかわらず、標準ライブラリで使われることは少ないです。 理由は⑧で書きます。
本物の sort は何をしているのか
さて、V8(Chrome と Node.js の JavaScript エンジン)の Array.prototype.sort は何をしているか。
TimSort です。 マージソートと挿入ソートを組み合わせたもので、2002年に Python のために Tim Peters が書いたものです。Python、Java(オブジェクトの配列)、そして V8 が使っています。V8 は2018年(Chrome 70)にクイックソートから TimSort に変えました。
やっていることを、この記事でやったことに対応させると3つです。
- 配列を走査して、すでに昇順(または降順)に並んでいる連続区間(run)を探す。 降順の run は反転して昇順にする
- 短い run は、挿入ソートで伸ばして、ある長さ以上にする
- run 同士をマージする(マージソートの統合の部分)
「すでに並んでいる区間を探して、そのまま使う」のが TimSort の核心です。 ③で見た「挿入ソートは整列済みなら比較 1999回で終わる」という性質を、アルゴリズムの中に組み込んだ形です。
なぜ短い run に挿入ソートを使うのかも、測れば分かります。
import { makeRandom } from './data.js';
import { insertionSort, mergeSort } from './sorts.js';
const noop = { lt:(a,b)=>a<b, gt:(a,b)=>a>b, le:(a,b)=>a<=b,
swap:(arr,i,j)=>{const t=arr[i];arr[i]=arr[j];arr[j]=t;}, write:(arr,i,v)=>{arr[i]=v;} };
const REP = 200000;
console.log(`長さ n の配列を ${REP} 回並べ替えたときの合計(ミリ秒)`);
console.log('');
console.log(' n | 挿入ソート | マージソート');
for (const n of [4, 8, 16, 32, 64, 128]) {
const src = makeRandom(n, 31);
const copies = [];
for (let i = 0; i < REP; i++) copies.push(src.slice());
let t = performance.now();
for (let i = 0; i < REP; i++) insertionSort(copies[i], noop);
const ins = performance.now() - t;
const copies2 = [];
for (let i = 0; i < REP; i++) copies2.push(src.slice());
t = performance.now();
for (let i = 0; i < REP; i++) mergeSort(copies2[i], noop);
const mrg = performance.now() - t;
console.log(String(n).padStart(4), '|', ins.toFixed(1).padStart(10), '|', mrg.toFixed(1).padStart(12));
}
長さ n の配列を 200000 回並べ替えたときの合計(ミリ秒)
n | 挿入ソート | マージソート
4 | 15.3 | 45.1
8 | 17.2 | 78.0
16 | 30.4 | 121.7
32 | 103.9 | 284.8
64 | 406.6 | 656.2
128 | 1778.4 | 1676.2
n が 64 以下では、O(n²) の挿入ソートのほうが O(n log n) のマージソートより速いです。 n=8 で 17.2 対 78.0。4.5倍速いです。 逆転するのは n=128 のあたりでした(1778.4 対 1676.2)。 理由は、マージソートには「割る」「作業用配列に書く」「戻す」という手間があり、小さいときはその手間のほうが大きいからです。
これがO記法の限界です。 O記法は「n が十分大きいとき」の話をしていて、小さい n については何も言っていません。 だから TimSort は「小さい塊は挿入ソート」という設計になっています。
run を探していることを、測って確かめる
「並んでいる区間を探している」という説明が本当かどうか、同じ関数に、並びの壊れ具合だけを変えたデータを渡して確かめます。
import { makeRandom, makeSorted } from './data.js';
const N = 200000;
function makeAlmostSorted(n, ratio) {
const a = makeSorted(n); let s = 4242;
const k = Math.floor(n * ratio);
for (let i = 0; i < k; i++) {
s = (s * 1103515245 + 12345) & 0x7fffffff; const p = s % n;
s = (s * 1103515245 + 12345) & 0x7fffffff; const q = s % n;
const t = a[p]; a[p] = a[q]; a[q] = t;
}
return a;
}
function makeTwoRuns(n) { const a = []; for (let i=0;i<n/2;i++) a.push(i*2); for (let i=0;i<n/2;i++) a.push(i*2+1); return a; }
function makeManyRuns(n, runLen) {
const a = [];
for (let i = 0; i < n; i += runLen) for (let j = 0; j < runLen && i + j < n; j++) a.push(i + j);
return a;
}
const sets = [
['ランダム', makeRandom(N)],
['整列済み(run 1本)', makeSorted(N)],
['run 2本', makeTwoRuns(N)],
['run 多数(長さ64ずつ)', makeManyRuns(N, 64)],
['1%だけ崩した', makeAlmostSorted(N, 0.01)],
['10%崩した', makeAlmostSorted(N, 0.10)],
['50%崩した', makeAlmostSorted(N, 0.50)],
];
function median(xs){const s=xs.slice().sort((a,b)=>a-b);return s[s.length>>1];}
const cmp = (x, y) => x - y;
console.log(`V8 の sort に同じ比較関数を渡して、並びの「壊れ具合」だけを変えた(n = ${N}、5回の中央値、ミリ秒)`);
console.log('');
for (const [dn, d] of sets) {
const r = [];
for (let i = 0; i < 5; i++) { const a = d.slice(); const t = performance.now(); a.sort(cmp); r.push(performance.now() - t); }
console.log(dn.padEnd(24, ' '), median(r).toFixed(1).padStart(6), 'ms');
}
V8 の sort に同じ比較関数を渡して、並びの「壊れ具合」だけを変えた(n = 200000、5回の中央値、ミリ秒)
ランダム 55.3 ms
整列済み(run 1本) 3.4 ms
run 2本 6.3 ms
run 多数(長さ64ずつ) 3.2 ms
1%だけ崩した 8.9 ms
10%崩した 11.2 ms
50%崩した 10.5 ms
同じ sort、同じ比較関数、同じ 20万件です。
ランダム 55.3ミリ秒 対 整列済み 3.4ミリ秒。16倍違います。 「run が多数(長さ64の塊が3125個)」も 3.2ミリ秒。 つまり1本に並んでいなくても、塊になっていれば速いのです。これが run を探していることの証拠です。 「1%だけ崩した」が 8.9ミリ秒。 崩し方を 10% にしても 11.2ミリ秒で、あまり増えません。ランダム(55.3)にはまったく届きません。
この表が言っていることは、実務では大きい話です。
「DBから
ORDER BY created_atで取ってきた配列を、アプリ側でcreated_atで並べ替え直す」という無駄なコードは、無駄なのに速いので、性能問題として発見されません。 逆に、シャッフルしてから渡すと16倍遅くなります。 何もしていないのに。
[スクリーンショット: 03_並びの壊れ具合で16倍.png] — node runs.js の出力全体を撮ります。「ランダム 55.3ms」と「整列済み 3.4ms」が同じ画面に並んでいることが大事です。同じ関数・同じ件数でこれだけ違う、が1枚で伝わります。
⑧ 1枚の総括表
最後に、6つと V8 を同じデータで測ります。
測り方を変えます。 ここまでは1つのプロセスで全部測っていましたが、JavaScript は同じプロセスで走らせるほど後のものが速く(あるいは遅く)なることがあります(実行中に機械語へ最適化していくため)。だから1つずつ別のプロセスで測ります。
import { makeRandom, makeSorted, makeReversed, makeFewUnique } from './data.js';
import { bubbleSort, selectionSort, insertionSort, mergeSort, quickSort3, heapSort } from './sorts.js';
const noop = { lt:(a,b)=>a<b, gt:(a,b)=>a>b, le:(a,b)=>a<=b,
swap:(arr,i,j)=>{const t=arr[i];arr[i]=arr[j];arr[j]=t;}, write:(arr,i,v)=>{arr[i]=v;} };
const N = Number(process.argv[3]);
const which = process.argv[2];
const table = {
bubble: (a) => bubbleSort(a, noop),
selection: (a) => selectionSort(a, noop),
insertion: (a) => insertionSort(a, noop),
merge: (a) => mergeSort(a, noop),
quick: (a) => quickSort3(a, noop, null, 'random'),
heap: (a) => heapSort(a, noop),
v8: (a) => a.sort((x, y) => x - y),
};
const label = { bubble:'バブル', selection:'選択', insertion:'挿入', merge:'マージ', quick:'クイック', heap:'ヒープ', v8:'V8 sort' };
const fn = table[which];
const sets = [makeRandom(N), makeSorted(N), makeReversed(N), makeFewUnique(N)];
function median(xs){const s=xs.slice().sort((a,b)=>a-b);return s[s.length>>1];}
function bench(d){const r=[];for(let i=0;i<5;i++){const a=d.slice();const t=performance.now();fn(a);r.push(performance.now()-t);}return median(r);}
console.log(`| ${label[which]} | ${sets.map(d=>bench(d).toFixed(1)).join(' | ')} |`);
| バブル | 694.4 | 0.1 | 659.5 | 758.4 |
| 選択 | 284.7 | 306.5 | 327.7 | 377.4 |
| 挿入 | 127.2 | 0.1 | 189.4 | 73.4 |
| マージ | 3.7 | 1.6 | 1.9 | 2.4 |
| クイック | 2.4 | 2.0 | 2.1 | 0.3 |
| ヒープ | 3.4 | 1.4 | 1.4 | 1.2 |
| V8 sort | 5.3 | 0.4 | 0.4 | 2.5 |
n = 20000、単位はミリ秒、5回測った中央値です。
| アルゴリズム | ランダム | 整列済み | 逆順 | 同値多数 |
|---|---|---|---|---|
| バブル | 694.4 | 0.1 | 659.5 | 758.4 |
| 選択 | 284.7 | 306.5 | 327.7 | 377.4 |
| 挿入 | 127.2 | 0.1 | 189.4 | 73.4 |
| マージ | 3.7 | 1.6 | 1.9 | 2.4 |
| クイック(3分割・無作為な軸) | 2.4 | 2.0 | 2.1 | 0.3 |
| ヒープ | 3.4 | 1.4 | 1.4 | 1.2 |
| V8 sort | 5.3 | 0.4 | 0.4 | 2.5 |
O(n²) の3つを外して、件数を10倍にします。
| マージ | 37.2 | 19.1 | 21.5 | 26.2 |
| クイック | 19.5 | 20.1 | 19.8 | 2.5 |
| ヒープ | 24.0 | 13.7 | 14.3 | 11.8 |
| V8 sort | 55.3 | 3.5 | 3.8 | 25.5 |
n = 200000 の表です。
| アルゴリズム | ランダム | 整列済み | 逆順 | 同値多数 |
|---|---|---|---|---|
| マージ | 37.2 | 19.1 | 21.5 | 26.2 |
| クイック(3分割・無作為な軸) | 19.5 | 20.1 | 19.8 | 2.5 |
| ヒープ | 24.0 | 13.7 | 14.3 | 11.8 |
| V8 sort | 55.3 | 3.5 | 3.8 | 25.5 |
予想と違ったこと
私はここで「自作は全部 V8 に負ける」という結果を期待していました。負けませんでした。
n=200000 のランダムなデータで、自作クイックソート 19.5ミリ秒、V8 の
sort55.3ミリ秒。自作が 2.8倍速い。
これは測り間違いではありません。理由が分かります。
V8 の sort は、比較のたびに、私が渡した (x, y) => x - y という JavaScript の関数を呼んでいます。 20万件なら比較は約350万回なので、JavaScript の関数呼び出しが350万回起きています。
私の自作クイックソートは、比較を a[i] < pivot と式で直接書いているので、関数呼び出しがありません。
この差を確かめるために、自作マージソートを「比較関数を受け取る形」に書き換えて測りました。
import { makeRandom, makeSorted } from './data.js';
const N = 200000;
// 自作マージソートに「比較関数を渡す形」にしたもの(V8 sort と同じ条件にする)
function mergeSortCmp(a, cmp) {
const buf = new Array(a.length);
(function sort(lo, hi) {
if (hi - lo < 2) return;
const mid = (lo + hi) >> 1;
sort(lo, mid); sort(mid, hi);
let i = lo, j = mid, k = lo;
while (i < mid && j < hi) buf[k++] = cmp(a[i], a[j]) <= 0 ? a[i++] : a[j++];
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
for (let t = lo; t < hi; t++) a[t] = buf[t];
})(0, a.length);
return a;
}
// 比較を式で直接書いた版
function mergeSortInline(a) {
const buf = new Array(a.length);
(function sort(lo, hi) {
if (hi - lo < 2) return;
const mid = (lo + hi) >> 1;
sort(lo, mid); sort(mid, hi);
let i = lo, j = mid, k = lo;
while (i < mid && j < hi) buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i < mid) buf[k++] = a[i++];
while (j < hi) buf[k++] = a[j++];
for (let t = lo; t < hi; t++) a[t] = buf[t];
})(0, a.length);
return a;
}
const cmp = (x, y) => x - y;
function median(xs){const s=xs.slice().sort((a,b)=>a-b);return s[s.length>>1];}
function bench(fn, data){const r=[];for(let i=0;i<5;i++){const a=data.slice();const t=performance.now();fn(a);r.push(performance.now()-t);}return median(r);}
const rnd = makeRandom(N), srt = makeSorted(N);
console.log(`n = ${N} 5回の中央値 単位はミリ秒`);
console.log('');
console.log(' ランダム 整列済み');
console.log('自作マージ(比較を式で直接) ', bench(mergeSortInline, rnd).toFixed(1).padStart(6), bench(mergeSortInline, srt).toFixed(1).padStart(8));
console.log('自作マージ(比較関数を渡す) ', bench((a)=>mergeSortCmp(a,cmp), rnd).toFixed(1).padStart(6), bench((a)=>mergeSortCmp(a,cmp), srt).toFixed(1).padStart(8));
console.log('V8 sort(比較関数を渡す) ', bench((a)=>a.sort(cmp), rnd).toFixed(1).padStart(6), bench((a)=>a.sort(cmp), srt).toFixed(1).padStart(8));
console.log('V8 sort(比較関数なし=文字列)', bench((a)=>a.sort(), rnd).toFixed(1).padStart(6), bench((a)=>a.sort(), srt).toFixed(1).padStart(8));
n = 200000 5回の中央値 単位はミリ秒
ランダム 整列済み
自作マージ(比較を式で直接) 70.9 37.3
自作マージ(比較関数を渡す) 66.3 27.0
V8 sort(比較関数を渡す) 90.5 5.7
V8 sort(比較関数なし=文字列) 160.5 21.7
この表の数字は、one.js の表とずれています。 同じプロセスで4つを続けて測っているせいです。性能を測るときは、測り方の違いが結果を変えます。 数字の絶対値を持ち出すときは、必ずどう測ったかを一緒に書いてください。
それでも行の間の関係は読めます。sort() に比較関数を渡さない最後の行が、ランダムで 160.5ミリ秒で最も遅いのが目を引きます。文字列に変換する手間が入るからです。①で見た「間違った結果を返すやり方」は、遅くもあります。
では、自作を採用してよいのか
駄目です。 理由を、この記事で自分が実際に踏んだものだけで並べます。
| 理由 | この記事で起きたこと |
|---|---|
| 1. データの形が変わると壊れる | 4段階直して、やっと4種類のデータで壊れなくなった。5種類目で壊れないとは言えない |
| 2. 落ちるのは「遅くなる」より悪い | Maximum call stack size exceeded。6000件で通り8000件で落ちた |
| 3. 安定性を自分で保証しないといけない | マージソートは <= を < にした瞬間に不安定になる。1文字 |
| 4. すでに並んでいるデータで、まったく勝てない | 整列済み 20万件で V8 は 3.5ミリ秒。自作クイックは 20.1ミリ秒。6倍負け。しかも実務のデータはたいてい少し並んでいる |
| 5. 勝った 2.8倍は、比較関数を使わない場合だけ | 数値の配列で、比較のロジックを書き換える予定がないという条件付きの勝ちです |
| 6. 誰も読めない | 3分割クイックソートの while (i <= gt) を、半年後の自分が正しく直せる自信はありません |
結論はこうです。
ソートは自分で書かない。
sortに比較関数を渡す。 でも、次の2つは説明できるようにしておく。 1. なぜ、すでに並んでいると速いのか → TimSort が run を探して再利用しているから 2. なぜ、同点の順番が保たれるのか → 仕様で安定と決まっていて、マージの取り方が<=になっているから
6つの性質を1枚に
この記事で書いた6つの、教科書に載っている性質と、実測をまとめます。
| 名前 | 平均 | 最悪 | 追加メモリ | 安定か | 実測での特徴(n=20000) |
|---|---|---|---|---|---|
| バブル | O(n²) | O(n²) | O(1) | 安定 | 整列済みなら 0.1ms(早期打ち切りあり)。それ以外は最下位 |
| 選択 | O(n²) | O(n²) | O(1) | 不安定 | どのデータでも 285〜377ms で変わらない。書き込みだけは 3992回で最少 |
| 挿入 | O(n²) | O(n²) | O(1) | 安定 | 整列済みなら 0.1ms・比較 n-1 回。TimSort が中で使う理由 |
| マージ | O(n log n) | O(n log n) | O(n) | 安定 | どのデータでも 1.6〜3.7ms。予測しやすい。ただし 100万件で +7.6MB |
| クイック | O(n log n) | O(n²) | O(log n) | 不安定 | 実装を4段階直すまで落ちた。直せば最速級(同値多数 0.3ms) |
| ヒープ | O(n log n) | O(n log n) | O(1) | 不安定 | 最悪でも崩れず、追加メモリなし、再帰なし。 それでも標準では使われない |
V8 の sort(TimSort) | O(n log n) | O(n log n) | O(n) | 安定 | 並びの壊れ具合で 3.4〜55.3ms(16倍) |
「ヒープソートは最悪でも O(n log n)、追加メモリなし、再帰なし。なのに標準では使われない」という行が残っています。理由を書いておきます。
- 不安定です。 標準ライブラリは安定である必要があります(ES2019 で決まりました)
- メモリの近い場所を続けて読まないので、実測ではクイックソートより遅いことが多い(表でもランダムで 24.0 対 19.5)。木の親と子は添字が2倍離れるので、CPU のキャッシュに乗りません
- すでに並んでいるデータで速くなりません。 表を見ると整列済み 13.7ms で、V8 の 3.5ms に完全に負けています
「最悪ケースの保証が強い」ことは、「実務で速い」ことと別でした。これがO記法だけでは分からない部分です。
つまずいたところ
1. 乱数で作ったデータで測って、結果が毎回変わった。 最初は Math.random() でデータを作っていたので、「バブルが遅い」のか「今回のデータが悪かった」のか分かりませんでした。 種を固定できる乱数(s = (s * 1103515245 + 12345) & 0x7fffffff)に変えて解決しました。性能を比べるなら、入力を固定するのが先です。
2. 回数を数えるコードが、測定結果を2.3倍変えていた。 c.lt(a, b) のように関数を通して数えると、n=200000 のマージソートが 35.0ms → 82.1ms になりました。回数を数えるときと時間を測るときで、別のものを渡す必要がありました。測るための道具が測定対象を変えるのは、性能測定でいつでも起きます。
3. 「同じ O(n²)」だと思っていた3つが、書き込み回数で500倍違った。 n=2000 のランダムで、バブル 1997750 回、選択 3992 回。O記法は定数倍を無視するので、この差が完全に見えません。 「バブルと選択はどちらも遅い」で終わらせていたら、「書き込みが高くつくときは選択のほうがまし」という判断ができません。
4. クイックソートを「速いやつ」として覚えていて、整列済みで落とした。 Maximum call stack size exceeded が出るまで、すでに並んでいるデータが最悪ケースだと知りませんでした。 しかも 6000件では通り、8000件で落ちます。「手元のデータで動いた」は、境目のどちら側かの運の話でした。
5. 軸を直したら、別のデータで落ちた。 median3 にして整列済みは直ったのに、同じ値が5種類しかないデータで深さ 5446 になって落ちました。 原因は軸ではなく分け方で、「軸と同じ値をどちらの組に入れるか決めていない」ことでした。1種類のデータで直ったことを確認して終わりにしたのが間違いでした。
6. 3分割に直したら、今度は整列済みが 9倍遅くなった。 同値多数は 5.1ms・深さ4 に直ったのに、整列済みが 19.5ms → 184.2ms、深さ 18 → 471 に。3分割の交換が「並んでいる」性質を壊すからでした。無作為な軸に変えて、やっと4種類全部で収まりました。4段階かかりました。
7. メモリの最大値を setInterval で取ろうとして、1回も記録されなかった。 1ミリ秒ごとにメモリを見るタイマーを仕込んだのに、増分が全部 0.0MB でした。JavaScript は1本のスレッドなので、ソートが走っている間タイマーは動けません。 前後で測る形に変えました。
8. 同じ数字を2回測って、55.3ms と 93.5ms になった。 プロセスを立ち上げた直後の1回目は、まだ機械語への最適化が済んでいないので数字が跳ねます。2回目以降は 53〜55ms で安定しました。 1回測って数字を出すのは危ないです。 この記事では5回測って中央値を使い、⑧では1アルゴリズムごとに別プロセスにしました。
後片づけ
作ったものを全部消します。
まず、何を消すのか確認します。
total 76
drwxrwxr-x 2 user user 4096 Oct 2 11:20 .
drwxrwxr-x 3 user user 4096 Oct 2 09:48 ..
-rw-rw-r-- 1 user user 982 Oct 2 10:31 bench.js
-rw-rw-r-- 1 user user 312 Oct 2 09:55 check.js
-rw-rw-r-- 1 user user 1104 Oct 2 10:02 count-n2.js
-rw-rw-r-- 1 user user 1188 Oct 2 09:52 data.js
(以下略)
この記事で触ったのは ~/cslab/ の中だけです。 npm install をしていないので、他の場所には何も置いていません。
grep が何も出さなければ消えています。何も表示されないのが成功です。
念のため確認します。
消えています
rm -rf は戻せません。 打つ前に、パスが ~/cslab/ になっていることを目で確認してください。
まとめ — 理解できたこと
[1,2,10].sort()が[1,10,2]を返すのは仕様。 比較関数を渡さないと要素は文字列にされて辞書順に並ぶ。[1,100,25,3,80,9]と['1','100','25','3','80','9']の並びが完全に一致することで確かめました。直し方はsort((a,b) => a-b)- 日本語とファイル名は
a - bでも<でも並ばない。localeCompare(b, 'ja')で五十音順、{ numeric: true }でfile9.txtの後ろにfile10.txt。そしてlocaleCompareを比較関数の中で毎回呼ぶと 9360ms、Intl.Collatorを1個作って使い回すと 353ms(26倍) - 性能を比べるなら、入力を固定するのが先。 種を固定できる乱数にするまで、測定結果が毎回変わって何も言えませんでした。そして回数を数えるコード自体が測定を 2.3倍変えます
- 時間はマシンで変わるが、比較回数は変わらない。 アルゴリズムの性質を見たいなら、回数を数えるほうが正しい
- 「同じ O(n²)」の3つは実測では別物。 n=2000 のランダムで、比較回数はどれも約200万で並ぶのに、書き込み回数がバブル 199万・挿入 100万・選択 3992(500倍差)。O記法は定数倍を無視するので、この差は見えません
- 挿入ソートは整列済みなら比較 n-1 回で終わる。 n=2000 で 1999回。O(n²) が O(n) になります。 そしてn が 64 以下ではマージソートより速い(n=8 で 4.5倍)。これが TimSort が挿入ソートを中で使う理由
- 選択ソートは4種類のデータで比較回数が完全に同じ 1999000。 最良も最悪もありません。予測しやすいという長所と、並んでいても速くならないという短所が同じ性質から来ています
- クイックソートは、すでに並んでいるデータで先頭を軸にすると O(n²) になり、落ちる。 n=4000 で比較 7998000 回・深さ 4000。6000件では通り、8000件で
Maximum call stack size exceeded。 「遅くなる」で済まず、例外で止まります - 軸を直しても終わりではなかった。
median3で整列済みは直ったのに、同値多数で深さ 5446。3分割に直したら整列済みが 9倍遅く。4段階(先頭 → 3つの中央値 → 3分割 → 3分割+無作為な軸)かけて、やっと4種類全部で壊れなくなりました - 「安定」は「同点のとき元の順番が保たれる」という意味で、「クラッシュしない」ではない。 たった3件(A70 B70 C50)で選択ソートが
A BをB Aにしました。 判断基準は「隣同士しか交換しないか、遠くへ飛ばすか」。バブル・挿入・マージは安定、選択・クイック・ヒープは不安定 - 安定かどうかは、実装の1文字で決まる。 マージソートの
c.le(<=)をc.lt(<)にすると不安定になります。「マージソートは安定」は丸暗記できる知識ではありません - V8 の
sortは TimSort で、すでに並んでいる区間(run)を探して再利用している。 同じ 20万件・同じ比較関数で、ランダム 55.3ms 対 整列済み 3.4ms(16倍)。 「長さ64の塊が3125個」でも 3.2ms なので、1本に並んでいなくても塊になっていれば速い - 自作が V8 に勝つ場面もある。 n=200000 のランダムな整数で自作クイック 19.5ms 対 V8 55.3ms(2.8倍)。理由は V8 が比較のたびに私の渡した JS 関数を350万回呼んでいるから。 それでも採用してはいけません。 整列済みでは 6倍負け、4段階直してやっと落ちなくなった実装で、安定性は自分で保証、半年後に読めない
- 最悪ケースの保証が強いことと、実務で速いことは別。 ヒープソートは最悪でも O(n log n)・追加メモリなし・再帰なしなのに、標準では使われません。不安定で、CPUのキャッシュに乗らず、すでに並んでいるデータで速くならないからです
- 結論: ソートは自分で書かない。
sortに比較関数を渡す。 ただし「なぜ既に並んでいると速いのか(run の再利用)」と「なぜ同点の順が保たれるのか(仕様で安定・マージの取り方が<=)」は、説明できるようにしておく
参考リンク
- roadmap.sh — Computer Science — この記事が対応している本家のロードマップ
- MDN — Array.prototype.sort() — 比較関数を省いたときに文字列として並ぶことが、仕様として書かれています
- MDN — Array.prototype.toSorted() — 元の配列を壊さずに並べ替える方
- MDN — String.prototype.localeCompare() — 「多数の文字列を比較する場合は
Intl.Collatorを使うほうが性能が良い」と明記されています - MDN — Intl.Collator —
numericオプションもここにあります - V8 公式ブログ — Getting things sorted in V8 — V8 が TimSort を採用した経緯と、それまでのクイックソート実装の問題が書かれています
- tc39/ecma262 — Array.prototype.sort の仕様 — 安定であることが仕様に書かれている場所
- CPython — listsort.txt — TimSort の作者本人による設計メモ。run をどう見つけてどう統合するかが書かれています
- Node.js — performance.now() — この記事で時間を測るのに使った時計
次に読む
この記事は 【深掘り】コンピュータ科学 の 11 / 25 本目です。
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 6つ書いて同じデータで測る
- 安定性とクイックソートの最悪
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント