再帰なしでマージソートやってみたら驚くほど高速化した話
スポンサーリンク
前回もマージソートを書いてみましたが,javascriptで再帰関数を使うと, 関数のコールによる時間がかかるため,結果として遅くなってしまうのではないかと考えました. 今回は再帰関数ではなく,ループだけでマージソートを作ってみます. 結果として,ループにしたら,2倍近く高速化されました.(Chromeで検証)
考え方
ループなしのマージソートは, 一言で言えば,最初の分割の過程をすっ飛ばして,いきなり併合から始める形式にしてます.
例えば,こんな配列をソートしたいとします.
[6, 4, 5, 3]
通常のマージソートですと,まず配列を2つに分けて,それからまたそれぞれを2つに分けて,… というのを繰り返します.
ちなみに,再帰の書き方であれば,配列xに対して,
function sort() { return marge(sort(xの左半分の配列), sort(xの右半分の配列)) }
と書きます.marge()
の中で,sort()
を再び呼び出しているので,再帰ですね.
それで,結局できるところまで分割すると,最終的には,以下のように配列が分割されています.
[6] [4] [5] [3]
次は,併合の段階です.6と4を併合(marge()メソッドを使用
),5と3を併合とやって,
2つの配列にまとめます.
[4,6] [3, 5]
そして,同じようにこの2つの配列をmarge()
を使って一つに併合して,ソート完了.
[3, 4, 5, 6]
さて,この併合の過程をループだけで表してみます.
- 最初は隣り合った長さ1の配列同士をmarge
- 次は隣り合った長さ2の配列同士をmarge
- 最後に隣り合った長さ4の配列同士をmarge
この長さの部分は1, 2, 4と上がっていくので,こいつをループにしてやります. 注意:xはソートしたい配列です.
for (var k = 1; k < x.length; k *= 2) { // 併合処理 }
このループの中の併合処理の部分はどうなるでしょうか.
例えば,最初の
[6] [4] [5] [3]
を併合する場合,配列x上の位置から考えれば,こんな処理ですね.
配列xの0番目と1番目をmarge, 2番目と3番目をmarge
次に,
[4,6] [3, 5]
という段階なら,
配列xの0番目から1番目の部分配列と2番目と3番目の部分配列をmarge
となります.
もう少し抽象化すると,ループ中で,
配列xのi1番目からi2番目の部分配列とj1番目とj2番目の部分配列をmarge
という処理をして,ループのインデックスをj2の一つ後ろにして,同じようにmarge
を行う,というのを繰り返すことで実現できます.
言葉で言ったら,なんだかすごく説明しにくいです….
コードはこんなふうになります.
for (var k = 1, lk = x.length; k < lk; k *= 2) { // k = 1, 2, 4, 8..とかえる. // 1個同士のマージを全部やって,次に2こ同士のマージというように… for (var i = 0, li = x.length; i < li; i += k * 2) { // 配列xの i ~ i + k 未満の部分配列と i + k ~ i + 2 * k 未満の部分配列をマージ marge(i, i + k, i + k, i + 2 * k); } }
marge()の処理など,実際の処理は次のソースを参照ください. チューニングでかなり手を加えているのでわかりにくいです.
ソース
function margeSort4(x) { function marge(i1, i2, j1, j2) { if (i1 >= x.length || i2 >= x.length) return; //配列の片方がないので計算不要 else if (j2 >= x.length) j2 = x.length; // 配列jの長さは減る var li = i2 - i1; // 1番目の配列の長さ var lj = j2 - j1; // 2番めの配列の長さ if (li === 0 || lj === 0) return; var a = new Array(li + lj), i = 0, j = 0, k = 0; // new Array(n)で少しだけ高速? while(i < li && j < lj) { // a に要素を小さい順に入れる処理 if (x[i1 + i] < x[j1 + j]) { a[k++] = x[i1 + i]; i++; } else { a[k++] = x[j1 + j]; j++; } } if (i >= li) { // 比較が終わって,あまった要素をすべてaに入れる for (var l = 0, la = j2 - j1 - j; l < la; l++) { a[k + l] = x[j1 + j + l]; } } else { for (var l = 0, la = i2 - i1 - i; l < la; l++) { a[k + l] = x[i1 + i + l]; } } // xのi1からj2-1の部分にaを入れる for (var i = 0, l = a.length; i < l; i++) { x[i1 + i] = a[i]; } } for (var k = 1, lk = x.length; k < lk; k *= 2) { // 1, 2, 4, 8.. の部分配列ごとに for (var i = 0, li = x.length; i < li; i += k * 2) { marge(i, i + k, i + k, i + 2 * k); } } return x; }