コームソート vs ヒープソート
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
NGNG比較したのですが、データ数が16M(16×1024×1024)
のとき、以下のようになりました。
処理時間 CPU使用率
コームソート(スレッド1つ) 46.35 sec 99.6 %
(スレッド8つ) 17.05 sec 317.8 %
ヒープソート(スレッド1つ) 75.58 sec 99.3 %
(スレッド8つ) 15.55 sec 320.4 %
結果から、スレッドが1つ(データを並列化しない)のとき、
コームソートが、スレッドが8つ(データを8分割し、並列に処理する)
のとき、ヒープソートが高速になりました。
なぜ、このような処理時間になってしまったか、原因を
教えて頂けませんでしょうか？
0002デフォルトの名無しさん
NGNGコンドームソート？
あとソートアルゴリズムは入力の傾向によっても
性能に違いが出て来るからデータの量だけじゃアレかも。
0003デフォルトの名無しさん
NGNGComb Sortで検索してみましょう。
0004どーせバカだよ
NGNG00051
NGNGどうもありがとうございました。
確かにそうですね。データの中身によりますね。
ただ、それだけなんでしょうかねー？
0006デフォルトの名無しさん
NGNGナマソーニューはどちらが処理速度が速いでしょうか？
検証してください。
00071
NGNG(主旨とは外れますが。。。)
こちらの方もだれか実証してください。
0008デフォルトの名無しさん
NGNGハード（セイキ）の硬さや長さ、太さに依存する。
処理速度の臨界値は未調査。
0009デフォルトの名無しさん
NGNGヒープソーニューの方が
並列向きだったということでわ？
最初のばらつき具合でも変わるきがするけど。
最初のデータを色々と変えて試したら
おもしろいかもね。
0010召喚士
NGNGシングルスレッドのときはCPUキャッシュが効いて速くなってるということでは？
つまりコームソートは（どんなロジックか知らないけど）、
連続したデータを読み込む傾向が強くて、データがキャッシュに入っている事が多いとか？
0011マージソート信者
NGNG0012召喚士
NGNGでも、メモリが少ないときはシェルソートかも。
0013デフォルトの名無しさん
NGNG0014デフォりトの名無しさん
NGNG0015デフォルトの名無しさん
NGNG読んでもなぜか載ってないですね。
ソート姦数とかがない環境でちょっとソートしなくちゃいけないときなんか便利なんですけどね。
0016デフォルトの名無しさん
NGNGそういう意味でとりあえずマージソートって意見は結構わかる。
0017デフォルトの名無しさん
NGNG日頃どういう文章を書いているのかよくわかる変換だな
0018デフォルトの名無しさん
NGNG昆布ソートって読んでいたよ。
0019デフォルトの名無しさん
NGNGの件はどうなったの？
0020デフォルトの名無しさん
NGNG0021デフォルトの名無しさん
NGNGインデックス付きクイックソートのが速くない？
0022デフォルトの名無しさん
NGNGそれだと比較回数が最悪２倍にならない？インデックスのメモリも必要だし。
まあ、２倍ぐらいならマージソートより速い場合が多いかな。
0023デフォルトの名無しさん
NGNGクイックと違ってクリティカルに遅い状況がない
ってなわけで、コームマンセー野郎です。
もっとも、頭悪いんで、バブルしかアルゴリズムを
理解してないのが原因なのだが。
0024デフォルトの名無しさん
NGNG0025デフォルトの名無しさん
NGNGソートアルゴリズムを熱く語ろう♪
ttp://piza.2ch.net/tech/kako/978/978149371.html
0026デフォルトの名無しさん
NGNGコームソートをリストに適用するのってどうやるの？
0027デフォルトの名無しさん
NGNGバブルソートならリストに適用できると思う。
問題は、10/13の位置がすぐに特定できないってのだと思う。
だけど、最初の3回以降は、幅が半分以下になるので、
それ以降はソート中にカウンターを用意して次のスタート位置を保存。
これでニュアンスわかるかな…。
0028デフォルトの名無しさん
NGNGhttp://www.s34.co.jp/cpptechdoc/article/sort/index.html#4
002926
NGNGありがとー。
みんな頭いいね
0030デフォルトの名無しさん
NGNG0031デフォルトの名無しさん
NGNGCPUクロックで性能測るってのはイマイチ。
出来れば、プログラム中にステップカウンタをつけて
比較回数等を出し、それを提示して欲しい。
0032デフォルトの名無しさん
NGNGコムソート程度のスピードが出せる他のリスト向け
ソートアルゴリズムって無いですか？
0033デフォルトの名無しさん
NGNGリストにはマージしかないだろ
0034デフォルトの名無しさん
NGNG0035デフォルトの名無しさん
NGNG挿入ソートを改良してシェルソートができたように、
バブルソートを改良してコームソートができたと思っていいのか？
だとしたら、シェルソートが平均 O(N^1.25) 程度かかるのに、
なんでコームソートが O(N*logN) なんだ？
コームソートの文献情報とかない？(論文でも可。)
なんか、Google で引いても録なのが出てこない。
0036デフォルトの名無しさん
NGNG以下、昔懐かしいZob-BBSにあった発言のコピペ（関係者いたらごめん）
---------------------------------------------------------------
コムソートとは...
このソートアルゴリズムを見たのは、日経バイト1991年11月号です。バイト誌の翻訳
記事。
あおり文句を引用すると、
・世界で最初に標準的な地位を得たソート・アルゴリズムであるバブル・ソートの欠点
は，実行速度が遅い事である。
・しかし，このアルゴリズムも２〜３行程度プログラムを追加する事で，劇的に速度が
向上する。
・この高速なバブル・ソートならば，コーディングやデバッグが簡単なので，他の高速
なソート・アルゴリズムも太刀打ちできないだろう。
だそうです。
実際どんな事をやっているのかというと、バブル・ソートでは隣り合う要素同士の比
較だったのを、ギャップサイズ離れた要素と比較する事によって、浮き上がってくるバ
ブルを高速に移動させてやろうという事です。
最初のギャップは要素数を1.3で割ったものを使用し、以下、１回のストロークが完了
するたびにギャップを1.3で割ったものを使用します。商が1未満になると、それ以降の
ギャップは1とし、要素の位置がまったく変化しなくなったら終わり。歯の荒いものから
細かいものへと何本もクシを使って髪をとかしていくのに似ている事から、コムソート
と名付けたという事です。
この1.3という収束率は、色々なリストに対して行ったベンチマークによって得られた
最適な値だそうです。また同様のベンチマークによって、ギャップが9または10になった
時に11に変更するという処理を付け加えることで、さらに処理速度を向上させる事がで
きるようです。この処理を付け加えたコムソートをコムソート11と呼びます。
以前このソートアルゴリズムを見て、どんなもんだろうな..と思ってた時にk.mitobe
さんが組んでくれたプログラムをアップしておきます。コムソート11のモジュールも入
っているので、さらに詳しく知りたい人はこちらのソースを参照して下さい。
ちなみに、バブルソートと挿入ソートには(あまりに遅いので)ウェイトが入っていま
せんが、その他のソートにはウェイトが入っています。また、要素の交換が発生する度
にGVRAMへの書き込みが発生するので、ソートアルゴリズムの速度比較にはなりません(
交換と比較の比率によって有利・不利がある)。あくまでもアルゴリズムを視覚的に捉え
るためのものだと思って下さい。
---------------------------------------------------------------
0037デフォルトの名無しさん
NGNG>なソート・アルゴリズムも太刀打ちできないだろう。
これが意味不明なんだが...
イントロソートが最速。
0038デフォルトの名無しさん
NGNG参考になるかどうかわからないけど……。
ttp://www.bsdclub.org/~motoyuki/d/d200005c.html#26-1
ただ、この文中の「quick sort よりも高速」ってのはどうなんだろうな。
条件にもよりそうな気がするが。
0039age
NGNG0040デフォルトの名無しさん
NGNGquick sortより速いってのは元のByteの記事にはなくて、
日本人のライターが自分で実験して付け加えたんだが、
その実験がムチャクチャ。
整数だけソートできる、インラインで書いたcomb sort
と、qsortを呼び出した結果の時間を比較してた。
qsortより速いというのは眉唾だろ。んでsage。
0041デフォルトの名無しさん
NGNGfor (i=0;i<NUM;i++) //乱数を埋め込む
data[i]=(data[i]<<16)+ (rand() & 0xffff);
qsort(data,NUM,sizeof(data[0]),comp);
for (i=0;i<NUM;i++) //データを元のビット位置に戻す
data[i]=data[i]>>16;
/*このように、クイックソートを呼び出す前に、データを上にシフトして空いた下位ビットに乱数を埋め込んでおけば、
データに同じ値がたくさん入っているような最悪パターンでもマージソートよりも高速にソートできます。
ただし、乱数のために数倍メモリを食います。*/
0042デフォルトの名無しさん
NGNGどっちかっつーと呼び出し側のテクだね。
rand()をiに変えたら安定ソートになりそう。
0043デフォルトの名無しさん
NGNG0044デフォルトの名無しさん
NGNG数値の並べ替えなら最強。
工夫すれば文字列にも使える。そしてかなり早い。
0045デフォルトの名無しさん
NGNG0046デフォルトの名無しさん
NGNG0047デフォルトの名無しさん
NGNG0048デフォルトの名無しさん
NGNG駄スレあげんなｳﾞｫｹ!!
■ このスレッドは過去ログ倉庫に格納されています