2010年8月17日火曜日

コーディングイディオムの奇妙な慣習

先日仕事で緊急に、他人の作ったVisual Basicのコードを改修するタスクを受け持った。

恥ずかしながら、VBは人生初だったが、Visual Studio様とGoogle様のお力でなんとか凌いだ。確かに言語としての敷居は低い。出だしの瞬間的な生産性はかなり高めだ。静止摩擦係数が低いという感じか。静的に型宣言を要求されるため、Java使いには意外と馴染む。ただ、互換性維持のためなのだろうが、同じことを実現するための関数の系統がいくつもあって、どれを選択すべきなのかわからないことが多かった。MSDNを真面目に読めば書いてあるのかもしれないが。

元のコードは典型的な要リファクタリングコードだった。マーチンファウラー先生曰く「臭う」箇所があまりに多くて鼻が麻痺しそうだった。処理はいくつかの関数に分けられていたが基本的に一本道であり、同じ処理がコードのあちこちに何度も出てくる。やたらとグローバル変数が宣言されている。ローカル変数のスコープが無意味に広い。if文のネストが尋常じゃなく深い。そして何よりも、テストコードが一切存在しなかった、いわゆる「レガシーコード」だ。

いろいろ手をつけたかったが、最終的に断念した。期間があまりに短かった上、仕様が毎日どころか数時間毎に変更されていくためだ。修正箇所を極力限定的にし、テストの項目数を極小にしなければ、どう考えても納期に間に合わなかった。直したくて直したくてウズウズする気持ちを抑えて、最小限の修正で実装を終えた。

結果、バグを作りこんでしまった。テストが甘かったといえばそれまでなのだが、初めから自分が書いていれば発生するはずのない類のバグだった。今回はあまりに酷い例だったが、経験上意外とこういうコードを書く人が多く見られるため、自戒も込めてメモを残しておく。


1. ローカル変数の宣言箇所

これは本当に奇妙なのだが、変数の宣言をサブルーチンの先頭にまとめて行うコードを大変よく見かける。正直メリットを一切思いつかない。ひょっとすると、Cのようなガベージコレクタを持たない言語では、領域を確保した後に開放するのを忘れないようにするために、チェックする箇所を限定するという目的があるのかもしれない。しかしほとんどのローカル変数は対象外だし、Javaを含めてGCを持つ言語では百害あって一利もない。典型的な害は以下のような例だ。

String var = null;
for (...) {
    if (...) {
        var = "foo";
    }
    System.out.println(var);
}

for文の中でしか利用しないにも関わらず、先頭で予め宣言したために変数varがfor文の外のスコープを汚染している。もっと問題なのは、変数varの値がループの1つ前の処理に依存していることだ。上記の例の場合、forループの初回はif文の条件に合致した場合、varの値は"foo"になるが、合致しなかった場合は宣言時に代入したnullになる。2回目もif文の条件に合致した場合は同じく"foo"になるが、合致しなかった場合は初回の結果に依存する。

要するにfor文中の条件分岐のいずれかのルートで、varの代入を忘れると嘘の値になるという厄介なバグを作ることになる。今回僕が作りこんだバグはコレだ。正しく動作させるためには以下のようにする必要がある。

String var;
for (...) {
    if (...) {
        var = "foo";
    } else {
        var = "bar";
    }
    System.out.println(var);
}

このような単純な例で見落とす可能性は低いが、このfor文の中の処理が長くなり、分岐が複雑多岐にわたるようになれば徐々に見落としが発生する可能性が増す。また、代入を忘れた場合もなんらかの値が入っているため、たまたま前ループで正しい値が代入されることでテストを通過してしまう可能性が高い。

このような見落としがそもそも発生しないようにすることは簡単で、以下のようにすれば良い。

for (...) {
    String var;
    if (...) {
        var = "foo";
    } else {
        var = "bar";
    }
    System.out.println(var);
}

変数varをfor文の中で宣言するだけだ。変数がforループ中、毎回宣言し直されるため、前回の値が誤って代入されることは絶対にない。昔はループのたびに変数宣言が行われることによるパフォーマンスの劣化を懸念するような意見があったが、ハードウェアのスペックが十分高くなった現在では、パフォーマンス劣化の危険性がバグを作り込む危険性に吊り合わない。そもそも、現在のJava VMでは上記のように都度宣言する記述を行っても、コンパイラの最適化によってforループの外で宣言する形に修正されるため、パフォーマンスの劣化自体が発生しない。そしてコンパイラが自動的に実行する最適化は、人が都度あれこれ気を使って行う最適化よりも概ね正確で効果的だ。変数は常に最小のスコープで、使うときに宣言すべきだ。

