投稿者: mshibata

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

• TX-Cでクイックソート、サンプルコード（改良版その2）のダウンロード（qsort20020623.zip、2,675 Bytes）

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

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

昨日のバージョンはバグっていたことが判明したので修正。いくら仕事が速くてもちゃんと並び替えられてないのでは意味がありません。

• TX-Cでクイックソート、サンプルコード（改良版の修正版）のダウンロード（qsort20020622.zip、1,947 Bytes）

修正した結果を測定しなおすと、残念ながらそれほど速くなってないみたいです。関数呼び出しのオーバーヘッドとかを気にするよりは、わかりやすく書いたほうがいいというのが今回の教訓ですかね……。

	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
txSort関数版（参考）	270 ms	260 ms	791 ms	371 ms

と、結果をまとめてみました。恐ろしいのはすでにソート済みのデータを再ソートしたときで、ソートしていないものと比べて180倍以上の時間がかかってます。対処法はあるみたいなので、やはりこれは直したほうがいいですかね……。

TX-C APIのtxSort関数を使ってやってみた結果も面白いです。ソート済みかどうかは処理時間にほとんど影響がないので（むしろ純粋に処理行数に依存）、やはりアルゴリズムが違うのでしょう。それにしてもやはりネイティブ処理は速い……。

再帰呼び出しをやめてスタックを自前で確保したり、メモリのコピーを別関数でなくインラインで処理してみたりと、いろいろ改良してみたところ、xhtml.txcを430ミリ秒、html40.txtを891ミリ秒というところまでいきました。

• TX-Cでクイックソート、サンプルコード（改良版）のダウンロード（qsort20020621.zip、1,842 Bytes）

整列済みのデータに弱いクイックソートですが、ほとんど整列済みのテキスト（手元にあったログファイル、約530 KB、10980行）で試してみたらなんと10325ミリ秒もかかってしまいました。WZのソート機能ではテキストによってこんなに差が出たりはしないので、アルゴリズムが違うのでしょう。ほとんど整列済みのテキストを再ソート、というケースは多いですし。

	xhtml.txc 304 KB / 9845行	html40.txt 773 KB / 18908行
再帰呼び出し版	561 ms	1151 ms
スタック実装+α版	430 ms	891 ms

qsortについてはひとまずこれで完成ということで。

TX-Cにはテキストを行でソートするtxSortというAPIがあります。この関数、「タブ区切りテキストの何番目のカラムで並べ替え」などが可能な高度なオプションを備えているわりには、数値としてソートができなかったりと、汎用的なソート関数としてはいまいちです。ANSI Cのqsort関数もTX-Cでは使えません。

そこで、練習もかねて汎用クイックソート関数をTX-Cで組んでみました。参考文献はまたまた『定本 Cプログラマのためのアルゴリズムとデータ構造』。あとはWebでいろいろ解説を読んだり。

• TX-Cでクイックソート、サンプルコードのダウンロード（qsort20020619.zip、1,635 Bytes）

テキストを行ごとに配列に読み込んでソートさせるテストマクロ（サンプルコードに付属）でベンチマーク（笑）を取ってみたところ、ynp5版xhtml.txc（約304 KB、9845行）のソートに561ミリ秒、W3CのHTML 4.01 Specificationのplain text版（約773 KB、18908行）のソートに1151ミリ秒と実用にも耐えられそうな感じです（ThinkPad X20、320 MB RAM）。さすがTX-C。

素朴に再帰呼び出しをしてたり、ループ内でmalloc/freeを繰り返してたりするので、工夫すればもうちょっと速くなりますかね……。

わがままを聞いていただけました。ありがとうございます！　まったく、好き勝手言ってしまってすみませんでした……。

• XHTMLプラグイン用私家版パッチ 第五弾（Final β Laboratory）

ここ数日のFinal β Laboratoryの更新履歴を、XHTMLプラグインの内部処理という超マニアックなトピックとTX-Cのコードで埋もれさせてしまったわけで、幅広い読者がいる「更新履歴」でWZマクロに興味ない人（というかxhtml.txcを読んだ人以外）にはさっぱりな話題が続いてしまったのも申し訳ない限りです。

それでも、これで現行のXHTMLプラグインで知られている問題点はほぼすべて対処がなされたことになりますから、HTMLCMD登場以降はじめての事実上の安定版ができたという意義は大きいです。

中村さん、おつかれさまでした。