ECMAScript 2019 から！
ついに！
Array.prototype.sort が安定ソートになったぞ！
でも全然話題になっていない気がする今日この頃。
せっかくなので Array.prototype.sort のおさらいをしつつ、安定ソートならワンチャン自前の不安定ソートのほうが速くね？ってことで追い抜いてみようかと思います。
Array.prototype.sort のおさらい
sort は、JavaScript の Array オブジェクトに生えているメソッドで、
破壊的に配列の要素をソートします。
console.log([1,2,3,4,5,6,7,8,9,10].sort());
これは当然ながら、こうなります。
[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]
他の言語から入ってきた人に割と「は？」と言ってもらえるので、話のネタに使えたり。
sort メソッドは、引数に比較関数を取りますが、省略した場合「文字列にして辞書順(正確には Unicode コードポイント順)」なので、こういう結果になります。
まあ、基本的には比較関数を常に指定するのが良いと思います。
比較関数は、比較対象の 2 引数を取り比較結果を数値で返す関数です。
目的の順序が、
- 一つ目 ➡ 二つ目 なら負
- 二つ目 ➡ 一つ目 なら正
- 同じなら 0
を返します。
ちなみに、数値じゃないものを返しても内部的に数値に変換してから比較されます。
また、NaN を返すと 0 扱いになります。
// 数値・文字列両対応昇順 (NaN 非対応)
const cmp = (x, y) => x < y ? -1 : x > y ? +1 : 0;
numArray.sort(cmp);
strArray.sort(cmp);
// NaN を含まない数値の場合
numArray.sort((x, y) => x - y); // 昇順
numArray.sort((x, y) => y - x); // 降順
// NaN を含む数値の場合 (昇順, NaN は後回し)
numArray.sort((x, y) => x - y || Number.isNaN(x) - Number.isNaN(y));
// オブジェクトならこんな感じ
const objArray = [{ age: 10 }, { age: 45 }, { age: 22 }];
objArray.sort((x, y) => x.age - y.age); // 年齢で昇順
// 破壊的なので、壊されるのが嫌ならコピーしてからソート
const sortedArray = unsortedArray.slice().sort((x, y) => x - y);
安定ソートになりました
さて、ソートには大別して、安定ソートと安定でないソート(不安定ソート)があります。
安定ソートとは何ぞや？と言う方は ➡ 安定ソート - Wikipedia
この sort メソッド、ES2018 までは安定ソートではありませんでした。
じゃあ不安定ソートか、と言うとそうでもありませんでした。
仕様上は、「必ずしも安定ソートでない」であり、要は実装依存だったわけです。
が、昨年仕様変更の提案があり、めでたく安定ソートに変更されました。
発起人は V8 チームの中の人みたいですね。
- ECMAScript® 2019 Language Specification - 22.1.3.27Array.prototype.sort ( comparefn )
- [Normative] Make Array.prototype.sort stable by mathiasbynens · Pull Request #1340 · tc39/ecma262
- Stable Array.prototype.sort · V8
実際問題として、安定ソートな環境で安定だと思い込んで書いたコードが他の環境で動かない、みたいなことは十分起こり得るわけですし、そもそも不安定ソートだとも言っていなかったので、きっちり指定されたのは良い変更であるように思います。
本題：自作不安定ソートの方が速い？
さて、汎用性と言う意味では、安定ソートへの変更は喜ばしくはあるのですが、別に安定である必要が無い場合パフォーマンス的にやや気がかりではあります。
処理系組み込みネイティブ実装とは言え、安定ソートは不安定ソートに比べてオーバーヘッドが大きくなりがちです。
加えて、比較関数は JavaScript 側の関数なわけで、ネイティブコードから JavaScript の関数を呼び出すのにも、それなりにコストがかかります。
最近の JavaScript は実行時にがっつり最適化される環境も多くなっているわけですし、もしかしたら不安定ソートで良いときは、自力でソート書いた方がパフォーマンス的に有利なのでは？
というわけで、実際試してみます。
実装
方針としては改変イントロソートで。
基本的にはクイックソートとして処理を進めつつ、末端部分では挿入ソートにします。
クイックソートのピボット選択に失敗しまくった時は、途中からヒープソートに切り替えます。
構成としては C++ STL のソートとだいたい同じですかね(たぶん)。
閾値の選択とかはかなり適当ですが。
const compareDefault = (x, y) => x < y ? -1 : x > y ? 1 : 0;
const heapSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
const n = j - i;
let k = 0;
while (++k < n) {
let c = k;
const cv = a[c + i];
while (c > 0) {
const p = ((c + 1) >> 1) - 1;
const pv = a[p + i];
if (cmp(pv, cv) >= 0) break;
a[c + i] = pv;
c = p;
}
a[c + i] = cv;
}
while (--k > 0) {
let p = 0;
const pv = a[k + i];
a[k + i] = a[i];
for (; ;) {
const cr = (p + 1) << 1;
const cl = cr - 1;
if (!(cl < k)) break;
const c = (cr >= k || cmp(a[cl + i], a[cr + i]) >= 0) ? cl : cr;
const cv = a[c + i];
if (cmp(pv, cv) >= 0) break;
a[p + i] = cv;
p = c;
}
a[p + i] = pv;
}
return a;
};
const insertionSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
for (let p = i + 1; p < j; p++) {
const v = a[p];
let q = p, r = p - 1;
if (cmp(v, a[i]) < 0)
for (; i < q; q = r--) a[q] = a[r];
else
for (; cmp(v, a[r]) < 0; q = r--) a[q] = a[r];
a[q] = v;
}
return a;
};
const med3 = (x, y, z, cmp) =>
cmp(x, y) < 0 ?
cmp(y, z) < 0 ? y : cmp(z, x) < 0 ? x : z :
cmp(z, y) < 0 ? y : cmp(x, z) < 0 ? x : z;
const ilog2 = n => {
let d = 0;
for (; n > 1; n >>>= 1) d++;
return d;
};
const INTRO_MIN = 32;
const introSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
const sub = (a, i, j, cmp, depth) => {
if (j - i < INTRO_MIN) return insertionSort(a, cmp, i, j);
if (depth-- <= 0) return heapSort(a, cmp, i, j);
let p = i, q = j - 1;
const pivot = med3(a[p], a[p + ((q - p) >> 1)], a[q], cmp);
for (; ; p++ , q--) {
while (cmp(a[p], pivot) < 0) p++;
while (cmp(pivot, a[q]) < 0) q--;
if (p >= q) break;
const t = a[p];
a[p] = a[q];
a[q] = t;
}
sub(a, i, p, cmp, depth);
sub(a, q + 1, j, cmp, depth);
return a;
};
return sub(a, i, j, cmp, 2 * ilog2(j - i));
};
// 参考までに普通のクイックソート
const quickSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
if (i < j) {
let p = i, q = j - 1;
const pivot = med3(a[p], a[p + ((q - p) >> 1)], a[q], cmp);
for (; ; p++ , q--) {
while (cmp(a[p], pivot) < 0) p++;
while (cmp(pivot, a[q]) < 0) q--;
if (p >= q) break;
const t = a[p];
a[p] = a[q];
a[q] = t;
}
quickSort(a, cmp, i, p);
quickSort(a, cmp, q + 1, j);
}
return a;
};
実測
条件: 10 万件のオブジェクトからなる配列を 5 個作ってそれぞれソート。
動作チェックは Windows 10 上の Chrome, Firefox, Edge (と、おまけで iPhone6 - Mobile Safari) で行いました。
const genRandomArray = length =>
Array.from({ length }, _ => ({
value: ~~(Math.random() * length)
}));
const comparator = (a, b) => a.value - b.value;
const size = 100000;
const count = 5;
const arrays = Array.from({length:count}, () => genRandomArray(size));
// 測定ここから
for (let array of arrays) {
/* sort array */
}
// ここまで
結果: Native stable sort vs self‐making unstable sort · jsPerf
最適化のかかり具合とか、件数変えて試したい場合は github.io の方をどうぞ。jsPerf と違い、こちらは一回ずつ、並びが同じ配列同士で比較します。
ブラウザに依ってばらつきますが、手元の環境では予想通り自作ソートの方が基本的に速くなりました。
あまり測定に時間をかけてもなあと言うことで、jsPerf の方はある程度控えめな数字にしましたが、件数増やしたり回数増やしたりすると、もう少し差が開きます。
逆に件数回数を減らすと、実行時最適化の効果が現れる前に測定が終わってしまうので、Array.prototype.sort の方が良い結果になります。
手なりで書いたコードでこんな感じなので、ちゃんとパフォーマンス考えて詰めていけば、もっと有利になるかもですね。
さて、皆様の環境ではいかがでしたでしょうか。
余談1: TypedArray.prototype.sort
Array.prototype.sort の影響を受けて、TypedArray.prototype.sort も安定ソートに変更になっています。
-
ECMAScript® 2019 Language Specification - 22.2.3.26%TypedArray%.prototype.sort ( comparefn )
- 直接は書かれていませんが、
Array.prototype.sortと同じ挙動を要求しています。
- 直接は書かれていませんが、
- [Normative] Make %TypedArray%.prototype.sort stable by mathiasbynens · Pull Request #1433 · tc39/ecma262
「プリミティブの数値なら安定でも不安定でも結果変わらなくない？」と思われるかもしれませんが、比較関数の呼び出しパターンが違ってくるので、ちゃんと安定ソートじゃないとダメだよ、と言う話になっています。
でもちょっと速度測ってみると、比較関数無しの時は各実装内部的にこっそり不安定ソートを使ってるっぽい？
ちなみに、TypedArray の sort を比較関数無しで呼んだ場合は、文字列辞書順ではなく数値昇順です。
余談2: CodePen には向かない
せっかく Qiita に CodePen 埋め込めるんだから CodePen で……と思っていたんですがダメでした。
CodePen は無限ループ回避のために各ループにチェックコードを勝手に挟むので、まともな比較になりません。
まあ、ソートに限った話ではないのですが、パフォーマンスチェックには向きませんね。
まとめ
- ES2019 から
Array.prototype.sortは安定ソート。 - ES2018 までは、安定ソートでないかも知れないので気を付けよう。
- 安定ソートである必要がないなら、件数が多くパフォーマンスが気になる部分は自力でソート書いた方が速いケースもあるかも。