Days on the Moon

JavaScript の Array#sort は、比較関数を渡さない場合、各要素は文字列として比較され、並び替えられます。これに関して、IE などで用いられている JScript では、文字列化を一度しか行わず結果をキャッシュしている、すなわち内部的にシュワルツ変換 (Schwartzian transform) を行っているようで、配列要素の toString メソッドを適宜調整することによりソートを高速化できるというのが IT 戦記で触れられていました。

これはつまり、通常次のようにするところを、

// 比較関数
function C(order) {
  this.order = order;
}
array.sort(function (a, b) { return a.order - b.order; });

次のようにすると JScript で高速化が図れるというものです。

// toString
function C(order) {
  this.order = order;
  this._sortKey = String.fromCharCode(order);
}
C.prototype.toString = function () {
  return this._sortKey;
};
array.sort();

これをさらに高速化する手立てはないかと考えているうちに、toString メソッドを組み込みのものに変えるというのを思いつきました。ユーザ定義関数よりも組み込み関数のほうが速いのではという発想です。具体的には String オブジェクトを用いて以下のようにします。

// String オブジェクト
for (var i = 0, n = array.length; i < n; i++) {
  var s = new String(String.fromCharCode(array[i].order));
  s.value = array[i];
  array[i] = s;
}
array.sort();
for (var i = 0, n = array.length; i < n; i++)
  array[i] = array[i].value;

やっていることは典型的なシュワルツ変換ですね。実際に実行時間を計ってみると次のようになりました。

「String (全体)」は String オブジェクトを使ったソートで前後の処理も含め結果の配列を得るのにかかった時間、「String (ソート)」は sort メソッドのみにかかった時間です。Safari 3.0.3 Beta は結果が安定しなかったので外しました。

JScript の場合、String オブジェクトを使ったソートは、ソートにかかる時間こそ toString メソッドを使ったものより短いものの、全体的な処理時間はその 3 倍弱かかっています。ほかの実装では概して比較関数を使ったものが一番早くなるようです。

というわけで、String オブジェクトを使うことによるパフォーマンスの向上は期待できなさそうです。ちなみに JScript の場合、比較関数を使ったソートは安定なのに対し、toString メソッドを使ったソートは安定でないので、シュワルツ変換以外にも、文字列のソートに特化したソートアルゴリズムを使うなどして高速化を図っているのかもしれません。

参考

• LIMILIC - JavaScriptのソートを高速化するための戦略
• JScript および SpiderMonkey でのソート速度測定に用いた JavaScript ファイル