2. 無意味な変数初期化

1.で挙げた修正後のコードを、以下のように書く人もよく見かける。

for (...) {
    String var = "bar";
    if (...) {
        var = "foo";
    }
    System.out.println(var);
}

こちらについては、必ずしもマズいとは言い切れ無い。特に上記のような単純な場合はコード量を減らす効果がある。しかし、僕はこのような書き方はあまり好きじゃない(そもそも上記のような単純な例なら、三項演算子を使えという話になってしまうがそれは置いておいて)。なぜなら上記の場合、if文の条件に合致するときに変数varの値は一旦"bar"によって初期化され、その後"foo"という値になる。この動作は非常に奇妙に感じる。もっと極端な例では以下のようなコードも見たことがある。

for (...) {
    String var = "";
    if (...) {
        var = "foo";
    } else {
        var = "bar";
    }
    System.out.println(var);
}

変数varを宣言した際に、「とりあえず」空文字で初期化しておくのだ。この空文字が実際に使われることは一度もない。空文字の代わりにnullでも同じことだ。宣言時に即初期化しろという強迫観念のようなものが存在するのだろうか。

このような記述は、コンパイラが持っている折角のチェック機構をひとつ潰すことになる。初期化を行わなかった場合、例えば以下のように記述すると、コンパイル時にエラーが発生する。

for (...) {
    String var;
    if (...) {
        var = "foo";
    }
    System.out.println(var);
}

なぜなら、if文の条件に合致しなかった場合に変数varの初期化が行われないため、後でvarを参照しようとしたときに困ってしまうからだ。else文でvarに明示的に値を代入しない限り、コンパイルは通らない。

このような単純な例では恩恵が得られないように感じるかもしれないが、分岐が複雑になっていけばこれに救われる可能性が高くなってくる。ある分岐で、うっかりvarへの代入を忘れてしまったとき、とりあえずvarの初期化をしてしまっていると、そのとりあえずの値が採用されてしまい、コンパイル自体は通ってしまう。その分岐ルートをテストしなければ、間違いに気づかない。最悪、とりあえずの値が期待する値とたまたま一致していると、バグに気づかないことになる。宣言時に初期化を行わなければ、すべてのルートで代入が行われていない限りコンパイル自体が通らない。


結局、1と2両方を心がけることで、作りこんでしまったバグをコンパイラが見つけてくれる。これを利用しない手はない。もしコーディング規約等でこれらの奇妙な慣習が義務付けられているのであれば、規約自体の見直しを行う時が来たということになるだろう。

2010年8月4日水曜日

クラッカー?

日頃から常時iPhoneのネット接続に使っているイー・モバイルのポケットWiFiなのだが、
なんか会社にいるときにふと見ると接続数のカウントがおかしい。1個多いのだ。
変だなーと思って管理画面で調べてみたら、やっぱり僕の知らない接続がある。
管理画面に表示されたMACアドレスが00:24:D6で始まっているので、どうやら
Intel製の無線LANのようだ。たぶん普通のWindowsPCなんだろう。

昔オープンで使っていたら、知らない人に勝手に常時使われていたので
一応暗号化は設定している。WPA/WPA2で暗号化方式はTKIP+AES。
まぁキーが割と短いので総当りされた可能性はあるのだが、
辞書に載っているような単語ではなかったので、かなり意図的な侵入の模様。
そういえば最近WPAのクラック方法が発見されたというのがニュースに
なってたなぁと思って調べてみたらあった。

http://www.itmedia.co.jp/news/articles/0811/11/news083.html

WPAでTKIPの時にクラッキングできるのか?
んー、でもこれは偽のパケットを挿入できるけれども傍受できるわけではない
ようだなぁ。やっぱり総当りだったのか?まだ1ヶ月も経ってないのに。。。

基本的にはiPhoneしかつないでないから今回は良いんだけど、
パケット見られてたわけだよね。気持ち悪いなぁ。
とりあえずSSIDを変えてステルスモードにし、WPA2 AESのみを受け付けるように
設定を変更した。さらにパスワードを長いものに変更。
MACアドレスフィルターも設定した。これでしばらく様子見。
これでもダメだったらどうしよう?もう打つ手が無い。

