うーん、がんばってみるものです。
ソートする要素数が少ないときは挿入ソートに切り替えたり、クイックソート時並び替えの基準値を選り好み(いいかげんな言いかた)したりと改善してみたところ、ソート対象の要素の並び状態にかかわらずほぼ一定の速さで処理できるようになりました。全体的な処理速度もアップ。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*型にまたキャスト、とかしてました。
ふだん使わない頭を使ったということで、勉強にはなりました(笑)。作った関数はそのうちどこかで使うでしょう。