|
2009-12-12[土] ソートはPGの基礎知識...昔(もう20年ほど前か)、os-9/6809を使っていたときアセンブラで dirコマンドを自作してソート機能をつけたことがある。 このとき最初 単純にかける(O(n^^2^^)系の)ソートで 実装していたのだけど、 公開してみたら、遅いからクィックソートにしてみたら、 と言われたのだった。 実際、差し替えたところ、 十数秒かかっていたのが3秒ぐらいになって、非常に驚いた覚えがある。 アセンブラでカリカリに書いてるから速いつもりだったんだよ。 でもそれ以上にアルゴリズムの性能が段違いにモノをいう、 ってのを身をもって教えられたのでした。 まあ、ものわかりの悪い奴なんで、 実際に経験しないと気づけないという... 本に速いと書かれているのみてても、その性能差を汲み取れてないのよね. その後、情報処理専門でない理系の大学のプログラムの授業で ソートを習ったりしたので、PGならソートくらいは知ってて当然の つもりだったのだけど... 数年前、作るものの仕様に整列をする部分があって、 やたら見積もり時間がおおかったり難色しめしたりする子がいて、 聞いてみるとソートを知らないという。 ゲーム専門学校とはいえプログラマ・コースだったから てっきり知っていると思ったら習ったことない、と。 初めてコレ聞いたときはかなりがっくりきた。 その後ゲ専出の何人か聞いた範囲ではほとんどが習ってなかった。 習っていた子もいたけれど、 バブルソートを自分で書いたことがある程度で、 でもって、ちゃっかりそのルーチンを仕事の実機で書いてくれて、 非常に残念な気分を味わえたのだった。(己と同じ過ちを...) これが酷いのか普通なのかはよくわからないけれど... ソートに関しては、 簡単だけれど性能の出ないルーチンを下手に作らせるよりも (PGは自分が書いたルーチンを使いたがるものだから)、 アルゴリズムの違いの性能差をとっとと見せ付けておくほうが、 そして、標準ライブラリにはそれらを使ったstd::sort(なりqsortなり)が あることを知ってもらっているほうが、いいだろうと思う.
ソート時間を測定してみる.ということで、かるくソート時間を計測してみとく. 実行環境は Athron64 X2 5600+ 8GB(Vista64) と Crusoe TM5400(600MHz) 256M(Win2k) なマシン. テストしてみたルーチンはコレ. 元ネタはwikipediaやその他検索ひっかかった所から.(面倒なんでクィックソートとか単純なまま) バブル,選択,挿入, コム, クィック, クィック+挿入(閾値32), std::sort, qsort の時間をチェック. (std::sortを呼ぶためC++でコンパイルしてるけれど他はCでの記述状態)
適当な個数のソートを何回か繰り返した平均を出している。 テスト環境は普段使っているPCのまま。 なるべく他のソフト立ち上げていないけれど、エディタやファイラは 多少残してたり常駐ソフトも残ってるしで、厳密さはなし。 時間計測も単純にC関数のclock()に任せてるので精度とかは微妙かもだし。 測定しなおすと、細かい数字は結構かわるし、たまに当たり所が悪いと余計に時間 食っていることもありそうだし。
それでも、大雑把な傾向は出てると思う.
Crusoe TM5400(600MHz) 256M(Win2k)環境でのint値のソート時間.(単位:μ秒)
Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのint値のソート時間.(単位:μ秒)
上から３つが Ｏ(ｎ^^2^^)、次の２つがＯ(ｎlogｎ)。 10,20個程度だと、大差ない雰囲気があるけれど、 1000個とか10000個のソートになってくると Ｏ(ｎ^^2^^)ものとＯ(ｎlogｎ)モノとで1～3桁 時間が違ってきてる。 （当然それ以上だとさらに差は拡大するわけで） 数が少ないときは比較的似通っているといっても、 挿入ソートは目だって速く、 上記結果だと、TM5400では int 50個程度までなら、Athron64X2では int 100個程度 までなら、コムソートやクィックソートより速い結果になっている. (もちろんCPU等環境の違いで個数は大きく変わる)
で、クイックソートは、一定個数以下になったら挿入ソートに切り替えることが
可能で、それによって速度を上げることができる. std::sort()も実はだいたい同様でクィック＋挿入(少なくともvcのはだったはず.)。 若干遅い結果なのは汎用性等の書き方で多少オーバーヘッドがあるのか. この差が問題になるかどうかは、用途しだいだけど、 普段気にするようなレベルではないだろう. ※追記>std::sort()の実装は(普通?は) 再帰が深くなるとヒープソートに切替えるらしい. (イントロソートらしい?)
ただ、Cライブラリの qsortもアルゴリズム自体は同様と思われるが、 こちらはCプログラムでの汎用性のため (とくにintなんていう単純なデータのソートとしては) オーバーヘッドが大きくなってしまっている模様。 quick+挿入に対して、1桁違うことはないだろうが、 下手すると数倍の時間がかかったりして、結構大きい。 C言語の場合は、性能のためにあえてqsortを使わず、 自前で(コムやクィック)ソート・ルーチン用意するのは、 ありの選択. （が、性能と手間を思うと、C++環境にできるなら とっととC++に移行してしまうのが吉かも） ※クィックソートから挿入ソートへの切替個数は、 コンパイラ付属のものにあわせて 32個にしている。 アルゴリズムの本(20年位前にかかれたもの)をみると、 CPU性能やコンパイラ性能等でかわってくるが だいたい 10～20 位、って値が示されているのだが、 最近のCPUの性能がいいのかより大きい値のほうが速いようだった.
ついでに他のソート時間を測定してみる.ついでに、wikipediaのコムソートの説明にあったcomb sort 11 と、 数日前に流行?っていたやねうらお氏の挿入ソートも試してみた。 (ちょっとはしょりすぎて100～1000の精度がいまいち...) Crusoe TM5400(600MHz) 256M(Win2k)環境でのint値のソート時間.(単位:μ秒)
Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのint値のソート時間.(単位:μ秒)
Athron64X2 5200+(2.6GHz) 8GB(Vista64)環境でのdouble値のソート時間.(単位:μ秒)
comb sort11については、個数が多いときには効果あるようだけど、逆に個数が 少ないときは増えた if 文のペナルティが出るのか、遅くなってしまっている。 その効果もささいな感じなので、無理に使う必要はなさそう. やねうらお氏の挿入ソートだけど、説明読んだときは効きそうに思ったのだけど、 結果は、よくなったり悪くなったり、で、ちょっと残念な結果でした。 いや、なんか、自分がポカやってる可能性は多いにあるのですが。 (TM5400の50個の列の値は、当たり所悪く他の処理時間が混ざったパターンぽく) やなう版は、最内側のループの外側とはいえ、外のループの内側に if文が増えているので、そのへんが影響して、 コンパイラの最適化やCPUのキャッシュ具合、分岐予測 等、 何かバランス的にくづれて、メモリー代入のペナルティと同等か それ以上のペナルティになってしまっているのかな？ 追記:こっちを書くまで気づいてなかったけど、 比較回数が1回増えてるので、コピーしないですました時間より 比較時間が増えるのが無視できないということかも. (元記事の前提と違う状態で使ってしまったとも)
その他
しらべていないけれど、 (己がかいた)クィック＋挿入は、一見性能よさそうにみえるけど、 個数がある数(以上?)だと、急激に時間がふえてしまったりしていた. ちょっと困った. あとソースをコンパイルしたexeや使ったバッチ等 |