ちなみにiPhoneがSSIDステルス時に自動接続に対応していないと
思って公開していたのだが、調べてみたらどうやら対応している模様。
公開状態の時に一度でも接続してしまうと、ステルス化したときに自動接続
してくれなくなるようだ。初めからステルス状態だとちゃんと探してくれる。

それにしても、意図的にWiFiデータを傍受するのは犯罪じゃなかったっけ?
ついこの間ドイツでGoogleのストリートビューカーが無線データを記録していて
大問題になっていたような。よしんば偶然ハッキングできたからと言ってそれを
使い続けるのはどう考えても非常識だと思う。

・・・問題は、どうやら、犯人が、社内にいるようなんだよね。。。
勤続10年ちょい。これまでに社員に盗まれたものの一覧。

・傘
・ノートPCのACアダプタ
・WiFi パスワード

どれも他人の物だとはっきり分かっていて犯行に及んでいるところが
タチが悪いなぁ。しかもだんだんエスカレートしてる。
次は現金かなぁ。現金に手を出されたら、さすがにオー人事 オー人事かなぁ。。。

2010年5月10日月曜日

ジェネリックスと可変長引数の微妙な関係

Javaのジェネリックス(総称)は、利用することはあってもAPIとして公開することはあまりなかったためこれまで気づかなかったが、可変長引数と組み合わせた場合に少々面倒な問題を持っていることに気づいたのでメモしておく。

JDK5でさまざまな新機能が追加されたが、ジェネリックスはその1つ。
一言で言ってしまえば、クラスやインタフェース、メソッドに型をパラメタとして定義できる機能である。
具体的な例とメリットはCollectionフレームワークでしばしば説明されている。

java.util.List<E>の例を以下に示す。
JDK5以前のコードは以下のような感じになる。


public void processMyClasses(List list) {
    for (Iterator iter = list.iterator(); iter.hasNext(); ) {
        MyClass myClass = (MyClass) iter.next();
        // myClass に対して何か処理
    }
}

for文の中で、MyClassへの明示的なキャストを行っている。
list引数の要素がすべてMyClassにキャストできるオブジェクトであることを期待して実装しているが、もし誤った要素が入っていれば、キャスト時にClassCastExceptionが発生してしまう。
このバグはコンパイル時には発覚しない。実行して初めて(最悪の場合バグにヒットする処理が行われるまでかなりの時間が経ってから)問題があることが判明する。
例外はここで発生するが、バグを作り込んだ箇所(おかしな要素をaddしたところ)は別の場所であり、デバッグがやっかいになる。
もちろん例外が発生しないようにinstanceof演算子で型チェックすることができるが、冗長であり、可読性を下げることになる。またデバッグが困難であることに変わりはない。

JDK5以降は、同じ処理を以下のように記述できる。

public void processMyClasses(List<MyClass> list) {
    for (Iterator<MyClass> iter = list.iterator(); iter.hasNext(); ) {
        MyClass myClass = iter.next();
        // myClass に対して何か処理
    }
}

for文の中でMyClassへの明示的なキャストが必要なくなっているのがミソだ。型パラメタを指定することで、その型以外の要素がリストに含まれないことがコンパイル時に保証される。

さらに、型パラメタを指定することで、同じくJDK5で導入された拡張for文を利用することができるようになる。

public void processMyClasses(List<MyClass> list) {
    for (MyClass myClass : list) {
        // myClass に対して何か処理
    }
}

型パラメタを指定しないList(原型)を使用すると、拡張for文の左側の型はMyClassではなくObjectでしか宣言できなくなる。
後で明示的にキャストしなければMyClassのメソッドを使用することができない。
バグ等による型保証の問題についても、通常のfor文と同様である。

このようなList<E>の特徴は、型Eの配列(E[])と非常に似ている。しかし、ジェネリックスと配列では、2つの点で大きく異なる。

1つはジェネリックスはerasureで実装されているという点である。つまりジェネリックスによる型チェックはコンパイル時に行われ、その後抹消される。コンパイルされた後のバイトコードにはその情報は残らない。これはバイトコードをデコンパイルするとはっきりするだろう。上記の例でいうと、デコンパイルされたコードのListはすべて原型が用いられ、明示的なキャストが自動的に追加される。つまり、JDK5以前のコードとほぼ同様のバイトコードができあがる。

