うめすこんぶ

日々のプログラミングで残しておきたいメモ.何かの役に立てれば幸いです.

再帰なしでマージソートやってみたら驚くほど高速化した話

スポンサーリンク

前回マージソートを書いてみましたが,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. 最初は隣り合った長さ1の配列同士をmarge
  2. 次は隣り合った長さ2の配列同士をmarge
  3. 最後に隣り合った長さ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;
}