前回は構想だけだったので、
ちょっとコードを書いてみました。
参考文献はhttp://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htmで、
ViViの作者による解説です。
処理速度と、メモリ効率を考えながらコードを書いたらかなり汚くなってしまいました。
本当はパフォーマンスとか考えずに綺麗にアルゴリズムを実装するほうがよいのかもしれませんね。
コード解説
アルゴリズムのややこしいコードなので、比較的コメントは多めにしてありますが、
後で自分でソースを読んで理解できる自信がありません。
その上、車輪の再発明的なコードなので、正直オススメしません。読むならSubversionのソースでも読むほうがタメになるのではないでしょうか。
とりあえず、参考文献にあるとおり、エディットグラフの最短経路を探す問題となりますが、
ここでは比較的原始的に経路を探すアルゴリズムで書いてみました。
計算量はO(M*N)となるはず(M,Nは比較対象となるデータの数)。
y方向のループとx方向の2重ループによる構成ですから、比較対象となる２つのデータの数の積だけループがまわります。
ただし、経路情報をメモリしているとメモリまでM*Nのオーダーで必要となりますが、
走査する対象列とその１つ手前の列の情報しか持たないようにすることで、2*Mのメモリ量に抑えています。
経路の情報もその長さは最短でも√M*Nになりますから（完全一致の場合）、これにさきの2*Mの長さを掛けると結構な分量になります。
ルートの分岐点のみ経路を保管し、あとは上の交点から下に下りる経路をとった扱いにして、省略しています。
こんなことをするからソースが複雑になるんですよね…。
インターフェース的には
* @param comparator オブジェクトの比較に用いる
* @param opeIte1 縦軸
* @param opeIte2 横軸
* @return 最短経路情報
*/
public static <T> List<Path> diff(Comparator<T> comparator,
Iterable<T> opeIte1, Iterable<T> opeIte2) {
となっており、比較のためのComparatorと、比較する二つのデータ型を渡します。
データはIterableで渡していますが、実際問題、Listでいいんじゃないかと作ってから思った次第。
Iterableにしたところで配列も渡せるってわけにはいかないんだもん。
経路の情報は右、右斜め下、下の3種の方向とその長さで、いわゆるランレングス方式で表記しています。
これもどういう型がよいか迷ったんですが、迷うぐらいならプロトタイプを書いてしまえ！ということで、
感性で書いてみました。
できれば先の参考文献にあった、O(NP) アルゴリズムで書き直したいところです。
車輪の再発明は勉強にはいいのですが、経済的ではないのでSubversionからソースもってきて終わりにしてしまうかもしれない。
展望
とりあえず、思ったよりも簡単に比較アルゴリズムは書けたので、
あとはコレにいろいろなデータを突っ込むだけといったところです。
一応、Javac tree APIでの構文解析木の取得がわりと簡単に出来たので、
構文解析木のdiffをとる方向性で考えています。
Visitorパターンで探索することになるんで、ちょっととっつきにくいのですが、まぁなんとかなるでしょう。
投稿日時 : 2007年10月20日 21:23