もう1つの大きな違いは、配列は共変(covariant)であるのに対し、ジェネリックスは不変(invariant)であるということだ。共変とは、クラスBがクラスAのサブクラスであった場合、クラスBの配列はクラスAの配列に暗黙的にキャストできることを意味する。

class A {...}
class B extends A {...}
であるとき:

B[] b = new B[10];
A[] a = b;

上記のコードはエラー無くコンパイルできる。これに対しジェネリックスは不変であるため、同様な記述が許されない。

List<B> b = new ArrayList<B>();
List<A> a = b;

上記のコードはコンパイルできない。
共変は一見直感的であり、便利なような気がするが、Javaの配列は参照であるが故にやっかいな問題を引き起こす。
例えば以下のコードはコンパイル時にはエラーが発生しない。

class A {...}
class B extends A {...}
class C extends A {...}
であるとき:

B[] b = new B[10];
A[] a = b;
a[0] = new C();
B tmp = b[0]

しかし、上記コードを実行すると、配列bの1番目の要素を取り出そうとしたときに例外が発生する。これはやっかいな問題である。上記コードであれば、例外の発生する箇所からさかのぼって、配列bにおかしな値を代入した犯人を突き止めればよいが、これが別メソッドの引数であったりすると追いかけるのが困難になってくる。
何よりバグがコンパイル時に自動的に見つからず、実行時に初めて発覚する可能性があるという点がやっかいだ。
もしジェネリックスが共変を許容すると、この配列の問題と全く同じことがジェネリックスでも起こる。せっかくの型保証が不完全になってしまうのだ。

以上のような大きな違いがあるため、配列とジェネリックスは非常に相性が悪い。原則としてコードの中に混ぜない方がよい。Joshua Bloch著 "Effective Java 第2版" の項目25では、"配列よりリストを選ぶ"ことが推奨されている。
共変が引き起こす上記のような問題を避けるため、例えば、型パラメタを指定した型の配列をnewすることはできない。"new ArrayList<String>[10]" はコンパイルエラーになる。

さて、いよいよ本題に入るが、ジェネリックスや拡張for文同様、JDK5で新たに導入された機能として、可変長引数がある。これはC言語にあるprintf文の様な書式指定の出力を実現するために導入されたといっても過言ではないが、その他の場面でも非常に便利な機能である。
ところが、これをジェネリックスと組み合わせた場合にちょっとやっかいなことが起こる。

可変長引数とジェネリックスを組み合わせたサンプルとして、複数のリストを引数として内容をマージして返すジェネリックメソッドを考える。まずは2つのリストの例。

static <E> List<E> concat(List<E> list1, List<E> list2) {
    List<E> result = new ArrayList<E>();
    result.addAll(param1);
    result.addAll(param2);
    return result;
}

これはなんの問題も無い。これを2つ以上のリストを引数とする可変長引数に修正したのが以下になる。

static <E> List<E> concat(List<E> list1, List<E> list2, List<E>... lists) {
    List<E> result = new ArrayList<E>();
    result.addAll(list1);
    result.addAll(list2);
    for (List<E> list : lists)
        result.addAll(list);
    return result;
}

最低2つのリストを要求するため、可変長引数は3番目に追加されている。これ自体はなんの警告もなくコンパイルできる。
しかし、このメソッドを利用しようとすると、コンパイル時に警告が出る。

List<String> list1 = Arrays.asList("a", "b", "c");
List<String> list2 = Arrays.asList("d", "e", "f");
List<String> list3 = Arrays.asList("g", "h", "i");
List<String> result = concat(list1, list2, list3);

上記コードをコンパイルすると、以下の警告が出力される。

注:Xxx.java の操作は、未チェックまたは安全ではありません。
注:詳細については、-Xlint:unchecked オプションを指定して再コンパイルしてください。

注記の通り、-Xlint:uncheckedオプションを指定してコンパイルし直すと、より詳細な警告が出力される。

Xxx.java:xx: 警告:[unchecked] 可変引数パラメータに対する型 java.util.List<java.
lang.String>[] の総称型配列の無検査作成です。
    List<String> result = concat(list1, list2, list3);
                                               ^
警告 1 個

