Table Sorting

HTML の table の行を、列の内容でソートする関数を作ろう。

試作１

最初に作ったのは、こんな関数だった。原理的には、 HTMLCollection に直接 sort 関数をあてることができないので、各行 (tr 要素) を配列 x に格納して x をソートし、それを順に戻すと言うもの。

var compareIndex = 0;
function sortRows ( section ) {
  var x=new Array;
  for(var i=0; i<section.rows.length; i++) x[i] = section.rows[i];
  x.sort( compareFunc );
  for( i=0; i<section.rows.length; i++)
    section.insertBefore(x[i], section.rows[i]);
}
function compareFunc (a, b) { 
  var a_ = a.cells[compareIndex].firstChild.nodeValue;
  var b_ = b.cells[compareIndex].firstChild.nodeValue;
  return a_ < b_ ? -1 : a_ != b_;
}

// 呼び出し例; 文書内の最初の tbody を列 2 でソート
compareIndex=2; sortRows( document.getElementsByTagName('tbody')[0] );

これはちょっと宜しくない。なんせ比較関数に列番号を渡せないもんで compareIndex をグローバル変数にして使っている。そして比較関数の中の処理が若干重いようで、これがちょっと行数の多い表になると半端じゃない時間がかかる。特に Mozilla で、行が 100 を超えるあたりから処理時間が目立ち始め、特にソート済みのデータに対する処理が重い。 IE はソート処理はそこそこ高速な模様。だけどレンダリング効率が悪いようで、行数が増えると理不尽に処理時間がかかるようになる。 テストケース１

試作２

以上を踏まえて、作り直す。修正内容としては、比較関数内で引数から実際に比較する値を取得するまでの経路を短くするために、配列 x の各要素の値を行要素からセル要素に変更した。 insertBefore で配列から表に書き戻す時も、セルの parentNode で列を取得できるので問題ない。結果として比較対象の列インデックスを引数で受け取れる用になった。また今回はソート中にソート対象やその長さが変わるようなことはないので、あらかじめ変数に取得しておくことにした。

function sortRows2 ( section, index ) {
  var x=new Array, rows=section.rows, N=rows.length;
  for(var i=0; i<N; i++) x[i] = rows[i].cells[index];
  x.sort( compareFunc2 );
  for( i=0; i<N; i++) section.insertBefore(x[i].parentNode, rows[i]);
}
function compareFunc2 (a, b) { 
  var a_ = a.firstChild.nodeValue;
  var b_ = b.firstChild.nodeValue;
  return a_ < b_ ? -1 : a_ != b_;
}

// 呼び出し例; 文書内の最初の tbody を列 2 でソート
sortRows2( document.getElementsByTagName('tbody')[0], 2 );

試作１と比較して、 IE で 90-85%, Mozilla で 70-60% まで処理時間を短縮できた。些細なことだけれども、こういうことでこれだけの効果が望める。 テストケース２

試作３

試作３では配列にセル (td, th 要素) を格納した。なぜ直接比較する値である firstChild.nodeValue でないのかというと、理由は 2 つある。まずソート後の配列をテーブルに反映させる時に、文字列からはこれが含まれていた tr 要素を参照できないこと、そしてそのような関数では firstChild がテキストでなく要素であるようなケースに対応できず、汎用性にかけるということ、この 2 点だ。

この 2 点を解決しようと試作３では試みた。セルから比較対照の値を抜き出す部分だけを外部関数化してカスタマイズしやすくし、その戻り値をオブジェクト型に型変換してプロパティに tr 要素を持たせるようにした。これによって比較関数を用意しなくてもいいようになった。

function sortRows3 ( section, index ) {
  var x=new Array, rows=section.rows, N=rows.length;
  for(var i=0; i<N; i++)
    x[i] = Object( getDataFunc3( rows[i].cells[index] ) ), x[i].row=rows[i];
  x.sort();
  for( i=0; i<N; i++) section.insertBefore(x[i].row, rows[i]);
}
function getDataFunc3 ( cell ) {
  return cell.firstChild.nodeValue;
}

// 呼び出し例; 文書内の最初の tbody を列 2 でソート
sortRows3( document.getElementsByTagName('tbody')[0], 2 );

Mozilla の処理時間はさらに半分、試作１と比較して 30% 程度になった。ソート済みの配列を同じソートをかけた時の問題もなくなった。 IE の処理時間は試作１の 60-70% 程度。 テストケース３

試作４

試作３までの改良で、大分処理速度は向上した。あとは使い勝手の部分だ。現在のところ次のような問題が残っている:

• セルから比較対照データを取得する関数の名前が決め打ち。
• 例えば降順にソートしたいときなどに、 sort 関数に比較関数を指定できない。

