差分表示

*&date(Y-n-j[lL],2009/12/12); ソートはPGの基礎知識...

昔(もう20年ほど前か)、os-9/6809を使っていたときアセンブラで
dirコマンドを自作してソート機能をつけたことがある。
このとき最初シェルソートで実装していたのだけど、
公開してみたら、遅いからクィックソートにしてくれ、
と言われたのだった。
実際、差し替えたところ、
十数秒かかっていたのが3秒ぐらいになって、非常に驚いた覚えがある。
アセンブラでカリカリに書いてるから速いつもりだったんだよ。
でもそれ以上にアルゴリズムの性能が段違いにモノをいう、
ってのを身をもって教えられたのでした。

まあ、ものわかりの悪い奴なんで、
実際に経験しないと気づけないという...
本に速いと書かれているのみてても、その性能差を汲み取れてないのよね.

その後、情報処理専門でない理系の大学のプログラムの授業で
ソートを習ったりしたので、PGならソートくらいは知ってて当然の
つもりだったのだけど...

数年前、作るものの仕様に整列をする部分があって、
やたら見積もり時間がおおかったり難色しめしたりする子がいて、
聞いてみるとソートを知らないという。
ゲーム専門学校とはいえプログラマ・コースだったから
てっきり知っていると思ったら習ったことない、と。
初めてコレ聞いたときはかなりがっくりきた。

その後ゲ専出の何人か聞いた範囲ではほとんどが習ってなかった。
習っていた子もいたけれど、
バブルソートを自分で書いたことがある程度で、
でもって、ちゃっかりそのルーチンを仕事の実機で書いてくれて、
非常に残念な気分を味わえたのだった。(己と同じ過ちを...)

これが酷いのか普通なのかはよくわからないけれど...

ソートに関しては、
簡単だけれど性能の出ないルーチンを下手に作らせるよりも
(PGは自分が書いたルーチンを使いたがるものだから)、
アルゴリズムの違いの性能差をとっとと見せ付けておくほうが、
そして、標準ライブラリにはそれらを使ったstd::sort(なりqsortなり)が
あることを知ってもらっているほうが、いいだろうと思う.

//※自分でバブルソートなりを考え付ける(発明できる)人は賢い人だ。
//けど
// //（クイックソート思いつけて、かつ、数が少ないときは、
// //挿入ソートのほうが速いから切替、
// //とかまで経験なく思いつけるほどの天才はまずいないので)、
// ライブラリ知らない人より使える人のほうが仕事的にはありがたいのなあ、と。

~
** ソート時間を測定してみる.

ということで、かるくソート時間を計測してみとく.

実行環境は Athron64 X2 5600+ 8GB(Vista64) と Crusoe TM5400(600MHz) 256M(Win2k)
なマシン.

