diff
(追記)この日の日記で紹介したO(ND)のdiffクラスより高速なO(NP)のdiffを書きました。id:siokoshou:20070315を参照。(追記終わり)
コード中でdiffを取りたかったので.NETなdiffクラスがないかと探してみたら、とてもよいものを見つけました。
deってことでドイツの方らしく、コードが大変几帳面でおもしろい(ステレオタイプな見方だけど)。Danke.
スピードはGood。作者によるとまだ最適化の余地はあるようですが、それでも非常に早いコードです。diffのアルゴリズムに詳しくなければこれより早いコードは書けません。.NET1.1らしく、Hashtableを使ってます。(追記)id:siokoshou:20070309 でさらに速くした。(追記終わり)
v5で public Item [] DiffText(string TextA, string TextB) を static に変更し忘れてますね。
サイト上で過去のバージョンとのdiffを見ることができて、これは自身のdiffを使ってるっぽい。ちょっとC風なコードですね。
２つのテキストの行の合計がintの範囲を超えるとマズイ作りだけど、2007年現在のメモリ量から言うと問題ないですね。
出力形式が扱いづらいんですが、共通項も出力するように改造するか、あるいは内部形式のDiff.DiffDataを直接扱えばきっと楽です。
CodeProjectでもC#のdiffの記事を２つ見つけたけど、こちらは総当りで比較するのか遅いのでお勧めできません。コードがイマイチだったんで、あまり読んでないけど。
diffのアルゴリズムについてぐぐるとviviの作者さんのとこがよく参照されてるようです。vivi昔使っていました。vi派です。
上記のdiffはここにあるO(ND)アルゴリズムです。Unixのdiffを書いたときの論文っぽい。上記のサイトから論文のPDFへのリンクがあります。GNUのdiffもちらっと見たら、同じアルゴリズムのようです。
WikipediaのdiffやLCS最長一致シーケンス列も良い資料です。普段からdiffを多用していながら、diffのアルゴリズムって気にしたこともなかったんですが、実に奥深い世界に繋がってておもしろいですねぇ。
ところで、気になるのは2倍早いというO(NP)なアルゴリズムのほう。インターネットアーカイブから論文を見つけました。ほとんど読んでませんが…。
実装を探してみるとRubyによる実装がありました。Rubyよくわかってないので、Rubyらしいところがわかりません…。
もう少し調べるてみるとSubversionがO(NP)とのこと。バージョン管理システムはdiffの上に成り立っているんで、diffの質は重要です。Cなのでコードを読んでみると…。これは本当に凄い凄いコードです！輝いて見えますｗ Guruが書くとCはこうなるのかって思い知らされました！Cなのにかなりきれいでテクニック満載。すげ〜すげ〜よ、これは、マジで…。プログラマを使い捨てていたらこんなコードを書ける人は生まれませんよ、なんて。
libsvn_diffの下あたりがdiff。論文のコードのpのループの最後のsnakeがないのはどうしてなんだろう？Rubyのコードにもない。(追記)わかった。擬似コードの2つ目のループに含めただけだった。(追記終わり)文字列をRing状のリンクリストにし、最後に番兵をつけて論文のコードにさらに磨きをかけてます。
ぼーっと読んでいてもよく分からないんでC#に移植してみました。ちまちまと移植してなんとか動いてますが、やっぱりまだ分からないところが多かったり(^^;
公開してもいいんでしょうか、これ。ライセンス読んでもよくわかりません。移植はどういう扱いになるんだろ？公開しても良いなら、ここにぺたんと貼り付けるんですが。どなたか詳しい方がいらっしゃいましたら教えてください。
気になるスピードですが、不満です。上記O(ND)のdiffより１割程度早いだけでした。早くはなっているものの、期待したほどじゃないのが、ね。元のSubversionのコードはファイルから読み込むようになっているところを、O(ND)のdiffを真似てstringを受けてハッシュ化して比較するように変更したんだけど、このあたりの速度が気になるところ。まあ、なにはともあれ速度は計測しないとね。そのうちまたちびちびと調べてみます。
今日のびっくりは、2chでよく見る「一方ロシアは鉛筆を使った」のネタ元が珠玉のプログラミングだったこと。コラム１の最後の問題でした。文言は違いますが。
