差分表示


*&date(Y-n-j[lL],2010/1/11); 安定ソートについてのメモ(sort test その5)

しつこくソートネタ.遣り残してた、というか、自分としては本題だった
[[安定ソート>http://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E3%82%BD%E3%83%BC%E3%83%88]] についてのメモ.

安定ソートだと、ソート対象の値が、同じ値だったときに元の順番を維持した状態でソートできる.

[[安定ソート>http://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E3%82%BD%E3%83%BC%E3%83%88]]
としては 
[[挿入ソート>http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88]]、
[[マージソート>http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88]]、
[[ビン(バケット)ソート>http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88]]、
[[基数ソート>http://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88]] 、
[[バブルソート>http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88]]
等がある.
アルゴリズムとかの詳しいことは
[[wikipedia>http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88]]とか、
[[このへん>http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/]]とか、
適当に検索するなりして調べて.


今回のテストルーチンは、
[[マージ>http://www.6809.net/tenk/html/prog/sort5/merge_sort.h.htm]]、
[[基数>http://www.6809.net/tenk/html/prog/sort5/radix_sort.h.htm]]、
[[quick>http://www.6809.net/tenk/html/prog/sort5/quick_sort.h.htm]]
[[(y)>http://www.6809.net/tenk/html/prog/sort5/quick_sort_y.h.htm]]、
[[その他のソート>http://www.6809.net/tenk/html/prog/sort5/sort_etc.h.htm]]、
[[テスト本体>http://www.6809.net/tenk/html/prog/sort5/sort_test5.cpp.htm]] で一組.
~
[[[ソース,exe,実行結果ログのzip>http://www.6809.net/tenk/html/prog/sort5/sort_test5.zip]]]

本題以外のソートも混ざってて、ごちゃごちゃしてるけれど、
本命は、マージソートと基数ソート.

マージソートは
- 最内側(一定個数以下)のソートとして挿入ソートを使っている.
- おそらく、汎用的な安定ソートルーチン(std::stable_sortとか)だと、
数が少ないときは挿入ソート、多くなればマージソート、って感じだと思う.
- データの個数の半分のサイズの作業メモリ(外部メモリ)が余分に必要になる.

基数ソートは
- 速いけれど、使える局面が限られる.~
ソートキーを(符号無)整数値に変換できないといけない.~
今回のテストは基数ソートしやすいテストデータにしている.
- 比較を単純化するため、テストデータは、負数無し(0と正数)にしている.
- このテストルーチンでは基数ソートの基数は8bit(0~255)で扱っている.~
なので、
int(4bytes)だと4分割して4回処理することになるし、
double(8bytes)だと8分割して8回処理することになる.~
(分割した処理ごとに範囲チェックをしてるので、入力が0~255ですめば1回+αの処理ですみバケットソートに近くなる)
- 浮動小数点数データについては、今時の一般的なIEEE な仕様であることを前提に、
ビットイメージをそのまま符号無整数値として扱っている.
//(たぶん、比較処理側で負数対応するよりも、比較キー生成時に正数化しておくがコストは安いだろう.
//もともと負数のないようなデータか、単純な下駄はかせをすればすむようなデータの場合に使える、
//と思っておけばいいのかも).
- データの個数分の作業メモリ(外部メモリ)が余分に必要になる.

~
**** 実行結果

とりあえず、その実行結果としては、

 [[【phenom2 945 vista64 vc2008:32bit】>http://www.6809.net/tenk/html/prog/sort5/sort_test5_phenom2_945.log]]
 [[【phenom2 945 vista64 mingw】>http://www.6809.net/tenk/html/prog/sort5/sort_test5_phenom2_945_mingw440.log]]
 [[【vaio-c1 win2k vc2008】>http://www.6809.net/tenk/html/prog/sort5/sort_test5_vaio_c1.log]]
 [[【玄箱HG debian4 gcc4.1.2】>http://www.6809.net/tenk/html/prog/sort5/sort_test5_kuroboxhg.log]]
>(※他のコンパイラでの結果等は[[zip>http://www.6809.net/tenk/html/prog/sort5/sort_test5.zip]]に同根)

いくつか抜粋してみると、(単位はμ秒)

phenom2 945(vista64)+vc2008(32bit)で int 配列をソートした場合.

,              個数 ,       100個,      1024個,     10000個,    100000個,   1000000個,  10000000個
,  回数(結果は平均) ,   ( 1000回),   (   98回),   (   10回),   (    1回),   (    1回),   (    1回)
,バブル SORT        ,      12.440,    1557.466,  150125.770,15098726.584,         ---,         ---
,挿入 SORT          ,       3.148,     267.288,   24947.270, 2500147.295,         ---,         ---
,vector insert      ,       9.242,     192.069,    9526.099, 1133735.433,         ---,         ---
,std::stable_sort   ,       3.483,      52.740,     739.982,    9859.912,  119201.882, 1492833.656
,マージ SORT        ,       2.403,      42.339,     564.813,    7241.423,   91783.523, 1102430.407
,基数 SORT          ,       5.778,      34.457,     312.889,    3309.778,   37145.294,  406029.607
,QUICK SORT(非安定) ,       2.104,      33.574,     439.805,    5471.645,   66066.008,  794235.790


phenom2 945(vista64)+vc2008(32bit)で double 配列をソートした場合.

,              個数 ,       100個,      1024個,     10000個,    100000個,   1000000個,  10000000個
,  回数(結果は平均) ,   ( 1000回),   (   98回),   (   10回),   (    1回),   (    1回),   (    1回)
,マージ SORT        ,       3.780,      64.883,     865.578,   11134.446,  141526.018, 1726543.597
,基数 SORT          ,      14.116,      90.035,     841.427,    8860.623,  106789.969, 1096515.828
,QUICK SORT(非安定) ,       3.685,      57.659,     750.542,    9295.246,  113065.837, 1363336.262


玄箱HG(PowerPC 266MHz)+gcc4.1.2で、int配列をソートした場合.

,              個数 ,       100個,      1024個,     10000個,    100000個,   1000000個
,マージ SORT        ,      36.000,     448.980,    7600.000,   96000.000, 1344000.000
,基数 SORT          ,      68.000,     285.714,    4400.000,   72000.000, 1024000.000
,QUICK SORT(非安定) ,      28.000,     367.347,    5600.000,   64000.000,  836000.000

~

表のstd::stable_sortはコンパイラ付属のstlライブラリを使った場合.
たぶんマージソート(with挿入ソート)がベースだろうと思うけれど、実装の違いからか、ちょっと差が現れている模様.
(vcのには勝ってるけど、gccのには負けてる)
(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)やソート対象のサイズ等により、効果的な境界値が大きくばらけるので、
汎用的な決めうちは、やりにくい.
//(100個もないなら基数ソート使うまでもなく... 
//このテストの場合、8ビット単位で処理しているせいか、256付近以降の数になりそう.
//それが256なのか1000なのか10000なのかは、状況によりけりで)


基数ソートは条件揃えば倍速以上になるとはいえ、
手間を思うと、よほどのことがないかぎり、
安定ソートはマージソート、
非安定ソートでよければクィックソート、
でいいかな、というのが結論.というか、普通を再確認しただけとも.


~

**** 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 を挿入するもの.

テストルーチンでは、他のソートと関数仕様あわせたため、(実使用からすれば)
余分なアロケート時間やコピー時間が混ざっていて、
他のソートと比較するのにはフェアな状態ではない.

が、回数に対する時間の増え方からすれば、効率はあまりよくないだろう.

これを用いるメリットは、
- データ追加の機会がまばらにあって、かつ、絶えず整列状態を維持しないといけないとき
- 余分な作業メモリ(外部メモリ)を必要としない

といったところか.

作業メモリについては、挿入ソートも作業メモリ不要なので、追加回数しだい...
どちらにしても、量が多いときの速度ペナルティが大きいので、数があるときは
メモリの折り合いつけてマージソートとかを使うほうがよいだろうけど.

~

しかし、余分に作業メモリ(外部メモリ)が必要になる、というのは、
場合(ターゲット環境)によっては面倒かもしれない.~
というか、std::stable_sort で勝手にアロケータを使われること、
が環境によってはつらかった.

なので、最大数わかってる場合に固定の作業メモリを与えられるマージソート・ルーチンがほしい、というのが、今回のテストルーチン作成の理由のひとつ(実際に使う機会があるかは別として)

あと、後述のSmpClassの例からすると登録順番も保持し比較対象にすることでクィックソート(std::sort)を用いるというのも、動的アロケート回避、という意味では有りな選択かもしれない.


~

※ 基数ソートで、符号無し整数として比較を行っているけど、他のソートは
型どおりに行っている.~
当然、条件を満たした状態だから、他のソートでも符号無し整数で比較することは可能なので、
そのように比較すれば、他のソートもも少し早くなるはず.
(面倒だからやりなおさないけど)



*** Class/Structのソート

テストルーチンで、SmpClass を使ったものについて.~
([[前回:雑記/2009-12-15]]のスマートポインタのソートの補足というか書き漏れ)

 [1] SmpClass1           [2] SmpClass2          [3] SmpClass3
 8バイトの構造体.        SmpClass3へのポインタ  128バイトの構造体.
 class {                 (4バイト)              class {
     float    key_;      ※比較はSmpClass3の        float    key_;
     unsigned no_;         ものを使う               unsigned no_;
 };                                                 unsigned rsv_[30];
                                                };

のようなデータのソートを行ってみる.~
[1]については、テストの都合unsigned no_ になっているが
 class {
     float  key_;
     Hoge*  pHoge_;
 };

のようなソートキーと実体へのポインタの組み合わせ、を想定している.
~
(面倒なので話を32bit環境に限定)

また、quickソートにおいて、登録順も比較対象にすることで[1]と同様の安定ソートを実現するため
 [4] SmpClass4
 12バイトの構造体
 class {
     flaot    key_;     // 比較対象
     unsigned no_;      // 比較対象
     unsigned rsv_[1];  // Hoge* pHoge;のようなのを想定.
 };

も用意.~
これらのデータをソートした結果は(phenom2 945 vc2008環境)

10000個の場合 (単位:μ秒)
,                   , [1](8bytes),[2](ポインタ),[3](128bytes), [4](12bytes)
,マージ SORT        ,    1188.489,     1362.142,   13398.148, ---
,基数 SORT          ,     364.076,     2304.525,    6199.210, ---
,QUICK SORT         ,     893.445,     1171.867,    6468.636, 954.360

100000個の場合 (単位:μ秒)
,                   , [1](8bytes),[2](ポインタ),[3](128bytes), [4](12bytes)
,マージ SORT        ,   15242.091,    24420.003,  179135.267, ---
,基数 SORT          ,    4175.601,    47205.162,  107197.703, ---
,QUICK SORT         ,   10910.046,    26117.914,   73457.520, 11795.913

のような感じ.

[1]の場合はソート対象のコピー量は増えるけれど比較コストは増えない.
[2]のようにポインタだけの場合はコピー量は最小になるけれど
メモリにあるポインタを経由して比較用のキーにアクセスするため
比較時間(コスト)が増加する.
で、CPUキャッシュ等の都合から、今時の環境だと[1]のほうが有利なことが多そう.

なので、[1]のようにできるならば、そうしたほうが構造体等のソートは
速くなると思われる.
~
(実体の並べ替えが必要な場合は、まずポインタをベースにこれでソートしておいて、
その結果を元に(作業メモリ使って)コピーし直しても元が取れそう)

で、どうせ、ソート用のテーブルを作るならば、登録順番も控えることで
クィックソートを使えるようにするのも一考.

ソート対象が8バイトから12バイトに増えるが、
マージソートや基数ソートは
余分に外部メモリを必要とするので、
メモリ使用量的には同等か有利ということになる.
(マージソートだと総数の半分、基数ソートだと総数分)

今回の例では、基数ソートに対しては全くだけれど、マージソートと比べるとよい結果となっている.
もっとも[4]はIEEEなfloatの正数であることを前提にキーと登録順を合わせた64bit整数にして
比較を軽くしているので、このように出来ず比較コストが上がると、また違う結果になるだろう.

>(今回の場合マージソート側は floatのまま比較しているのでフェアでないかも.試しにキーをビットイメージのunsiged値にしたところ[1]の結果は10000回1170.596μ秒, 100000回13034.268μ秒. 多少縮むが、一応上記を書き換える必要はなさそ)

~

*** バケット(ビン)ソート

基数ソート以上に利用条件厳しいけれど、条件があえばバケット(ビン)ソートのほうが当然速い.
で、一応、用意してみた([[これ>http://www.6809.net/tenk/html/prog/sort5/backet_sort.h.htm]])
~
といっても工夫してないので整数のみの対応.

基数ソートのようにgetkeyを与えられるようにすればいいのだけれど、
ただ、基数ソート・ルーチンは、
入力の値がすべて0~255までなら1回+αで処理打ち切ることになりビンソートに近い状態になるので
(多少オーバーヘッドが多いけれど)、
その結果をみれば大体の雰囲気はつかめると思う.

ということで、乱数の値を0~255にして試した結果は、[[コレ>http://www.6809.net/tenk/html/prog/sort5/sort_test5_rand256_phenom2_945.log]].
~
…他のテスト(SmpClass)は整数型にしてなかったので、結局intテストしか意味がなかった.

抜粋すると、
,             ,       100個,      1024個,     10000個,    100000個,   1000000個
,QUICK SORT   ,       2.110,      32.696,     359.920,    3716.045,   40616.405
,マージ SORT  ,       2.433,      42.029,     497.885,    5679.423,   66518.720
,基数 SORT    ,       2.089,      11.584,     106.138,    1293.111,   14738.046
,BACKET SORT  ,       1.845,       9.299,      81.253,     859.956,   11884.890

のような感じ.場合によっちゃ、やっぱりバケットソート専用も意味あるかな.



*** その他諸々

当然、それなりに測定誤差がある.~
細かい数値ままにしてるけれど、上位1,2桁ぐらいの感覚でみるのがよさそう.

//数値にすると差があるように見えるけれど、倍速になるとしても、それが、
//全体の処理の20%だったものが10%になるのか、
//0.2%だったものが0.1%になるのか、
//結局、ソート個数や実行環境しだいなので、トレードオフの判定は前提が定まってから.

前回以降にCPUを換装してしまい、今回分と前回分を単純に比較できなくなってしまったので、
テストでは、安定ソートだけでなく、前回試した他のソートもいくつか試している.
~
ついでに前回やりそこねてた シェルソートも追加(思ったより速い処理だった).
~
std::vectorと同様に無理やり multisetに挿入した場合も追加
(安定なわけじゃないし、ソートとしてはやっぱり遅いけれど)

前回のテストでは、quick_sortのtemplate版が内部でイテレータのアドレス比較してて
実質、配列のソートにしか対応してなかった. で、オフセット値を用いて修正してみると、
Bidi版と大差なくなってしまった.
厳密にはBidi版のほうがまだ1変数多くなるので、比較処理によっては差がありえるけど、
これくらいなら利便のほう優先して、今回のテストのquickソートは前回のBidi版をベースにした.
~
(けど、classのソート等で、一旦、ポインタを集める場合は配列になるだろうで、
それなら配列版のほうがよいという考えも)

前回の結論に基づき、quickソート内部の挿入ソートを Bidirectional Iterator を
受け付ける形でやねう版にしてみたはいいけど、性能出なかった.
よくよく考えれば、
やねう版挿入ソートは、無駄な代入を減らせる可能性が高まる代わりに、比較回数が1回増えてる.
比較処理がコピーよりも十分にコストが安いことが前提なわけで、
比較のコストが高くなる場合は当然不利だ.
ただ、元のソースは、ループで1回無駄に比較をしている状態でもあるので、その1回分の比較を
回避することで改善した...が、[[ソースが結構酷い状態>http://www.6809.net/tenk/html/prog/sort5/quick_sort_y.h.htm]]に.
~
改善できたといっても普通のとどっこいどっこいな結果だったので、
結局、マージソートともども、普通のを用いることにした.

基数ソートルーチンは、実は dmc でコンパイルすると int 版の結果が不正になってしまっていた.
こちらのバグかもしれないけれど、深く追求せず.
他にも玄箱でTYPE_SMPCLASS=4でコンパイルするといくつかのソートで実行結果が不正になるが、これも放置.

クィックソート等再帰を用いた処理は当たり所が悪いとスタック溢れがあるよう.
(乱数を0~255にしたら駄目なモノがあった... 個数減らして回避)

open watcom c++ (v1.8)の場合、std::stable_sort, std::upper_bound が未実装だった.
辻褄あわせして通したけれど、他にもテンプレートの特殊化ができなかったり、と、
まだ使うにはつらい感じ.

今回linux環境で使ったタイマーはwinに比べての精度がよくなさそう(4ミリ秒単位くらい?). 
ただ、他のプロセスの時間を含まない値なので、そういう面では楽かも.