コード上はきちんと型指定されているように見えるのに、総称型配列の無検査作成、つまり原型を使用していると警告が出る。これはなぜだろうか。
答えはコードをデコンパイルしてみると分かる。上記のconcatメソッド呼び出し箇所は、以下のようにコンパイルされている。

concat(list, list1, new List[] { list3 });

可変長引数は、そのすべての引数を含む配列に変換され、呼び出しを行っている。
ここで思い出してもらいたいのだが、共変の問題のため、型パラメタを指定した型の配列をnewすることはできない。従って上記の引数を、"new List<String>[] { list3 }"というように記述することはできない。デコンパイルしたコードはすべての型パラメタが抹消されているが、上記の可変長引数部分は始めから型パラメタが指定されていない(原型)ということになる。このため、コンパイラが型安全でないことを警告しているのだ。
結局可変長引数が配列で実装されているため、ジェネリックスとの相性の悪さが露呈することになった。

ジェネリックスを使用してAPIを実装する場合、どうしても型安全でない警告が発生してしまうことがある。
しかしそれはたいていの場合内部の実装において発生する警告であり、APIを利用する側からは見えない。
上記の問題はAPIを利用する側で警告が発生してしまう。
対策としてはAPI自体を別の形に修正するか、利用者に逐一無検査警告を取り除いて貰うしかない。
無検査警告を取り除くには、以下のようにSuppressWarningsアノテーションを指定する。

@SuppressWarnings("unchecked")
List<String> result = concat(param1, param2, param3);

SuppressWarningsアノテーションは、ローカル変数の他にもメンバ変数やメソッド、クラスなどに指定することができる。
しかし、このアノテーションを指定することは、いわばクサいものに蓋をすることであり、必要以上に指定してしまうと本当の問題があった場合にそれを見えなくしてしまう。指定は極力ローカルにとどめるべきだ。
上記のようにローカル変数に対して個別に指定するのが望ましい。また、なぜ警告を抑制して良いのかについて、コメントを入れておくことがEffective Javaでは推奨されている。

これは非常にカッコ悪いが、ちょっとどうしようもない問題のようだ。
もし私がなにか勘違いしているだけなのか、あるい根本的な対策があるならばぜひ教えていただきたい。

2010年3月15日月曜日

Google DevFest 2010 パッチワーク問題を解いてみた

ガワだけ作って1年くらい放置していたブログだが、唐突に始めてみたりする。
ブログの語源をたどってみると、ウェブ上のログという意味でウェブログと呼ばれていたのが縮められたようだ。というわけでこれはただの記録。あなたにとってなんの役に立たなくても時間の返品は出来かねます。

去る3/12にベルサール汐留で開催されたGoogle DevFest 2010 Japanに参加してきた。このイベントは参加証をゲットするためにクイズに挑戦しなければならないという斬新な試みがなされていた。
クイズの内容はいろいろなものがあったが、いくつかプログラムを書かなければ解けない問題があった。パッチワーク問題はそのひとつ。以下に問題を引用する。

ここに "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。 これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。
まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。
そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト(600 行)として答えてください。
以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。
例1:
入力
ABAAB
BABAA
BAABB
ABABB
BABAA
塗りつぶしたところ.
AB__B
B_B__
B____
AB___
BABAA
答え
2
3
4
3
0
例2:
入力
BAABBABBBB
BAABABBBBB
BBAABABBBA
BABBBABBAA
BBABAAABAB
BABABBBAAA
AABBBAAAAA
BAAAAAABBB
AAABABBAAB
AABAABBABA
塗りつぶしたところ.
BAABBABBBB
BAABABBBBB
BBAABABBB_
BABBBABB__
BBABAAAB_B
B_BABBB___
__BBB_____
B______BBB
___B_BBAAB
__B__BBABA
答え
0
0
1
2
1
4
7
6
4
4 

問題文を一目見て、ぷよぷよかと。
マス目毎に再帰呼び出しを行えば、とりあえず解けそうだなと思った。
何の言語で書いてみようかと思ったが、脳ミソが溶けていてJava以外の言語で書ける気がしなかったので仕方なくJavaで書いた。以下がそのプログラム。

package devfest;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;

/**
 * @author hideaki
 *
 */
public class PatchWork {

    private static final Logger logger = Logger.getLogger(PatchWork.class.getName());

    private static enum Type {
        A, B
    }

