LIMILIC

ソート雑感

単純な文字列のソートには興味がない。

そんなのでパフォーマンスを気にするケースはほとんどないので。

問題はハッシュの配列のソートを行うケース。（比較関数を渡さないといけない）

低スペックPCでは、巨大な配列のソートに時間がかかりすぎる。

livedoor Readerの実際に使っているsubscriptionを利用して調査してみる。

http://pics.livedoor.com/u/mala__/3174836

• Array#sortは比較関数を渡さない場合、toStringで文字列化した状態で比較される。
• IE6,7共に配列の長さ分だけしかtoStringが呼ばれないことがわかる。
• 内部でschwarzian transformが行われていることが推察できる。
• Opera9.5は独特、バグってる？
  • 値がばらけていないと比較関数が大量に呼び出されるようだ。
• Safariのソートは他のブラウザより呼び出し回数が少なくなるようにチューニングされているようだ。

戦略

• とにかく関数呼び出しが最小になるようにすればいい
• cmp関数を渡さないでtoStringの呼び出し回数を減らす → IEでのみ取れる戦略
• cmp関数の呼び出し回数を減らす → 自前でソートアルゴリズムを書く。

IEに特化したソートの高速化

• 比較関数を渡さないソート→toStringの結果でソートして望んだ結果になるようにtoStringを書き換えるのはどうか？
• 配列の要素が任意のクラスに属している場合は、任意のクラスのtoStringをカスタマイズすればよい。
• 単純ハッシュの場合は、Object.prototype.toStringが使われる。
• 便宜上 custom object sortとobject hack sortと呼ぶことにする。

custom object sort

• 配列の要素をそれぞれ任意のクラスのインスタンスに変換する。
• 任意のクラス.prototype.toStringを書き換えて、ソートが終わったら元に戻す。
• アプリケーションに依存、データ構造を知っている必要がある
  • アプリケーション内で使う場合、任意のクラスに便利なメソッドを追加することができる。設計がすっきりする。
  • ハッシュから変換コストがかかる

ハッシュからオブジェクトへの変換コスト

配列の件数が多い場合は、コンストラクタの書き方によって速度に大きな差が出る。

for文ですべてのキーをコピーする。

convert to object 851 ms

あらかじめコピーするキーを決めておく。

convert to object2 250 ms

いずれもIE6、3000件の場合。配列の初期化、JSON受信時にこういう変換を行っておくといいだろう。件数の割には許容できる速度。

メソッドを生やせるメリットができる。他のブラウザだとそんなに差が出ない。十分早い。

object hack sort

• ハッシュはそのままでObject.prototype.toStringを書き換えてソートする
• かなり強引な方法、ハックしたtoStringにObject#toStringを必要とする処理が入っていたら無限ループになるのでエラー。

ソートの速度

livedoor Readerのsubsのダミーデータ。レートが0-5、レートでソートする。

3000件のダミーデータをソートした結果、事前にシャッフルして、1回。

normal sortはこんなの。

subs.sort(function(a,b){return a.rate - b.rate})

IE6の場合

normal sort 1432 ms

bucket sort 30 ms

quick sort 1052 ms

marge sort 902 ms

object hack sort 120 ms

custom object sort 111 ms

IE7の場合

normal sort 260 ms

bucket sort 20 ms

quick sort 231 ms

marge sort 231 ms

object hack sort 40 ms

custom object sort 30 ms

Safari2の場合

normal sort 30 ms

bucket sort 14 ms

quick sort 698 ms

marge sort 495 ms

object hack sort 39 ms

custom object sort 31 ms

Firefox2の場合

normal sort 240 ms

bucket sort 10 ms

quick sort 251 ms

marge sort 211 ms

object hack sort 400 ms

custom object sort 251 ms

Opera9

normal sort 81 ms

bucket sort 12 ms

quick sort 153 ms

marge sort 168 ms

object hack sort 158 ms

custom object sort 159 ms

ベンチ環境はCore Duo 2GHzのMacBookとParallels。

感想

• IE6で1秒以上待たされるのは致命的。改善したい。
• データ構造にあわせた最適化→バケツソート→一番早い
• 数値データということしか知らない→比較関数書く、normal sort, marge sort, quick sort
• toStringハックしてソート → IEで効果大、扱いづらいが。
• ソートアルゴリズム自前で書く意味
  • 場合によってはあるぽい。ただし微々たるもの。
  • 普通に書いても大差ない。比較関数の呼び出しをなるべく減らすように書かないと意味がなさげ。