|
2010-1-11[月] 安定ソートについてのメモ(sort test その5)しつこくソートネタ．遣り残してた、というか、自分としては本題だった 安定ソート についてのメモ. 安定ソートだと、ソート対象の値が、同じ値だったときに元の順番を維持した状態でソートできる． 安定ソート としては 挿入ソート、 マージソート、 ビン(バケット)ソート、 基数ソート 、 バブルソート 等がある. アルゴリズムとかの詳しいことは wikipediaとか、 このへんとか、 適当に検索するなりして調べて.
今回のテストルーチンは、
マージ、
基数、
quick
(y)、
その他のソート、
テスト本体 で一組.
本題以外のソートも混ざってて、ごちゃごちゃしてるけれど、 本命は、マージソートと基数ソート． マージソートは
基数ソートは
(分割した処理ごとに範囲チェックをしてるので、入力が0～255ですめば1回+αの処理ですみバケットソートに近くなる)
実行結果とりあえず、その実行結果としては、 【phenom2 945 vista64 vc2008:32bit】 【phenom2 945 vista64 mingw】 【vaio-c1 win2k vc2008】 【玄箱HG debian4 gcc4.1.2】
いくつか抜粋してみると、(単位はμ秒） phenom2 945(vista64)+vc2008(32bit)で int 配列をソートした場合．
phenom2 945(vista64)+vc2008(32bit)で double 配列をソートした場合．
玄箱HG(PowerPC 266MHz)+gcc4.1.2で、int配列をソートした場合．
表のstd::stable_sortはコンパイラ付属のstlライブラリを使った場合． たぶんマージソート(with挿入ソート)がベースだろうと思うけれど(追記:実際はも少しいろいろやってるよう)、 実装の違いからか、ちょっと差が現れている模様． (vcのには勝ってるけど、gccのには量が多いと負ける) quick ソートは安定ソートではないけれど、実行速度の比較のために並べている． (※実行ログでは、quick(+挿入) になっているモノ) 基本的にマージソートはクィックソートより遅くなるが、 基数ソートは条件が揃えばクィックソートよりも速くなりえる． だいたい説明サイトの説明にあるとおりの状況、かな． （どの程度の性能差があるかを見てみたかったので今回のテスト） ただ、基数ソートは仕組み上、ソート値のビット数が多い(値の範囲が広い)場合、処理が重くなるので、 int(4bytes)だと飛びぬけて早いのに、double(8bytes)だと微妙な差になっている． また、phenom2(3GHz 2次cache 512KBx4 3次 6MB)環境だと、 テストで使ったデータ数やデータサイズ・CPU(キャッシュ容量)が 基数ソートに有利に働いた面もあるようで、 クィックソートよりも十分早くなれるが、 玄箱HG(PowerPC 266MHz cache:16+16KB)の場合は 1024個,10000個では速そうだけど、 それ以上ではクイックソートのほうが速くなっていて、 基数ソートが必ずしも速いというわけでない模様．
基数ソートは、個数が少ないときは、処理のオーバーヘッドが大きすぎて割にあわない． もっともクィックソートにしろマージソートにしろ、数が少ないときは実質、挿入ソートになっているので、 実際に基数ソートを使う場合も一定数以下はマージソートを使う、のようにするだろう． ただ、他の実行環境(CPU)やソート対象のサイズ等により、効果的な境界値が大きくばらけるので、 汎用的な決めうちは、やりにくい．
基数ソートは条件揃えば倍速以上になるとはいえ、 手間を思うと、よほどのことがないかぎり、 安定ソートはマージソート、 非安定ソートでよければクィックソート、 でいいかな、というのが結論．というか、普通を再確認しただけとも．
upper_boundを用いた vector への insert先の結果のvector insertの行は、vector<Hoge> hoge_vec; でデータを保持しているとき、
hoge_vec.insert(std::upper_bound(hoge_vec.begin(),hoge_vec.end(), val), val); のような感じに安定ソート状態を維持したまま新規の値 val を挿入するもの． テストルーチンでは、他のソートと関数仕様あわせたため、(実使用からすれば) 余分なアロケート時間やコピー時間が混ざっていて、 他のソートと比較するのにはフェアな状態ではない． が、回数に対する時間の増え方からすれば、効率はあまりよくないだろう． これを用いるメリットは、
といったところか． 作業メモリについては、挿入ソートも作業メモリ不要なので、追加回数しだい... どちらにしても、量が多いときの速度ペナルティが大きいので、数があるときは メモリの折り合いつけてマージソートとかを使うほうがよいだろうけど．
しかし、余分に作業メモリ(外部メモリ)が必要になる、というのは、
場合(ターゲット環境)によっては面倒かもしれない． なので、最大数わかってる場合に固定の作業メモリを与えられるマージソート・ルーチンがほしい、というのが、今回のテストルーチン作成の理由のひとつ（実際に使う機会があるかは別として) あと、後述のSmpClassの例からすると登録順番も保持し比較対象にすることでクィックソート(std::sort)を用いるというのも、動的アロケート回避、という意味では有りな選択かもしれない.
※ 基数ソートで、符号無し整数として比較を行っているけど、他のソートは
型どおりに行っている．
Class/Structのソート
テストルーチンで、SmpClass を使ったものについて．
[1] SmpClass1 [2] SmpClass2 [3] SmpClass3
8バイトの構造体. SmpClass3へのポインタ 128バイトの構造体.
class { (4バイト) class {
float key_; ※比較はSmpClass3の float key_;
unsigned no_; ものを使う unsigned no_;
}; unsigned rsv_[30];
};
のようなデータのソートを行ってみる.
class {
float key_;
Hoge* pHoge_;
};
のようなソートキーと実体へのポインタの組み合わせ、を想定している．
また、quickソートにおいて、登録順も比較対象にすることで[1]と同様の安定ソートを実現するため
[4] SmpClass4
12バイトの構造体
class {
flaot key_; // 比較対象
unsigned no_; // 比較対象
unsigned rsv_[1]; // Hoge* pHoge;のようなのを想定.
};
も用意． 10000個の場合 (単位:μ秒)
100000個の場合 (単位:μ秒)
のような感じ． [1]の場合はソート対象のコピー量は増えるけれど比較コストは増えない. [2]のようにポインタだけの場合はコピー量は最小になるけれど メモリにあるポインタを経由して比較用のキーにアクセスするため 比較時間(コスト)が増加する. で、CPUキャッシュ等の都合から、今時の環境だと[1]のほうが有利なことが多そう.
なので、[1]のようにできるならば、そうしたほうが構造体等のソートは
速くなると思われる.
で、どうせ、ソート用のテーブルを作るならば、登録順番も控えることで クィックソートを使えるようにするのも一考. ソート対象が8バイトから12バイトに増えるが、 マージソートや基数ソートは 余分に外部メモリを必要とするので、 メモリ使用量的には同等か有利ということになる. (マージソートだと総数の半分、基数ソートだと総数分) 今回の例では、基数ソートに対しては全くだけれど、マージソートと比べるとよい結果となっている． もっとも[4]はIEEEなfloatの正数であることを前提にキーと登録順を合わせた64bit整数にして 比較を軽くしているので、このように出来ず比較コストが上がると、また違う結果になるだろう．
バケット(ビン)ソート
基数ソート以上に利用条件厳しいけれど、条件があえばバケット(ビン)ソートのほうが当然速い．
で、一応、用意してみた(これ)
基数ソートのようにgetkeyを与えられるようにすればいいのだけれど、 ただ、基数ソート・ルーチンは、 入力の値がすべて0～255までなら1回+αで処理打ち切ることになりビンソートに近い状態になるので (多少オーバーヘッドが多いけれど)、 その結果をみれば大体の雰囲気はつかめると思う．
ということで、乱数の値を0～255にして試した結果は、コレ．
抜粋すると、
のような感じ．場合によっちゃ、やっぱりバケットソート専用も意味あるかな．
その他諸々
当然、それなりに測定誤差がある.
前回以降にCPUを換装してしまい、今回分と前回分を単純に比較できなくなってしまったので、
テストでは、安定ソートだけでなく、前回試した他のソートもいくつか試している.
前回のテストでは、quick_sortのtemplate版が内部でイテレータのアドレス比較してて
実質、配列のソートにしか対応してなかった． で、オフセット値を用いて修正してみると、
Bidi版と大差なくなってしまった．
厳密にはBidi版のほうがまだ1変数多くなるので、比較処理によっては差がありえるけど、
これくらいなら利便のほう優先して、今回のテストのquickソートは前回のBidi版をベースにした．
前回の結論に基づき、quickソート内部の挿入ソートを Bidirectional Iterator を
受け付ける形でやねう版にしてみたはいいけど、性能出なかった．
よくよく考えれば、
やねう版挿入ソートは、無駄な代入を減らせる可能性が高まる代わりに、比較回数が1回増えてる．
比較処理がコピーよりも十分にコストが安いことが前提なわけで、
比較のコストが高くなる場合は当然不利だ．
ただ、元のソースは、ループで1回無駄に比較をしている状態でもあるので、その1回分の比較を
回避することで改善した...が、ソースが結構酷い状態に.
基数ソートルーチンは、実は dmc でコンパイルすると int 版の結果が不正になってしまっていた． こちらのバグかもしれないけれど、深く追求せず． 他にも玄箱でTYPE_SMPCLASS=4でコンパイルするといくつかのソートで実行結果が不正になるが、これも放置. このテストのクィックソート等再帰を用いた処理は当たり所が悪いとスタック溢れがあるよう. (乱数を0～255にしたら駄目なモノがあった... 個数減らして回避. 追記:下記に修正版) open watcom c++ (v1.8)の場合、std::stable_sort, std::upper_bound が未実装だった. 辻褄あわせして通したけれど、他にもテンプレートの特殊化ができなかったり、と、 まだ使うにはつらい感じ． 今回linux環境で使ったタイマーはwinに比べての精度がよくなさそう(4ミリ秒単位くらい?)． ただ、他のプロセスの時間を含まない値なので、そういう面では楽かも．
追記
実際のstl(stlport)のものをみると std::sortやstd::stable_sortはも少しいろいろ工夫してるよう.
(std::sortは、イントロソート等工夫してるらしく)
このテストのquick sort は、中間値のコピーをローカル変数にとるため値のサイズが大きいと再帰中のスタック消費がはげしくなってしまっていた.
|