差分表示
*&date(Y-n-j[lL],2009/12/15); ソートについて２
** test1 補足
やねう版の結果がちょっと気になったので、手元ですぐ動くvc以外の
コンパイラでも試してみた。~
mingw32-gcc(3.4.5, 4.4.0TDP-1), dmc8.51(beta), open watcom 1.8, bcc5.82(フリーのTurboC++) あたり. (手元に残っていたものなので、最新版というわけでない)
プログラムのほうも時間計測の関数変えたり結果出力編集するの面倒だったので若干修正.
~
([[ソース:sort_test1.cpp>http://www.6809.net/tenk/html/prog/sort_test1_kai.cpp.html]])
実行環境は athron64x2 5200+ 8GB(Vista64)環境.
//実行結果は [[1回目>PG雑記/sort_test1(20091214版)の1回目]]、 [[2回目>PG雑記/sort_test1(20091214版)の2回目]]
実行結果は [[1回目>http://www.6809.net/tenk/html/prog/sort_test1_1st.txt]]、 [[2回目>http://www.6809.net/tenk/html/prog/sort_test1_2nd.txt]]
(だいたい似たようなもんだけれど、それなりに誤差があるので雰囲気見るために)
~
(あと表にはしてないけれどvcは2003,2010β2ともvc2008と同様の結果だった)
~
やねう版挿入ソートについては、mingw-gcc,bccの場合は効果があるよう.
他はどちらともいえない感じ。
//vcとかの このデータだけみるとやねう版のほうが心持悪く思えるけど、
このへんは、このテストの偶然の部分が多そうなので判別付かず.
~
どちらかというと gcc4.4.0 のinsert sortの結果が抜き出て悪い..これは
コンパイラのバージョン上がれば直る?(駄目?). 3.4.5のほうは素直な結果に思える.
さらに quick sort の一部として使った場合の結果は、微妙.~
傾向は現れてそうな感じもあるけどひっくり返ることあるし、そもそも測定誤差の振れ幅を思うと気にしても仕方ないレベルかもで.
でもまあ、基本どんぐりの背比べ、だけどよくなるコンパイラもある、んだから、汎用的に書く場合は やねう版 でいいかも、と。
（下手な書き方してでっかい要素をそのままソートする場合にはやねう版のほうが有利な気もするし）
※ と結論にしたけれど、後のtest2～は test1補足を試す前に調査してたのでやねう版になってません
~
ついでに std::sort。
gccやwatcomだと他の結果がいまいちのことがあっても
付属stlのstd::sortは速いので、
基本的には付属のを使うのが吉のよう.
vcのは若干、bccのは結構、遅いけれど...
bccについては使ったのは数年前のもので最新じゃないし、
borlandのc++はその時々に付属するstl(の元)が変わったりするので…
てみたらdinkumwareだった(VCと同じ元ネタ)...orz
~
>前回もちょこっと書いたquick sortの10000000個時の時間が極端に悪くなっている件はvcだけでなく他のコンパイラでも同様のよう. スタック拡張とか何か極端なことが起こったのかとも思うけどわからず. このCソースバージョンの元にしたC++テンプレートバージョンでは10000000個実行しても正常な時間だったので、深入りしないで放置中.
※追記: vcのコンパイルオプションが不味く、スタック等のチェックルーチンが結構生成されていた.
(関数分割や分岐が多いと不利だった模様).
チェックを生成しない設定でコンパイルしたら、
結論がかわるほどの大きな違いはなかったけれど、
std::sort等ややねう版の結果も心持よくなったような気も.
~
** test2 引数の数の違いの影響
関数呼び出しオーバーヘッドが性能に影響する、状況だろうから、
じゃあ、2引数版(<専用) と 3引数版（比較ファンクタ指定）
でどれくらいの差がでるか、と思い、試した.（引数の数というより、ループの最内側で使われる引数で渡された'比較'が、ちゃんインライン展開されているや否や）
([[ソース:sort_test2.cpp>http://www.6809.net/tenk/html/prog/sort_test2.cpp.html]])
cでなくc++のテンプレートで実装. std::sortに引数をあわせている.
また quick sort とかいているけど実際には挿入ソートを使ったバージョン.
(以後単にquick sortと書いていても同様)
vcでの結果(単位:μ秒)
| |int 1万個|double 1万個|string 1万個|int 1千万個|double 1千万個 |
|std::sort(arg2) | 756| 1147| 6277| 942694| 1381667|
|std::sort(arg3) | 748| 1147| 6207| 957118| 1408231|
|quick sort(arg2) | 531| 836| 5523| 748300| 1245526|
|quick sort(arg3) | 562| 873| 5526| 764235| 1236120|
|quick sort/bidi(arg2)| 559| 856| 6482| 781253| 1220958|
|quick sort/bidi(arg3)| 539| 870| 5604| 807795| 1252734|
他のコンパイラもだいたい同様の傾向.
引数が2個か3個かの違いは、(ちゃんとオプティマイズされてたら)気になるような
差は見受けられず.
~
(オプティマイズ無しだと当然2引数のほうが速くなる)
てことで、実体つくるなら3引数版をつくってそれを呼び出す2引数版を作る、で
よいのだろう.
~
>表の下２つは、次のテストの前準備として軽く確認実行してみたもの.~
bidiとなっているのは、引数として random iterator でなく bidirectional iterator を受け取れるようにしたバージョン（ようは std::list をソートできるようにしたもの).
>イテレータの大小チェック代わりにカウンタを追加してるため、大きくはないけれど若干遅くなっているのは現れている模様.
~
** test3 std::listのソート
(追記: マージソート失念して間抜けなことしてます..orz)
std::list のソートのテスト. 比較のため、~
-std::vectorをソート
-std::listをquick_sort|bidi版でソート
-std::list.sort()でソート
-listの要素へのポインタのvectorをつくってそれをソート
してみた。~
（[[ソース:sort_test3.cpp>http://www.6809.net/tenk/html/prog/sort_test3.cpp.html]]）
(コンパイルはvc2008)
SmpClass版(mallocポインタやstd::vectorを持つ適当なクラス) (単位:μ秒)
, 個数 , 10個, 20個, 100個, 1000個, 10000個, 100000個
,vectorを quick sort , 23.829, 101.530, 506.015, 6833.299, 93907.745,1378442.931
,list を quick sort , 23.002, 101.610, 510.747, 7135.188, 98371.301,1443433.383
,std::list.sort , 9.272, 23.957, 26.209, 289.911, 3688.178, 69306.364
,list要素へのポインタのvectorをsort , 2.337, 4.322, 19.277, 237.209, 3285.823, 55324.629
std::string版
, 個数 , 10個, 20個, 100個, 1000個, 10000個, 100000個
,vectorを quick sort , 3.806, 9.111, 67.051, 580.947, 7106.490, 77688.365
,list を quick sort , 3.370, 8.543, 69.276, 625.485, 7640.357, 98245.657
,std::list.sort , 9.649, 12.035, 33.156, 372.973, 4950.978, 80472.099
,list要素へのポインタのvectorをsort , 2.562, 5.266, 28.576, 388.569, 4996.934, 82327.433
int版
, 個数 , 10個, 20個, 100個, 1000個, 10000個, 100000個
,vectorを quick sort , 2.098, 3.190, 15.860, 228.311, 2789.600, 32882.182
,list を quick sort , 1.976, 3.299, 17.805, 269.671, 3953.645, 47324.450
,std::list.sort , 9.119, 11.075, 24.704, 252.267, 3489.200, 45217.828
,list要素へのポインタのvectorをsort , 2.381, 4.057, 17.913, 230.364, 6432.312, 37080.760
基本的には SmpClass版の結果が、実使用に近いものだと思う.
で、みてのとおり、std::list でソートしたくなったら、~
std::list のメンバーの sort() を使う~
という当たり前の結論.~
//要素の比較の重さしだいだけれど、要素の実体のコピーをせずリンク付け替えだけだろうから、要素のサイズの影響が少ないよう.
intやdoubleのような小さい要素で少量のときは逆転してるけど、
そもそも個数がn個程度と限定されているならばlistでなくvectorあたりでよく.
無理に bidirectional iterator を受け取れる quick sort 作ってまで
やることじゃない、と.
あと、そのものstd::list自体のソートが必要なく、
途中の処理として整列された順番でデータ舐めたいだけならば、
４つ目のように、
要素へのポインタを集めてそれをソートして使うのが吉かも.
//std::listの実装はみていないけれど、雰囲気的には、一旦ポインタでソートしておいてその結果を元にリンクし直している、って感じなんじゃなかろうか.
//(std::stringの結果が解せないけれど...)
~
** test4 大きめのオブジェクトのソート、スマートポインタのソート
普通は、大きめのオブジェクトの実体を直接ソートしない。しないですむように作る。~
整列状態で処理する箇所用に別途ポインタ配列を作ってそれをソート、~
という感じ。~
//>たとえば Hogeクラスのvectorなりlistなり何なりがあるときvector<Hoge*> hoge_ptr_vec にまず実体へのポインタを貯めてしまい
// struct hoge_ptr_less {
// bool operator()(const Hoge& l, const Hoge& r) const { return *l < *r; }
// };
//>て感じの比較用クラス用意して、
// std::sort(hoge_ptr_vec.begin(), hoge_ptr_vec.end(), hoge_ptr_less());
//>でソート.
//実体をどうしても並び替える必要があるならば、ポインタ配列をソートして、
//その結果をもとにコピーしなおすほうがマシ（メモリー量によるけど）
~
もっとも、大きめのオブジェクトはポインタなりハンドルなりで扱い
そのまま管理/やりとりすることはないだろうで、
c++だとスマートポインタの類による管理も増えている.
じゃあスマートポインタのソートはどう？ってことで、試した.
~
（[[ソース：sort_test4.cpp>http://www.6809.net/tenk/html/prog/sort_test4.cpp.html]]）
以下 SmpClass (mallocポインタ,std::vectorメンバー有り)の結果(単位μ秒)
vc2008版(64バイト)
, 個数 , 10個, 20個, 100個, 1000個, 10000個, 100000個
,vector要素へのポインタのvectorのみをsort , 2.796, 5.147, 21.990, 287.369, 3684.756, 61983.786
,vectorを sort , 30.635, 118.802, 648.003, 8777.072, 118188.904,1659458.255
,ポインタでソートして、その結果でvector再構築 , 11.170, 21.526, 119.504, 1107.969, 17498.802, 196852.603
,shared_ptrのvectorを sort , 4.270, 18.970, 97.132, 1006.036, 14163.602, 254964.388
,intrusive_ptrのvectorを sort , 2.301, 4.994, 28.664, 411.351, 5306.401, 94754.501
,intrusive_ptrのvectorを生ポインタソートで再構築 , 3.479, 6.100, 25.769, 319.049, 4364.801, 76751.165
mingw32-gcc(4.4.0)版(56バイト)
, 個数 , 10個, 20個, 100個, 1000個, 10000個, 100000個
,vector要素へのポインタのvectorのみをsort , 1.872, 2.235, 8.086, 126.084, 1692.534, 33156.449
,vectorを sort , 16.779, 71.353, 335.637, 4449.427, 61817.563, 961931.055
,ポインタでソートして、その結果でvector再構築 , 6.669, 10.973, 70.962, 603.142, 11622.357, 138767.218
,shared_ptrのvectorを sort , 2.953, 7.177, 61.087, 636.142, 9128.046, 190523.935
,intrusive_ptrのvectorを sort , 2.217, 4.397, 25.608, 367.889, 5052.667, 98505.257
,intrusive_ptrのvectorを生ポインタソートで再構築 , 2.225, 3.287, 11.059, 152.973, 2379.911, 45465.695
上から順に.
-本体のソートが不要であれば、やっぱりポインタの配列作ってソートしちまうのが一番安そう.
-実体の直接ソートは桁違いに時間を食うはめに.
-一旦ポインタ配列ソートしてからだと結構ましになる. でもポインタだけの管理にくらべれば桁がやっぱり大きい.
-c++0xで入る予定のstd::shared_ptrの場合. 実体にくらべ小さいとは言え、生のポインタにくらべれば複雑なので、実装方法次第だろうけれど、この例ではちょっと気になる程度のペナルティが発生している感じ.
-boost::intrusive_ptrを使った例. 生のポインタにくらべ時間は数割増といった感じで、思ったよりもペナルティは少ない感じ.~
10,20個程度だとポインタ配列を作るコストのほうが高くなることもあるのか、intrusive_ptr直ソートのほうが速くなることもあるよう.
-boost::intrusive_ptrで管理しているものを、一旦生のポインタ配列を作ってソートし、その結果を元に返す例. 一定以上ソートするならば intrusive_ptr のままよりもこのほうが速い.
~
shared_ptrはいろいろ便利だけれど、やっぱりその分実行時コストがかかってしまう。
それが気にならない箇所ならいいけれど、
ソートのような場合は考えたほうがよさそう.
intrusive_ptrは、ポイント先になるクラス側に参照カウンタ処理が必要となり、
shared_ptrより使い勝手は落ちるけれど、
参照カウンタの処理自体は shared_ptr よりも素直な状態なので、
実行時コストは小さい.
で intrusive_ptr のほうは、ソート済の生ポインタをも一度intrusive_ptrに
することができる(もちろん、このへん、操作をあやまると参照カウンタ管理を
破綻しかねないので注意深く...)が、
shared_ptrは生ポインタ化してソートした結果を元のshared_ptrに戻す方法が
なさそう.
(shared_ptrの指す先でなくshared_ptr自体のアドレスでソートすればだが不本意)
~
追記:比較条件が単純でソートキーが値一つですむようならば、
ポインタのみの配列でなくソートキーとポインタのペアの配列を
ソートしたほうが速くなりやすいと思われる([[test5:雑記/2010-01-11]])
~
[CR]
** ソース＆実行ファイル
とりあえず、今回のソース等を固めたもの.
>[[[download>http://www.6809.net/tenk/html/prog/sort_test_20091215.zip]]]
----
#comment