2002-06-23

うーん、がんばってみるものです。

ソートする要素数が少ないときは挿入ソートに切り替えたり、クイックソート時並び替えの基準値を選り好み(いいかげんな言いかた)したりと改善してみたところ、ソート対象の要素の並び状態にかかわらずほぼ一定の速さで処理できるようになりました。全体的な処理速度もアップ。Cコンパイラに付属しているqsort関数のソースコードを読んだのがひじょうに参考になりました。やはりいざとなったら「ソースを使え」ってことでしょうか。

xhtml.txc
304 KB/9845行
xhtml.txc
(ソート済み)
html40.txt
773 KB/18914行
ログファイル
555 KB/11545行
再帰呼び出し版 541 ms 86905 ms 1141 ms 13729 ms
スタック実装+α版 470 ms 86234 ms 1001 ms 13510 ms
挿入ソート併用選り好み版 440 ms 430 ms 951 ms 161 ms
txSort関数版(参考) 270 ms 260 ms 791 ms 371 ms

それでもtxSort関数版と比べると所要時間の傾向が違ってますね……。一部でtxSort関数版を上回ってるし。またちゃんとソートできてないんじゃないかと疑いました(笑)。

いろいろと大ボケしていたところも修正。void*型のポインタでもらったからってそのままvoid*型変数で扱うことはないとか(char*として受け取ればバイト単位で操作できる)。無理やりlong型にキャストして数値として扱ってからvoid*型にまたキャスト、とかしてました。

ふだん使わない頭を使ったということで、勉強にはなりました(笑)。作った関数はそのうちどこかで使うでしょう。