diffの高速化

Unified Formatで表示できるところまで来たのはいいけど、
六千行ほどのファイルに適用したら、表示されるのに20秒以上かかってしまって
使い物にならないので、そのへんをちょこちょこと直す。
編集距離を求める処理自体はO(NP)だから速いんだけど、
肝心のSESの経路を記録する部分がかなりお粗末なのが原因だった。
まだかなり改善の余地はあるだろうけど、
それなりにマシな速度で動くようにはなった。

# 単純にtimeコマンドで計測
./unidiff a.txt b.txt  0.12s user 0.08s system 62% cpu 0.318 total

各ファイルの行数と2つのファイルの差分における追加と削除の数は以下の通り。
あと環境はMacOSX10.5.4、GCC4.3.2で、コンパイルオプションにはO2を指定。

ファイル名と行数	追加	削除
a.txt:6351 b.txt:6463	1426	1314

比較対象としてGNU diffutilsのdiffで実行すると、

diff -u a.txt b.txt  0.01s user 0.02s system 22% cpu 0.151 total

う〜む、倍近い差がある。