5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

コームソート vs ヒープソート

1 :デフォルトの名無しさん:01/09/14 18:35
コームソートとヒープソートの処理時間を
比較したのですが、データ数が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分割し、並列に処理する)
のとき、ヒープソートが高速になりました。
なぜ、このような処理時間になってしまったか、原因を
教えて頂けませんでしょうか?

2 :デフォルトの名無しさん:01/09/14 18:42
コームソートって知らない。
コンドームソート?

あとソートアルゴリズムは入力の傾向によっても
性能に違いが出て来るからデータの量だけじゃアレかも。

3 :デフォルトの名無しさん:01/09/14 19:01
>>2
Comb Sortで検索してみましょう。

4 :どーせバカだよ:01/09/14 19:04
シェルソートとどう違うのかよくわからなかった...

5 :1:01/09/14 19:55
>>2
どうもありがとうございました。
確かにそうですね。データの中身によりますね。
ただ、それだけなんでしょうかねー?

6 :デフォルトの名無しさん:01/09/14 19:59
コンドームソーニューと
ナマソーニューはどちらが処理速度が速いでしょうか?
検証してください。

7 :1:01/09/14 20:04
それも興味ありますねー。
(主旨とは外れますが。。。)
こちらの方もだれか実証してください。

8 :デフォルトの名無しさん:01/09/14 21:34
>>6
ハード(セイキ)の硬さや長さ、太さに依存する。
処理速度の臨界値は未調査。

9 :デフォルトの名無しさん:01/09/14 21:52
ようするにコンドームソーニューより
ヒープソーニューの方が
並列向きだったということでわ?
最初のばらつき具合でも変わるきがするけど。

最初のデータを色々と変えて試したら
おもしろいかもね。

10 :召喚士:01/09/15 04:11
マルチスレッドにすると、遅くなるということは、
シングルスレッドのときはCPUキャッシュが効いて速くなってるということでは?

つまりコームソートは(どんなロジックか知らないけど)、
連続したデータを読み込む傾向が強くて、データがキャッシュに入っている事が多いとか?

11 :マージソート信者:01/09/15 04:12
どんな場合でもマージソート使うから関係ない。

12 :召喚士:01/09/15 04:22
うんうん。
でも、メモリが少ないときはシェルソートかも。

13 :デフォルトの名無しさん:01/09/15 04:25
コムソートは極端にメモリ少ないとき使える

14 :デフォりトの名無しさん:01/09/15 06:44
コンドームは極端に精液少ないときでも使ったほうがイイ!

15 :デフォルトの名無しさん:01/09/15 21:36
コームソートは書くのも簡単だし、大概シェルソートより速い(自分で実験してみた)のに、アルゴリズム本とか
読んでもなぜか載ってないですね。
ソート姦数とかがない環境でちょっとソートしなくちゃいけないときなんか便利なんですけどね。

16 :デフォルトの名無しさん:01/09/15 21:58
なにはともあれ安定なソートが便利なことが多いよ。
そういう意味でとりあえずマージソートって意見は結構わかる。

17 :デフォルトの名無しさん:01/09/15 22:04
>>15
日頃どういう文章を書いているのかよくわかる変換だな

18 :デフォルトの名無しさん:01/09/16 01:05
あ、あれってコームソートって読むのか。
昆布ソートって読んでいたよ。

19 :デフォルトの名無しさん :01/09/17 19:52
で、>>7
の件はどうなったの?

20 :デフォルトの名無しさん:01/09/17 20:08
コーム=くし  

21 :デフォルトの名無しさん:01/09/17 20:33
安定なソートってマージソートより
インデックス付きクイックソートのが速くない?

22 :デフォルトの名無しさん:01/09/17 22:23
>>21
それだと比較回数が最悪2倍にならない?インデックスのメモリも必要だし。
まあ、2倍ぐらいならマージソートより速い場合が多いかな。

23 :デフォルトの名無しさん:01/09/21 16:52
メモリ要らない、ベクターじゃなくてリストでも使える、
クイックと違ってクリティカルに遅い状況がない
ってなわけで、コームマンセー野郎です。

もっとも、頭悪いんで、バブルしかアルゴリズムを
理解してないのが原因なのだが。

24 :デフォルトの名無しさん:01/09/24 09:26
コーマンとヒップのどちらを基準とするかの命題

25 :デフォルトの名無しさん:01/09/26 03:46
こんなん出ましたけど。

ソートアルゴリズムを熱く語ろう♪
ttp://piza.2ch.net/tech/kako/978/978149371.html

26 :デフォルトの名無しさん:01/09/26 03:56
>>23
コームソートをリストに適用するのってどうやるの?

