2002-06-25

XHTMLプラグイン(+ynp5)での「img要素挿入ダイアログにダイアログにaltとtilte属性の入力欄が必要か?」問題について(奈良県奈良市某所、2002年6月22日の独り言、およびFinal β Laboratory、2002/06/23(Sun) 更新履歴を参照のこと)。

altについては見米さんと同一見解(挿入後のカーソル位置がalt上なのでそこで書いてね)なんですよねー。本文から持ってくることも多いので、ダイアログ上よりWZの編集画面上の方が書きやすいです。

img要素にはalt属性をつけましょう、という話それじたいはもうラディカルでもなんでもなくなりましたけど、代替テキストという役割を考えると、イメージを選ばせた時点でそれに代わるテキストも同時に要求してくるというのは、教育的には(笑)いいんじゃないですかね。タグ出力時にalt属性の箇所にカーソルが来ているという仕様は渋くて素敵なんですが、なんというか、通好みすぎると感じなくもありません(笑)。ダイアログで入力しなくてもalt=""というコードは出力されるわけですから、エディタ側でのコピー&ペーストの妨げにはならないかな、とも思いますし。

……とかいってみるテスト(笑)。「もう少しほかの人の意見も聞いてみたいかなあ」なんて言われるのでつい反応してしまいました。個人的にも、付いてくれると、嬉しいかな、なんて。

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*型にまたキャスト、とかしてました。

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

2002-06-22

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

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

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

2002-06-21

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

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

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

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

2002-06-19

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

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

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

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