    /**
     * パッチワークテーブルのマス目の一要素を表すクラス。
     */
    private static final class Element {
        /** この要素の一つ前の行の要素。無い場合はnull */
        Element up;
        /** この要素の一つ後の行の要素。無い場合はnull */
        Element down;
        /** この要素の一つ前の列の要素。無い場合はnull */
        Element left;
        /** この要素の一つ後の列の要素。無い場合はnull */
        Element right;

        final Type type;

        /**
         * 上下左右に同じ文字の要素のつながった数。
         * 未調査の場合はnull。
         */
        Counter counter = null;

        Element(Type type) {
            if (type == null)
                throw new NullPointerException();
            this.type = type;
        }
    }

    /**
     * 上下左右に同じタイプの要素がいくつつながっているかを表すクラス。
     */
    private final class Counter {
        private int count = 0;
        /**
         * カウントを1つ増やす。
         * 親インスタンスのmaxメンバを参照し、countがmaxの値を超えた場合、更新する。
         */
        void increment() {
            count++;
            if (count > max)
                max = count;
        }
        int getCount() {
            return count;
        }
    }

    /** パッチワークテーブル */
    private final List<List<Element>> table;

    /** 最大連結数 */
    private int max = 0;

    /**
     * @param args 第1引数はロードするファイル名
     */
    public static void main(String[] args) throws Exception {
        PatchWork patchWork = new PatchWork(args[0]);
        patchWork.search();
        patchWork.makeResult();
    }

    /**
     * コンストラクタ。
     * 指定されたファイルを読み込み、パッチワークテーブルを完成させる。
     *
     * @param filename ロードするファイル名
     * @throws IOException ファイルのロードに失敗した場合
     */
    public PatchWork(String filename) throws IOException {
        List<List<Type>> typeTable = loadFile(filename);
        List<List<Element>> result = new ArrayList<List<Element>>();
        List<Element> lastLine = null;
        for (List<Type> typeList : typeTable) {
            List<Element> thisLine = new ArrayList<Element>();
            Element lastElement = null;
            for (int i = 0; i < typeList.size(); i++) {
                Element thisElement = new Element(typeList.get(i));
                if (lastElement != null) {
                    // 前後列の関連付け
                    lastElement.right = thisElement;
                    thisElement.left = lastElement;
                }
                if (lastLine != null) {
                    // 前後行の関連付け
                    Element upElement = lastLine.get(i);
                    upElement.down = thisElement;
                    thisElement.up = upElement;
                }
                thisLine.add(thisElement);
                lastElement = thisElement;
            }
            result.add(Collections.unmodifiableList(thisLine));
            lastLine = thisLine;
        }
        table = Collections.unmodifiableList(result);
    }

    /**
     * ファイルを読み込んで、対応するTypeのテーブルを作成する。
     *
     * @param filename ロードするファイル名
     * @return Typeテーブル
     * @throws IOException ファイルのロードに失敗した場合
     */
    private List<List<Type>> loadFile(String filename) throws IOException {
        BufferedReader reader = null;
        try {
            List<List<Type>> result = new ArrayList<List<Type>>();
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
            for (String line; (line = reader.readLine()) != null; ) {
                List<Type> row = new ArrayList<Type>();
                for (char c : line.toCharArray())
                    row.add(Type.valueOf(String.valueOf(c)));
                result.add(Collections.unmodifiableList(row));
            }
            return Collections.unmodifiableList(result);
        } finally {
            if (reader != null)
                reader.close();
        }
    }

    public void search() {
        for (List<Element> line : table)
            for (Element element : line)
                if (element.counter == null)    // その要素が未判定の時
                    traverse(element.type, new Counter(), element);
        logger.info("max:" + max);
    }

    /**
     * 判定対象が、指定されたタイプと同じタイプのエレメントかどうかを判定する。
     * 判定対象がnullの場合、判定対象が判定済みの場合、または判定対象が指定されたタイプと異なる場合は終了する。
     * それ以外の場合、その上下左右の要素を再帰的に判定する。
     *
     * @param type 判定対象と比較するタイプ
     * @param counter エレメントが保持するカウンター
     * @param element 判定対象
     */
    private void traverse(Type type, Counter counter, Element element) {
        assert type != null && counter != null;
        if (element != null && element.counter == null && element.type == type) {
            element.counter = counter;
            counter.increment();
            traverse(type, counter, element.up);
            traverse(type, counter, element.down);
            traverse(type, counter, element.left);
            traverse(type, counter, element.right);
        }
    }