というわけで、これを解決してみたい。データ取得関数、比較関数ともに、引数で指定するかこの関数のプロパティに設定するかのどちらかだと思う。

function sortRows4 ( section, index, cmpfn, getfn ) {
  var x=new Array, rows=section.rows, N=rows.length;
  cmpfn = cmpfn || arguments.callee.compareFunc;
  getfn = getfn || arguments.callee.getFunc
                || function(cell){return cell.nodeName;};
  for(var i=0; i<N; i++)
    x[i] = Object( getfn( rows[i].cells[index] ) ), x[i].row=rows[i];
  if ( cmpfn ) x.sort( cmpfn ); else x.sort();
  for( i=0; i<N; i++) section.insertBefore(x[i].row, rows[i]);
}
// データ取得関数
function getDataFunc4 ( cell ) {
  return cell.firstChild.nodeValue;
}
// 降順ソート用比較関数
function compareFunc4 ( a, b ) {
  return a > b ? -1 : a != b;
}

// 呼び出し例: 文書内の最初の tbody を列 2 でソート
sortRows4( document.getElementsByTagName('tbody')[0], 2, undefined, getDataFunc4 );

// 比較関数を指定した呼び出し例: 降順ソート
sortRows4( document.getElementsByTagName('tbody')[0], 2, compareFunc4, getDataFunc4 );

// データ取得関数のデフォルトを getDataFunc4 に設定する例;
sortRows4.getFunc = getDataFunc4;
// 上は次のようにも記述できる:
sortRows4.getFunc = function ( cell ) { return cell.firstChild.nodeValue; }

// 比較関数を compareFunc4 に設定する例;
sortRows4.compareFunc = compareFunc4;
// 上は次のようにも記述できる:
sortRows4.compareFunc4 = function ( a, b ) { return a_ > b_ ? -1 : a_ != b_; }

// 以上の指定があれば、次の記述で sortRows4.getFunc, sortRows4.compareFunc が
// デフォルトで使用される
sortRows4( document.getElementsByTagName('tbody')[0], 2 );

テストケース４, テストケース４(降順ソート)

試作５

ここまでの結果から、次のようなことを推測してみた。

• Mozilla は DOM ノードを辿るのが遅い。この回数を減らす、または経路を短くすると処理効率が上がる。
• IE はレンダリングが遅い。特に断続的に画面再描画を行うと、飛躍的にパフォーマンスが悪くなる。

試作１－４までで行った改良は、主に Mozilla 向けの改良、つまり実際のソート処理の改良だった。できれば IE 向けの改良、レンダリング面の改良も行いたいと思う。問題は for 文で並べ替えているため、どうしても行数分だけ再描画が発生することである。

ここで一つ思いついた。一度ソート対象の tbody 要素を文書ツリーから削除して、バックグラウンドで再構築した後に書き戻したらどうだろう？ これなら画面の書替えは 2 回しか発生しない。 テストケース５

function sortRows5 ( section, index, cmpfn, getfn ) {
  var x=new Array, rows=section.rows, N=rows.length;
  var marker = document.createElement('tbody');
  cmpfn = cmpfn || arguments.callee.compareFunc;
  getfn = getfn || arguments.callee.getFunc
                || function(cell){return cell.nodeName;};
  for(var i=0; i<N; i++)
    x[i] = Object( getfn( rows[i].cells[index] ) ), x[i].row=rows[i];
  if ( cmpfn ) x.sort( cmpfn ); else x.sort();
  section.parentNode.replaceChild( marker, section );
  for (var i=0; i<N; i++ ) section.appendChild(x[i].row);
  marker.parentNode.replaceChild( section, marker );
}

問題が出るのは行数が多い場合なので、ここでは 200 行と 400 行の場合だけ実験結果を示す。

以上の結果、試作１から処理時間を元の 20-30% 程度にまで抑えることができた。

テストケースについて

各テストケースは、上記の関数に処理時間を計測する目的でいくつか式を追加している。具体的には、次の式を追加している。

function sortRows ( section ) {
  var t0=new Date; // 関数開始時刻
  ... // 
  var t1=new Date; // ソート開始時刻
  ... // ソート関数呼び出し
  var t2=new Date; // ソート終了/レンダリング開始時刻
  ... // レンダリング処理
  return([t1-t0, t2-t1, new Date-t2]); // 処理終了時刻
}

各実験結果は、ランダムに作成した表に対してソート処理を10回ずつ行い、平均処理時間(ミリ秒)を行数で割った値を比較した。

もちろん、この実験で計測できるのは JavaScript コードの処理時間でしかないので、特にレンダリングについては実際の描画がこのとおりであるとは必ずしも言えない。

この実験は以下の環境で行った。

• Windows 2000 SP2
• Internet Explore 6.0 / Mozilla 0.9.8
• AMD Duron 800MHz
• RAM 448MB