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についてはひとまずこれで完成ということで。