タグ: import

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

• 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登場以降はじめての事実上の安定版ができたという意義は大きいです。

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

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

念が通じました！　不具合の原因についての詳細な解説も読めます。……なるほど、GetKc関数に値を返さない道すじがありましたか。……って昨日はそのあたり（GetKc関数付近）を読んでたはずなんですが、どうやら目が節穴だったようです。

じつは情けないことがもうひとつ。僕の調べた限りではこれも立派な原因のうちの一つですと突っ込まれてしまいましたが、昨日の記事で「meta要素のhttp-equiv属性が二重引用符で囲まれていな
いと起きるのかな？」と考えたんですが、いまいじってみるとどうもそうでもないみたい、と書いたことについて。

その後ynp4の解説を読んでいたら、急に思いあたるふしが出てきたので、オリジナルだと信じきっていたxhtml.txcの変更履歴をセーフファイルで確認してみたら、4月6日に編集したという痕跡が。変更内容は__on_txFrameNew関数内の以下の部分、

GetHeaderStr(text,"meta>[^>]*http-equiv=¥"Content-Type¥"","content",sz,CCHWORD,0,0)

を次のようにというもの。

GetHeaderStr(text,"meta>[^>]*http-equiv=¥"?Content-Type¥"?","content",sz,CCHWORD,0,0)

……すみません、自分で対処して忘れてたみたいです（苦笑）。当時のHTMLソースをひっぱりだしてきても再現しないのも当然です（とはいえそのときもGetKc関数の問題点には気づいてなかったんですが）。お騒がせしました……。

ということは、この状態でynpのパッチもあてていたわけで、考えてみると恐ろしいことなんですが……。

もとい、本題。ここまで愚挙を露呈しておいてからいうのも説得力に欠けるんですが（笑）、xhtml.txcは（というかその前身のhtmlcmd.txcから）GetKcのほかにも返り値の型が違ってたり、値を返さない関数で値をreturnしてたり、というのがけっこうあるので、このさいynp版でそういうのを一掃してしまってはどうでしょうか。

少なくとも、ynp4版xhtml.txcでは5095行目にある、wndImeSetOpen(hwnd,0);というのはwndImeSetOpen(text->hwndtext,0);でないとまずいと思うので（hwndは宣言されてないのでint型に自動定義されている）ここだけでも……。