    /**
     * 各行のmax要素を数え、標準出力する。
     */
    public void makeResult() {
        StringBuilder sb = new StringBuilder();
        for (List<Element> line : table) {
            int count = 0;
            for (Element element : line) {
                if (element.counter.getCount() == max) {
                    count++;
                    sb.append('_');
                } else {
                    sb.append(element.type);
                }
            }
            System.out.println(count);
            sb.append('\n');
        }
        logger.info(sb.toString());
    }
}

ファイルから読み込む挙動とElementリストの初期化を分けたのには、特に深い意味はない。読み込み元がファイル以外になることも考えて処理を分離しただけである。
処理としては単純で、あるElement(マス目)の上下左右が自分と同一であるかどうかチェックし、同一であればその先を再帰的に調べていくだけである。つながった領域と認識されたElement同士は、Counterインスタンスを共有する。Counterインスタンスはその領域のつながった数を表す。ついでにElementがCounterインスタンスを持つことが、そのElementがチェック済みであることを意味している。後で最大値をチェックするのが面倒だったので、ちょっとズルをしている。

この解法で気になるのは、再帰処理のスタックがどこまで積まれるか、である。最悪の場合(全マスがAまたは全マスがB)600x600=360,000スタックが積まれることになり、これは流石にオーバーフローするだろう。したがって、これは問題のマス目の性質が比較的良心的であることを期待している。

さて、DevFestで(正確にはDevFestお開き後に同じ会場で催されたGTUG主催のLightening Talkで)問題の答え合わせがあり、このパッチワーク問題にはUnion-Findと呼ばれるアルゴリズムを利用するのが良いという話があった。なので帰って早速調べてみた。

一言で言ってしまうと、このアルゴリズムは、ある集合を互いに素な部分集合に分類するのに使える。パッチワーク問題でいうある集合とは600x600のマス目すべてであり、互いに素な部分集合とは隣同士がつながっている部分である。ちなみにここで言う互いに素とは、同じ要素が複数の部分集合に含まれないことをさす。要するにある隣同士がつながった塊と、別の塊の両方に、同じマス目が含まれることが無いことを意味している。
同じ部分集合に含まれる要素をN-ary treeで保持し、root要素を使って管理することで高速に処理しようという狙いがある。

用意しなければならない関数は2つ、あるtreeのrootを見つけるfindと2つのtreeをマージするunionである。unionは片方のtreeのroot要素の直下に、もう片方のroot要素が結合されることでなされる。treeが深いほどrootを見つける処理が増えるので、treeはなるべく浅い方がいい。なのでunion時には2つのtreeの深さを比べて浅いtreeが深いtreeの下に入るようにする。

というわけで、パッチワークプログラムをUnion-Findアルゴリズムを利用するように改造したのが以下である。

package devfest;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;

public class PatchWork2 {

    private static final Logger logger = Logger.getLogger(PatchWork2.class.getName());

    private static enum Type {
        A, B
    }

    /**
     * パッチワークテーブルのマス目の一要素を表すクラス。
     */
    private static final class Element {
        /** この要素の一つ前の行の要素。無い場合はnull */
        final Element up;
        /** この要素の一つ前の列の要素。無い場合はnull */
        final Element left;

        final Type type;

        private final UnionFind unionFind;

        Element(Type type, Element up, Element left) {
            if (type == null)
                throw new NullPointerException();
            this.type = type;
            this.up = up;
            this.left = left;
            unionFind = new UnionFind();
        }

        void union(Element element) {
            unionFind.union(element.unionFind);
        }

        int size() {
            return unionFind.size();
        }
    }

    /** パッチワークテーブル */
    private final List<List<Element>> table;

    private int max;

    /**
     * @param args 第1引数はロードするファイル名
     */
    public static void main(String[] args) throws Exception {
        PatchWork2 patchWork = new PatchWork2(args[0]);
        patchWork.search();
        patchWork.makeResult();
    }