27 :デフォルトの名無しさん:01/09/26 06:38
>>26
バブルソートならリストに適用できると思う。
問題は、10/13の位置がすぐに特定できないってのだと思う。
だけど、最初の3回以降は、幅が半分以下になるので、
それ以降はソート中にカウンターを用意して次のスタート位置を保存。

これでニュアンスわかるかな…。

28 :デフォルトの名無しさん:01/09/27 01:27
>>26
http://www.s34.co.jp/cpptechdoc/article/sort/index.html#4

29 :26:01/09/28 21:08
>>27-28
ありがとー。
みんな頭いいね

30 :デフォルトの名無しさん:01/09/30 02:18
コムソート11

31 :デフォルトの名無しさん:01/09/30 03:54
>1
CPUクロックで性能測るってのはイマイチ。
出来れば、プログラム中にステップカウンタをつけて
比較回数等を出し、それを提示して欲しい。

32 :デフォルトの名無しさん:01/10/01 03:30
リストのコムソート、思ったより速いですね。
コムソート程度のスピードが出せる他のリスト向け
ソートアルゴリズムって無いですか?

33 :デフォルトの名無しさん:01/10/01 08:12
>>32
リストにはマージしかないだろ

34 :デフォルトの名無しさん:01/10/01 19:46
Σ(゚д゚lll)ガーン

35 :デフォルトの名無しさん:01/10/02 20:44
スレ違いですまないが、コームソートがよくわからん。
挿入ソートを改良してシェルソートができたように、
バブルソートを改良してコームソートができたと思っていいのか?
だとしたら、シェルソートが平均 O(N^1.25) 程度かかるのに、
なんでコームソートが O(N*logN) なんだ?

コームソートの文献情報とかない?(論文でも可。)
なんか、Google で引いても録なのが出てこない。

36 :デフォルトの名無しさん:01/10/08 19:55
>>35
以下、昔懐かしいZob-BBSにあった発言のコピペ(関係者いたらごめん)
---------------------------------------------------------------
 コムソートとは...

 このソートアルゴリズムを見たのは、日経バイト1991年11月号です。バイト誌の翻訳
記事。
 あおり文句を引用すると、
・世界で最初に標準的な地位を得たソート・アルゴリズムであるバブル・ソートの欠点
は,実行速度が遅い事である。
・しかし,このアルゴリズムも2〜3行程度プログラムを追加する事で,劇的に速度が
向上する。
・この高速なバブル・ソートならば,コーディングやデバッグが簡単なので,他の高速
なソート・アルゴリズムも太刀打ちできないだろう。
 だそうです。
 実際どんな事をやっているのかというと、バブル・ソートでは隣り合う要素同士の比
較だったのを、ギャップサイズ離れた要素と比較する事によって、浮き上がってくるバ
ブルを高速に移動させてやろうという事です。
 最初のギャップは要素数を1.3で割ったものを使用し、以下、1回のストロークが完了
するたびにギャップを1.3で割ったものを使用します。商が1未満になると、それ以降の
ギャップは1とし、要素の位置がまったく変化しなくなったら終わり。歯の荒いものから
細かいものへと何本もクシを使って髪をとかしていくのに似ている事から、コムソート
と名付けたという事です。
 この1.3という収束率は、色々なリストに対して行ったベンチマークによって得られた
最適な値だそうです。また同様のベンチマークによって、ギャップが9または10になった
時に11に変更するという処理を付け加えることで、さらに処理速度を向上させる事がで
きるようです。この処理を付け加えたコムソートをコムソート11と呼びます。

 以前このソートアルゴリズムを見て、どんなもんだろうな..と思ってた時にk.mitobe
さんが組んでくれたプログラムをアップしておきます。コムソート11のモジュールも入
っているので、さらに詳しく知りたい人はこちらのソースを参照して下さい。
 ちなみに、バブルソートと挿入ソートには(あまりに遅いので)ウェイトが入っていま
せんが、その他のソートにはウェイトが入っています。また、要素の交換が発生する度
にGVRAMへの書き込みが発生するので、ソートアルゴリズムの速度比較にはなりません(
交換と比較の比率によって有利・不利がある)。あくまでもアルゴリズムを視覚的に捉え
るためのものだと思って下さい。
---------------------------------------------------------------

37 :デフォルトの名無しさん:01/10/08 19:57
>コーディングやデバッグが簡単なので,他の高速
>なソート・アルゴリズムも太刀打ちできないだろう。
これが意味不明なんだが...
イントロソートが最速。

38 :デフォルトの名無しさん:01/10/08 20:04
>>35
参考になるかどうかわからないけど……。

ttp://www.bsdclub.org/~motoyuki/d/d200005c.html#26-1

ただ、この文中の「quick sort よりも高速」ってのはどうなんだろうな。
条件にもよりそうな気がするが。

10 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)