テストしてみたルーチンは[[コレ>http://www.6809.net/tenk/html/prog/sort_test1.cpp.html]].

元ネタは[[wikipedia>http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88]]やその他検索ひっかかった所から.(面倒なんでクィックソートとか単純なまま)

バブル,選択,挿入, コム, クィック, クィック+挿入(閾値32), std::sort, qsort
の時間をチェック. (std::sortを呼ぶためC++でコンパイルしてるけれど他はCでの記述状態)


適当な個数のソートを何回か繰り返した平均を出している。

テスト環境は普段使っているPCのまま。
なるべく他のソフト立ち上げていないけれど、エディタやファイラは
多少残してたり常駐ソフトも残ってるしで、厳密さはなし。
時間計測も単純にC関数のclock()に任せてるので精度とかは微妙かもだし。
測定しなおすと、細かい数字は結構かわるし、たまに当たり所が悪いと余計に時間
食っていることもありそうだし。

それでも、大雑把な傾向は出てると思う.
~
(追記:コンパイルはvc2008で32bit版でコンパイル)
~
以下、結果.

Crusoe TM5400(600MHz) 256M(Win2k)環境でのint値のソート時間.(単位:μ秒)
|　　　　　　個数| 10個| 20個|  30個|  40個|  50個| 100個|256個|1000個|10000個|
|バブル ソート   |1.362|4.826| 3.853|24.632|38.205| 110.0|  731| 14860|1283800|
|選択 ソート     |1.092|3.564| 7.377|16.140|26.640|  90.0|  470|  6970| 825200|
|挿入 ソート     |0.691|1.964| 3.837| 6.292| 9.415|  40.0|  240|  3064| 373500|
|コム ソート     |1.242|5.850| 5.007| 7.412| 9.465|  25.0|   71|   762|  11000|
|クィックソート  |1.422|5.648| 5.540| 7.732|10.265|  20.0|   70|   300|   8000|
|クィック+挿入   |0.721|1.984| 3.873| 9.372| 7.060|  15.0|   40|   240|   7000|
|std::sort       |1.001|2.844| 3.703| 9.292|13.170|  20.5|   61|   300|   8000|
|qsort           |2.935|7.612|19.763|26.680|35.850|  70.0|  170|   802|  21000| 

Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのint値のソート時間.(単位:μ秒)
|　　　　　　個数| 10個| 20個| 30個| 40個| 50個|100個|256個|1000個|10000個|
|バブル ソート   |0.237|0.738|1.547|2.792|4.115| 18.0|  104|  1566| 152200|
|選択 ソート     |0.249|0.744|1.420|2.280|3.335| 11.5|   62|   822|  78300|
|挿入 ソート     |0.121|0.306|0.533|0.932|1.155|  3.5|   21|   310|  29100|
|コム ソート     |0.232|0.554|0.960|1.412|1.810|  4.5|   14|    76|   1100|
|クィックソート  |0.280|0.720|1.190|1.688|2.530|  5.0|   14|    68|    800|
|クィック+挿入   |0.123|0.300|0.533|0.824|1.145|  3.0|    9|    42|    500|
|std::sort       |0.158|0.340|0.573|0.996|1.340|  3.5|   11|    56|    700|
|qsort           |0.524|1.282|2.153|3.192|4.215|  9.0|   28|   130|   2100| 


上から３つが Ｏ(ｎ^^2^^)、次の２つがＯ(ｎlogｎ)。
//(クィック＋挿入は応用モノで、std::sortは C++標準ライブラリ(この場合vc付属のもの)、 qsort はC標準ライブラリのもの)

10,20個程度だと、大差ない雰囲気があるけれど、
1000個とか10000個のソートになってくると
Ｏ(ｎ^^2^^)ものとＯ(ｎlogｎ)モノとで1～3桁 時間が違ってきてる。
（当然それ以上だとさらに差は拡大するわけで）

数が少ないときは比較的似通っているといっても、
挿入ソートは目だって速く、
上記結果だと、TM5400では int 50個程度までなら、Athron64X2では int 100個程度
までなら、コムソートやクィックソートより速い結果になっている.
(もちろんCPU等環境の違いで個数は大きく変わる)


で、クイックソートは、一定個数以下になったら挿入ソートに切り替えることが
可能で、それによって速度を上げることができる.~
それが クィック+挿入 の行の結果.

std::sort()も実は同様でクィック＋挿入(少なくともvcのはだったはず)。
若干遅い結果なのは汎用性等の書き方で多少オーバーヘッドがあるのか.
この差が問題になるかどうかは、用途しだいだけど、
普段気にするようなレベルではないだろう.

ただ、Cライブラリの qsortもアルゴリズム自体は同様と思われるが、
こちらはCプログラムでの汎用性のため
(とくにintなんていう単純なデータのソートとしては)
オーバーヘッドが大きくなってしまっている模様。

quick+挿入に対して、1桁違うことはないだろうが、
下手すると数倍の時間がかかったりして、結構大きい。

C言語の場合は、性能のためにあえてqsortを使わず、
自前で(コムやクィック)ソート・ルーチン用意するのは、
ありの選択.

（が、性能と手間を思うと、C++環境にできるなら
とっととC++に移行してしまうのが吉かも）

※クィックソートから挿入ソートへの切替個数は、
コンパイラ付属のものにあわせて 32個にしている。
アルゴリズムの本(20年位前にかかれたもの)をみると、
CPU性能やコンパイラ性能等でかわってくるが
だいたい 10～20 位、って値が示されているのだが、
最近のCPUの性能がいいのかより大きい値のほうが速いようだった.
(少なくともintやdouble程度をソートする分には）


** ついでに他のソート時間を測定してみる.

ついでに、wikipediaのコムソートの説明にあったcomb sort 11 と、
数日前に流行?っていた[[やねうらお氏>http://d.hatena.ne.jp/yaneurao/]]の[[挿入ソート>http://d.hatena.ne.jp/yaneurao/20091126]]も試してみた。
(ちょっとはしょりすぎて100～1000の精度がいまいち...)

Crusoe TM5400(600MHz) 256M(Win2k)環境でのint値のソート時間.(単位:μ秒)
|個数             | 10個| 20個|  30個|  40個|  50個| 100個|256個|1000個|10000個|
|insert sort      |0.691|1.964| 3.837| 6.292| 9.415|  40.0|  240|  3064| 373500|
|insert sort(yane)|0.681|1.962| 3.840| 6.368|14.220|  40.0|  200|  6230| 425700|
|comb sort        |1.242|5.850| 5.007| 7.412| 9.465|  25.0|   71|   762|  11000|
|comb sort11      |1.282|3.084| 0.813|10.936|13.820|  25.0|   80|   582|  11000|
|quick+insert sort|0.721|1.984| 3.873| 9.372| 7.060|  15.0|   40|   240|   7000|
|quick+yane-insert|0.711|2.002| 3.873| 5.368| 7.110|  15.0|   50|   240|   6100|

Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのint値のソート時間.(単位:μ秒)
|個数             | 10個| 20個| 30個| 40個| 50個|100個|256個|1000個|10000個|
|insert sort      |0.121|0.306|0.533|0.932|1.155|  3.5|   21|   310|  29100|
|insert sort(yane)|0.118|0.316|0.580|0.924|1.345|  4.5|   27|   404|  38800|
|comb sort        |0.232|0.554|0.960|1.412|1.810|  4.5|   14|    76|   1100|
|comb sort11      |0.231|0.564|1.027|1.480|1.945|  4.5|   14|    74|   1000|
|quick+insert sort|0.123|0.300|0.533|0.824|1.145|  3.0|    9|    42|    500|
|quick+yane-insert|0.123|0.322|0.587|0.864|1.190|  3.0|    9|    42|    600|

Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのdouble値のソート時間.(単位:μ秒)
|個数             | 10個 | 20個 | 30個 | 40個 | 50個 |100個|256個|1000個|10000個|
|insert sort      | 0.185| 0.478| 0.863| 1.340| 1.910|  6.5|   35|   480|  47100|
|insert sort(yane)| 0.196| 0.502| 0.903| 1.400| 1.990|  6.5|   35|   498|  48600|
|comb sort        | 0.310| 0.812| 1.397| 2.148| 2.840|  7.0|   22|   112|   1700|
|comb sort11      | 0.314| 0.860| 1.453| 2.208| 3.020|  6.5|   22|   108|   1600|
|quick+insert sort| 0.185| 0.502| 0.863| 1.376| 1.930|  4.5|   14|    66|    900|
|quick+yane-insert| 0.194| 0.510| 0.907| 1.424| 1.920|  5.0|   14|    68|    900|

comb sort11については、個数が多いときには効果あるようだけど、逆に個数が
少ないときは増えた if 文のペナルティが出るのか、遅くなってしまっている。
その効果もささいな感じなので、無理に使う必要はなさそう.

やねうらお氏の挿入ソートだけど、説明読んだときは効きそうに思ったのだけど、
結果は、よくなったり悪くなったり、で、ちょっと残念な結果でした。
いや、なんか、自分がポカやってる可能性は多いにあるのですが。
(TM5400の50個の列の値は、当たり所悪く他の処理時間が混ざったパターンぽく)

やなう版は、最内側のループの外側とはいえ、外のループの内側に
if文が増えているので、そのへんが影響して、
コンパイラの最適化やCPUのキャッシュ具合、分岐予測 等、
何かバランス的にくづれて、メモリー代入のペナルティと同等か
それ以上のペナルティになってしまっているのかな？


*** その他


しらべていないけれど、
(己がかいた)クィック＋挿入は、一見性能よさそうにみえるけど、
個数がある数(以上?)だと、急激に時間がふえてしまったりしていた.
ちょっと困った.

あとソースをコンパイルしたexeや使ったバッチ等

[[ダウンロード>http://www.6809.net/tenk/html/prog/sort_test1_20091212.zip]]

----
#comment