    /**
     * コンストラクタ。
     * 指定されたファイルを読み込み、パッチワークテーブルを完成させる。
     *
     * @param filename ロードするファイル名
     * @throws IOException ファイルのロードに失敗した場合
     */
    public PatchWork2(String filename) throws IOException {
        List<List<Type>> typeTable = loadFile(filename);
        List<List<Element>> result = new ArrayList<List<Element>>();
        List<Element> lastLine = null;
        for (List<Type> typeList : typeTable) {
            List<Element> thisLine = new ArrayList<Element>();
            Element lastElement = null;
            for (int i = 0; i < typeList.size(); i++) {
                Element upElement = (lastLine == null) ? null : lastLine.get(i);
                Element thisElement = new Element(typeList.get(i), upElement, lastElement);
                thisLine.add(thisElement);
                lastElement = thisElement;
            }
            result.add(Collections.unmodifiableList(thisLine));
            lastLine = thisLine;
        }
        table = Collections.unmodifiableList(result);
    }

    /**
     * ファイルを読み込んで、対応するTypeのテーブルを作成する。
     *
     * @param filename ロードするファイル名
     * @return Typeテーブル
     * @throws IOException ファイルのロードに失敗した場合
     */
    private List<List<Type>> loadFile(String filename) throws IOException {
        BufferedReader reader = null;
        try {
            List<List<Type>> result = new ArrayList<List<Type>>();
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
            for (String line; (line = reader.readLine()) != null; ) {
                List<Type> row = new ArrayList<Type>();
                for (char c : line.toCharArray())
                    row.add(Type.valueOf(String.valueOf(c)));
                result.add(Collections.unmodifiableList(row));
            }
            return Collections.unmodifiableList(result);
        } finally {
            if (reader != null)
                reader.close();
        }
    }

    public void search() {
        for (List<Element> line : table) {
            for (Element element : line) {
                compare(element, element.up);
                compare(element, element.left);
            }
        }
        logger.info("max:" + max);
    }

    private void compare(Element thisElement, Element otherElement) {
        assert thisElement != null;
        if (otherElement != null && otherElement.type == thisElement.type) {
            thisElement.union(otherElement);
            int tmp = thisElement.size();
            if (tmp > max)
                max = tmp;
        }
    }

    /**
     * 各行のmax要素を数え、標準出力する。
     */
    public void makeResult() {
        StringBuilder sb = new StringBuilder();
        for (List<Element> line : table) {
            int count = 0;
            for (Element element : line) {
                if (element.size() == max) {
                    count++;
                    sb.append('_');
                } else {
                    sb.append(element.type);
                }
            }
            System.out.println(count);
            sb.append('\n');
        }
        logger.info(sb.toString());
    }
}

package devfest;

public final class UnionFind {

    /** この要素のroot。経路圧縮のためにメンバ定義する。 */
    private UnionFind root = this;

    /** この要素の親要素。この要素がrootの場合はnull */
    private UnionFind parent;

    /** この要素が含まれるtreeの深さを表す。自身がroot要素である場合に限り意味を持つ。 */
    private int rank;

    /** この要素が含まれるtreeの構成数を表す。自身がroot要素である場合に限り意味を持つ。 */
    private int size = 1;

    /**
     * この要素が含まれるtreeのrootを見つけて返す。
     *
     * @return root要素
     */
    public UnionFind find() {
        while (root.parent != null)
            root = root.parent;
        return root;
    }

    /**
     * この要素が含まれるtreeと引数で指定された要素が含まれるtreeを結合する。
     * 但し、両者のrootが同一である場合(すでに結合されている場合)何も行わない。
     *
     * @param other 結合する相手のtreeに含まれる要素
     */
    public void union(UnionFind other) {
        UnionFind thisRoot = this.find();
        UnionFind otherRoot = other.find();
        if (thisRoot != otherRoot) {
            if (thisRoot.rank > otherRoot.rank) {
                otherRoot.parent = thisRoot;
                thisRoot.size += otherRoot.size;
            } else {
                thisRoot.parent = otherRoot;
                otherRoot.size += thisRoot.size;
                if (thisRoot.rank == otherRoot.rank)
                    otherRoot.rank++;
            }
        }
    }

    public boolean isRoot() {
        return parent == null;
    }

    public int size() {
        return find().size;
    }
}

再利用の予定は今のところないが、純粋なUnion-Findアルゴリズム部分は別クラスとしている。

このアルゴリズムの計算量は O(A(n)) となるらしい。Aはアッカーマン関数の逆関数。この辺になるとまともな文献を漁らないとなんのことか分からないが、かなりゆっくり増加する関数らしい。