今更ですが、Googleの入社試験

最近数学ガールの影響で、論理クイズにはまっています。
5人の海賊で金貨を山分けする問題とか、5人の奴隷を使って毒入りの樽を探しあてる問題とか、面白い問題があって楽しんで解いています。
で、昔挑戦して解けなかったGoogleの入社試験の問題があったなー、と思い出してたので、また挑戦してみることにしました。
↓の問題です。

ある村では100組の夫婦がいて、夫は全員浮気をしたことがあります。
この村の妻は自分以外の夫が浮気をしたら、それをすぐに知ることができます。
またこの村には掟があって、妻は自分の夫の浮気を知ったらその日の内に夫を殺さなければいけません。
この村の妻は決してその掟を破りません。
ある日村の女王が全員の前でこう言いました。「この村の夫の最低一人は浮気をしている。」
さて、この村に何が起こるでしょうか?

解いてみたら非常に面白かったので、自分の出した回答を晒しておきます。

では、挑戦。

以下では、

  • 浮気経験のある夫 = 黒夫
  • 浮気経験のない夫 = 白夫

とします。


まず、浮気していたのが1人だけだった場合について考えます。
妻は自分の夫以外の浮気がすぐにわかるので、

  • 黒夫の妻( 1人) ⇒ 黒夫だとわかっている人数:0人
  • 白夫の妻(99人) ⇒ 黒夫だとわかっている人数:1人

となります。
この状態で女王の宣告があれば、黒夫の妻はすぐに自分の夫が浮気をしていることがわかります。
他の99人が白なのは分かってるので、黒の可能性があるのは自分の夫だけですから。
よって、その日のうちに黒夫は殺されることになります。


次に、浮気していたのが2人だった場合について考えます。

  • 黒夫の妻( 2人) ⇒ 黒夫だとわかっている人数:1人
  • 白夫の妻(98人) ⇒ 黒夫だとわかっている人数:2人

となります。
この状態で女王の宣告があっても、黒夫の妻から見て浮気している人が1人いて、その人のことを言っている可能性もあるため、1日目は何も起こりません。
しかしもし黒夫が1人なら1日目に殺されるのはずなので、何も起こらないで2日目を迎えたことにより黒夫の妻にも浮気をしていたのが1人ではなかったことが分かります。
その他に浮気をしている可能性があるのは、自分が浮気をしているかどうか知ることができない、自分の夫以外あり得なくなります。
よって、2日目に2人の黒夫は殺されることなります。


浮気が3人だった場合には、

  • 黒夫の妻( 3人) ⇒ 浮気したことがわかっている人数:2人
  • 白夫の妻(97人) ⇒ 浮気したことがわかっている人数:3人

となります。
もし浮気をしているのが2人なら、2日目に殺人が行われるのは上で述べたとおりです。
しかし2日目に何もおきないので、浮気していたのが2人ではなかったことが黒夫の妻にもわかり、3日目に黒夫3人が殺されます。


・・・とまあ、ここまで書けば充分でしょう。
妻の立場からすると、n人の黒夫が見えている場合、自分の夫が白夫ならばn日目に殺人が起こることになります。
もしそれが起こらなければ自分の夫が浮気していることが分かるので、n+1日目に掟により夫を殺すことになります。
帰納法により何人でもこの法則が成り立つので、この村の場合は女王の宣告から100日目に全ての夫が殺されることになります。

面白いポイント

この問題、パッと聞いたときには「妻が既に知っている情報を女王が与えただけなんだから、何も起こらないんじゃね?」と考えそうです。
しかし、実は全妻に対して、
「もし浮気しているのが1人だけだったら、その日のうちに殺人が起こる」
という情報を与えたことになります。
この情報が引き金になって連鎖反応が起こり、結局全ての夫が殺されることになるとは、直感だけではなかなか分かりません。

コンピュータの問題に関わっている人なら、同じような事態に遭遇したことがあるのではないでしょうか?
直感では何も問題がなさそうに思えたプログラムの変更・仕様の変更などが、巡りめぐってトンでもない事態を引き起こしてしまったことは、誰でも一度は経験があると思います。
このテストは、そういった問題への対処できる論理思考力が備わっているのかを見るための問題なんだと思います。

おまけ

せっかくなので、黒夫達を救う方法について考えてみました。
妻は殺害が行われたかどうかでしか、自分の夫が黒夫かどうかを知ることができません。
とすれば、殺害を行えなくするか、殺害が行われても妻はそのことを知ることができなくなれば、この村に再び平和が訪れます。

案1.初日に、誰か1人死ぬ

これが発生したら村は救われます。死ぬのは夫でも妻でも構いません。
死んでしまった黒夫は殺せないですし、死んでしまえば黒夫を殺すこともできないからです。
ようするに、「もし浮気しているのが1人だけだったら、その日のうちに殺人が起こる」という条件を、殺人を行えなくすることで崩しています。
n日が経過するとn人が死んでくれないと連鎖が止まらないので、初日に発生するのがベストです。
でも、これを意図的にやろうとすると誰かを殺さないといけなくなります。
・・・なんかヤなので、もう少し平和的な手を考えてみます。

案2.初日に、一組の夫婦に旅に出てもらう

こちらの方がより平和的解決ですね。旅に出た夫妻が殺人を行ったかどうかがわからない状態を作り出しています。
ただし、旅先から帰ってきてしまうとまた連鎖が始まってしまうので2度と帰れませんが・・・。
あ、でもこれって白夫の夫婦を旅に出しても意味ないので、

  • 自分たち夫婦が旅に出て行く組に選ばれた ⇒ 自分の夫は黒夫

となって、結局殺人が起こってしまうような・・・。じゃあ、

案3.村を2つに分けて、交流を絶つ

というのはどうかな?
あ、でもこれも2つに分けるときに、

  • 片方が全員白夫だと成り立たなくなる ⇒ 自分たちの組に最低1人は黒夫がいる

ということになって、人数が減った分返って殺人が起こるタイミングを早めてしまうような・・・。ならば、

案4. 村を3つに分けて、交流を絶つ

で、なんとかならないかな?
自分たちの組が全員白夫でも成り立つので、連鎖が発生しなくなるはずです。

案5.案1, 案4のあわせ技。

初日に案4をやってしまえば、「黒夫は1人以上」という状況を保てます。
この状態で村の誰か1人が自然死するのを待てば、その後は元通りの村に戻れます。
村を分けるときに、「もし黒夫 or その妻が自然死したら、お互い連絡して元に戻る」という取り決めをしておけば良いのです。
(本当は誰が自然死しても良いのに、上のような取り決めにしないといけないのも、何気に面白いポイントだなぁ・・・。)

で、

回答の方は解いた後にGoogle先生に問い合わせて、どうやら合ってるらしいことが分かりました。
が、おまけの黒夫救出作戦の方は合ってるかどうかが分かりません。
もし間違っているとか、論理展開が甘いとかに気がついた方などおられましたら、突っ込んでいただけると幸いです。

Javaのinterfaceの遅さについて考える。

ふと、「Javaのinterfaceのメソッド起動は遅いかもしれない」と思って調べてみました。

まずは動作テスト

メソッド起動よりループの方が遅いのか、普通にループさせてテストしても差がでませんでした。
なので、下記のようなテストコードを書いて検証。
JVMは1.6.0_27でテストしました。

interface IFoo { void foo(); }
abstract class AbstractFoo { public abstract void foo(); }
class Foo extends AbstractFoo implements IFoo { @Override public void foo() {} }
public class VirtualVSInterface {
	public static void main(String[] args) {
		// ↓自作ライブラリ。見たまんまなので、説明略。
		PerformanceMeter.init(System.out);

		Foo foo = new Foo();
		for (int time = 0; time < 10; time++) {
			PerformanceMeter.start();
			for (int i = 0; i < 30000; i++) {
				callFoo3000Times(foo);
			}
			PerformanceMeter.end();
		}
		PerformanceMeter.show();
	}

	static void callFoo3000Times(Foo foo) { // ← ここを書き換える
		foo.foo();
		foo.foo();
		foo.foo();
		foo.foo();
		foo.foo();
		// :
		// :
		// こんな感じで3000回呼び出す。
	}
}

callFoo3000Timesメソッド内で3千回呼び出して、それを3万回ループさせて、合計9千万回のメソッド呼び出しを行います。

これの結果は↓

[PerformanceMeter][****] Elapsed time is 1227.436899(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1288.487153(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1267.502598(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1265.594484(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1250.509644(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1267.367435(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1269.642116(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1252.13631(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1257.907276(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1356.383693(ms), Used memory is 0.0(KB).
[PerformanceMeter][Summary]
    [****]: 12702.967608(ms), performed 10 times, average 1270.29676(ms)

10回テストして、平均が1.27秒くらい。
次に、callFoo3000Timesメソッドのパラメタを↓のようにinterfaceに書き換えます。

	static void callFoo3000Times(IFoo foo) { // ← ここを書き換える

これの実行した結果が↓

[PerformanceMeter][****] Elapsed time is 1383.983558(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1486.349774(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1415.176375(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1406.891197(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1406.291089(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1436.857707(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1406.008785(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1407.861295(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1403.233229(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1425.40517(ms), Used memory is 0.0(KB).
[PerformanceMeter][Summary]
    [****]: 14178.058179(ms), performed 10 times, average 1417.805817(ms)

こちらは平均約1.42秒くらい。
やっぱり、interfaceとして起動した方が遅くなりますね・・・。
ついでに抽象クラスとしての起動も試してみます。

	static void callFoo3000Times(AbstractFoo foo) { // ← ここを書き換える

[PerformanceMeter][****] Elapsed time is 1232.08464(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1246.014175(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1252.963544(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1259.100222(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1251.726542(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1284.862976(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1332.044005(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1263.652151(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1246.69983(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 1250.21408(ms), Used memory is 0.0(KB).
[PerformanceMeter][Summary]
    [****]: 12619.362165(ms), performed 10 times, average 1261.936216(ms)

平均約1.26秒くらい。
通常の呼び出しとの有意な差はないみたいです。
思ったとおり、遅くなるのはinterfaceのときだけですね。

何故interfaceが遅いと思ったのか?

Javaのメソッドの構造は、基本下記のようになっているそうです。

Javaでメソッドを実装すると、↑の図のように各クラスが一つずつ持っている、関数テーブルに登録されます。
親クラスの関数テーブルの内容は、子クラスの関数テーブルに全てコピーされます。
子クラスでメソッドをオーバーライドした場合には、該当するメソッドが登録されている箇所が上書きされます。
つまり、上の図で言うとSubClass1はmethodBarをオーバーライドしているのでインデックス1が、SubClass2はmethodFooをオーバーライドしているのでインデックス0が、それぞれ上書きされます。


下記コードを例に考えると、

    public static void main(String[] args) {
        SubClass1 sub1 = new SubClass1();
        SubClass2 sub2 = new SubClass2();

        callAsSuperClass(sc1);
        callAsSuperClass(sc2);
    }
    
    void callAsSuperClass(SuperClass sc) {
        sc.methodFoo();  // (1)
        sc.methodBar();  // (2)
    }

(1)は「インスタンスのクラスの保持する関数テーブルのインデックス0を起動する」、(2)は「インスタンスのクラスの保持する関数テーブルのインデックス1を起動する」という意味になります。
インスタンスがSubClass1のときには、(1)ではSubClass1の関数テーブルのインデックス0が、(2)では同テーブルのインデックス1が、それぞれ起動されます。
この場合、インデックス0のmethodFooはコピーされたままオーバーライドされていないので、実際にはSuperClassのmethodFooと同じものが起動されます。
SubClass2の場合も同様に、(1)ではSubClass2でオーバーライドされたmethodFooが、(2)ではSuperClassのmethodBarが起動されます。
Javaのような静的型付言語では、基本的にはこのようにしてポリモーフィズム(多態性)を実現しています。
abstractメソッドは関数テーブルのインデックスを特定のシグニチャのメソッドのために予約した状態と考えることができますし、

   super.methodFoo();

のようなコードは、親クラスの関数テーブルのメソッドを呼び出していると考えることができます。


・・・と、ここまではクラスが一つしか親を持てない、単一継承だけについて考えてきました。
しかし、多重継承についても考え出ると、途端に話がややこしくなります。
Javaにも制限付きながら、「interface」という多重継承が存在しています。
では、上の図にinterfaceを足してみます。

FooInterfaceとBarInterfaceとで、別のメソッドをそれぞれインデックス0に割り当てています。
もしこの図のとおりだとすると、下記のコードの(3)では関数テーブルのインデックス0番を起動しようとしますが、そこに登録されているのは実際にはmethodFooです。

    public static void main(String[] args) {
        SubClass1 sub1 = new SubClass1();
        SubClass2 sub2 = new SubClass2();

        callAsSuperClass(sub1);
        callAsSuperClass(sub2);
    }
    
    void callAsSuperClass(BarInterface bar) {
        bar.methodBar();  // (3)
    }

このように、interfaceは複数implements可能なので、↑で説明したような単純な関数テーブルだけでは実現できません。


「じゃあ、BarInterfaceはメソッド一つだけど、領域を二つ分とってインデックス1にmethodBarを登録して、methodFooとかぶらないようにすれば?」と思うかもしれないですが、これもダメです。
何故なら、Javaでは一つのクラスがimplementsできるinterface数には特に上限はないですし、interfaceも多数のクラスに実装されることがあります。
さらにjava.sql.Connectionのように、約50ものメソッドを持っているinterfaceも存在しています。
これら全ての整合性を取るのは大変ですし、関数テーブルの肥大化も招いてしまうため、現実的ではないでしょう。
と言うわけで、javaのinterfaceはメソッドを起動する為になんらかの対策をとっているはずで、その分通常のクラスと比べてメソッド起動が遅くなるのでは?と考えたわけです。

アセンブルしてみる

実際のメソッド起動の様子を見れるかもしれないと思って、↓のようなコードを書いて、逆アセンブルしてみました。

interface IFuga{ void fuga(); }
abstract class AbstractFuga { public abstract void fuga();}
class Fuga extends AbstractFuga implements IFuga{
	@Override public void fuga() {System.out.println("fugafuga.");}
}

public class Sample {
	public static void main(String[] args) {
		Sample sample = new Sample();
		Fuga fuga = new Fuga();
		sample.callAsInterface(fuga);
		sample.callAsAbstract(fuga);
		sample.callAsMethod(fuga);
	}
	private void callAsInterface(IFuga fuga){
		fuga.fuga();
	}
	private void callAsAbstract(AbstractFuga fuga){
		fuga.fuga();
	}
	private void callAsMethod(Fuga fuga){
		fuga.fuga();
	}
}

アセンブル用のコマンドは↓。

javap -c -private Sample

得られたバイトコードは、↓のようになりました。

Compiled from "Sample.java"
public class tetz42.sample.Sample extends java.lang.Object{
public tetz42.sample.Sample();
  Code:
   0:	aload_0
   1:	invokespecial	#8; //Method java/lang/Object."<init>":()V
   4:	return

public static void main(java.lang.String[]);
  Code:
   0:	new	#1; //class tetz42/sample/Sample
   3:	dup
   4:	invokespecial	#16; //Method "<init>":()V
   7:	astore_1
   8:	new	#17; //class tetz42/sample/Fuga
   11:	dup
   12:	invokespecial	#19; //Method tetz42/sample/Fuga."<init>":()V
   15:	astore_2
   16:	aload_1
   17:	aload_2
   18:	invokespecial	#20; //Method callAsInterface:(Ltetz42/sample/IFuga;)V
   21:	aload_1
   22:	aload_2
   23:	invokespecial	#24; //Method callAsAbstract:(Ltetz42/sample/AbstractFuga;)V
   26:	aload_1
   27:	aload_2
   28:	invokespecial	#28; //Method callAsMethod:(Ltetz42/sample/Fuga;)V
   31:	return

private void callAsInterface(tetz42.sample.IFuga);
  Code:
   0:	aload_1
   1:	invokeinterface	#37,  1; //InterfaceMethod tetz42/sample/IFuga.fuga:()V
   6:	return

private void callAsAbstract(tetz42.sample.AbstractFuga);
  Code:
   0:	aload_1
   1:	invokevirtual	#42; //Method tetz42/sample/AbstractFuga.fuga:()V
   4:	return

private void callAsMethod(tetz42.sample.Fuga);
  Code:
   0:	aload_1
   1:	invokevirtual	#46; //Method tetz42/sample/Fuga.fuga:()V
   4:	return
}

通常のメソッドの起動にはinvokevirtual、そしてinterfaceでのメソッド起動ではinvokeinterfaceというのが使われています。
どうやら、このinvokeinterfaceが遅くなった原因のようです。
 ※ 記事のテーマとは無関係ですが、コンストラクタやprivateメソッドの起動はinvokespecialです。多態性が必要ないとき向けはこれみたいです。

invokeinterfaceについて調べてみる

invokeinterfaceの動作が気になったので、ググってみました。で、英語ですが↓の仕様書が見つかりました。
invokeinterface
一応読んでみたのですが・・・、「クラスCに該当するメソッドが見つかったらそれを起動。見つからなかったら親クラスを再帰的にたどっていく。」みたいに書かれてました。
うーん、流石にそんな風に動作するとは思えない・・・。もし本当にそんなつくりだったら、もっと遅いと思うし・・・。
これは「Javaの仕様としては、こうだよ。」という話で、実際の実装とは違う話なんだと思います。


もう少し探してみたところ、下記を発見しました。
Java の invokevirtual 命令と invokeinterface 命令の違い
なるほど、クラス側でimplementsされたinterfaceごとに変換テーブルを持っておくってことか。
先ほどの図に追加すると、下記みたいな感じかな?

↓のコードを例に考えると、

    public static void main(String[] args) {
        SubClass1 sub1 = new SubClass1();
        SubClass2 sub2 = new SubClass2();

        callAsSuperClass(sub1);
        callAsSuperClass(sub2);
    }
    
    void callAsSuperClass(BarInterface bar) {
        bar.methodBar();  // (3)
    }

 ・(3)では、BarInterfaceなので、BarInterface用変換テーブルが選ばる。
 ・methodBarはインデックス1番に変換されて、これを元に関数テーブルのmethodBarを見つけて起動。
という感じですね。
interfaceと対応するテーブルを見つける手段は、ハッシュを使ったり、最近起動したinterfaceをキャッシュして再利用したりして高速化するそうです。
ということは、interfaceを激しく切り替えるようなコードを書けば、遅くなるはずですね。
試してみます。

最初のコードを↓のように、異なるinterfaceを順番に起動するように書き換えました。

interface IFoo { void foo(); }
interface IFooFoo { void foo(); }
interface IFooFooFoo { void foo(); }
abstract class AbstractFoo { public abstract void foo(); }
class Foo extends AbstractFoo implements IFoo, IFooFoo, IFooFooFoo {
	@Override public void foo() {} 
}
public class VirtualVSInterface {
	public static void main(String[] args) {
		// ↓自作ライブラリ。見たまんまなので、説明略。
		PerformanceMeter.init(System.out);

		Foo foo = new Foo();
		for (int time = 0; time < 10; time++) {
			PerformanceMeter.start();
			for (int i = 0; i < 30000; i++) {
				callFoo3000Times(foo, foo, foo);
			}
			PerformanceMeter.end();
		}
		PerformanceMeter.show();
	}

	static void callFoo3000Times(IFoo foo, IFooFoo foofoo, IFooFoo foofoofoo) { // ← ここを書き換える
		foo.foo();
		foofoo.foo();
		foofoofoo.foo();
		foo.foo();
		foofoo.foo();
		foofoofoo.foo();
		// :
		// :
		// これを3000回
	}
}

この状態で実行すると・・・

[PerformanceMeter][****] Elapsed time is 2114.41286(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2166.698675(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2118.031035(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2129.420224(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2254.794114(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2258.398601(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2140.098524(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2138.503943(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2306.046959(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2151.361103(ms), Used memory is 0.0(KB).
[PerformanceMeter][Summary]
[****]: 21777.766038(ms), performed 10 times, average 2177.776603(ms)

おお、確かに遅くなった!
平均2.18秒くらいです。
念のため、↓のパラメタ全てが同一のinterfaceとなるパターンも試してみます。

	static void callFoo3000Times(IFoo foo, IFoo foofoo, IFoo foofoofoo) { // ← ここを書き換える

[PerformanceMeter][****] Elapsed time is 2309.425604(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2361.475312(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2322.6211(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2324.873959(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2342.970822(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2336.956926(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2317.427165(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2312.028347(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2319.148782(ms), Used memory is 0.0(KB).
[PerformanceMeter][****] Elapsed time is 2327.235032(ms), Used memory is 0.0(KB).
[PerformanceMeter][Summary]
[****]: 23274.163049(ms), performed 10 times, average 2327.416304(ms)

あれ!?
平均2.33秒くらい?
別interfaceで起動する例に比べると、キャッシュが効く分早いかと思ったのですが・・・。


試しにjavaの起動オプションに「-server」とか「-Xint」とか足してみて何回かテストしたのですが、どの条件でも別interface経由で起動するほうが早い、という結論になってしまいました。
javapでの逆アセンブルも試してみたのですが、特筆するような結果は得られなかったので、割愛します。


それにしても最初の事例に比べると、随分遅いですね・・・。
interfaceを多数implementsしたときの影響は、思っていたより大きいようです。

まとめ

Javaは単一継承が基本の言語であり、多重継承が可能となるinterfaceは特殊な存在であり、バイトコード上も特別な処理がされています。
そのため、通常のクラスに比べると少々メソッド起動が遅いです。
 ※とはいえ、その差は微々たるものなので、通常の用途では気にする必要はありません。


また、多数のinterfaceをimplementsするとより遅くなってしまうような結果が今回出ましたが、充分な実験&考察ができていません。
この件に関しては、また機会があったら試して記事にしてみたいと思います。

足きりだけど、DevQuizの回答を晒させて下さい。

GoogleのDevQuizってチャレンジしましたか?
私一応チャレンジしたんですけど…、100点しか取れなかったので足きりになってしまいました。

考えが甘かったんですよね〜。
ZusaarNotify-modokiの開発にのめり込んだりしているうちに時間は経過してしまい。
やっと取り掛かったのが締め切り前日9/11の夜。今にして思えばその時点でもうアウトでした。
数時間でなんとかなるような甘いものじゃ、全然なかったです。(少なくとも、私の実力では。)

折角やったので、回答した分だけでも自分の答えを晒しておこうと思います。

ウォームアップクイズの回答

Chrome

次の HTML5 の要素のうち、Google Chrome 13 でサポートされていないものはどれでしょうか?
 ・

videoをサポートしていることは知ってたのですが、他はわかりませんでした。
適当なHTML書いて全部試してみたら、timeだけ何も起こりませんでした。
調べたところ、timeタグはクローラ等のHTMLを解析するプログラムに情報を与える目的のタグだそうなので、何も起きない=サポートしていないで良いのか? と少し悩みましたが、他になかったのでこれを選びました。

maps API

Google Maps JavaScript API V3 にて以下のコードのように定義した gddMapType では、 通常の地図と比べてどのように見た目が変化するでしょうか? 間違っているものを選択してください。

maps APIを使ったことがなかったので、これも実際に動かしてみて確認しました。
・黒くなっていない道路があったこと
・黒く塗りつぶすと言うより、彩度を落とすことを目的としたコードだったこと
などから、「全ての道路が黒く塗りつぶされる。」を選択しました。
でも、「featureType: "road",」は
http://gmaps-samples-v3.googlecode.com/svn/trunk/styledmaps/wizard/index.html
辺りを見ると全ての道路を示してそうな気がするのですが、何故黒くならなかった道路が存在したのかはまだ良くわかってません。

Google translate

こちらのロシア語を日本語に翻訳すると何になるでしょうか?

ロシア語は全然わからないけど、綴りからみてじゃがいもっぽいな、と思ってGoogle翻訳でじゃがいもを翻訳してみたら、ドンピシャでした。

Android

Android 3.x (Honeycomb)についての次の記述のうち、間違っているものはどれでしょう?

・ドラッグ & ドロップ(ドラッグ中の半透明 UI 表示など)の実装が簡単にできる API が提供されている
・画面描画を高速化するハードウェアアクセラレーションを活用するには Java では足りず、C/C++ を活用した JNI プログラミングが必要である
・Fragment, Action Bar などの考え方は今後 一般の携帯電話用にもリリースされる Ice Cream Sandwich のアプリケーション開発においてもそのまま継承される

Android知らないので、普通に検索して調べてみました。
結果、2番目を選択。

iGoogle

iGoogle ガジェット ダッシュボードのトップページで閲覧できるページビューやインストール数は過去何日間分でしょうか?

これも知らなかったので調べて、「7日分」を選びました。

ウォームアップは翌朝まで結果がでなかったのでヒヤヒヤしましたが、満点が取れていました。

Web Game

ちょうどChrome Extensionを作っていたので、まずはWeb Gameにチャレンジ。
ヒントのExtensionをそのまま使って回答を作成しました。
細かいバグを出しながら、1時間くらい格闘して書き上げたのが下記ソース。

var element = document.getElementById('card0');
if (element == null) {
	alert('Card element is not found. Check element id.');
} else {
	main();
}

function main() {
	var myevent = document.createEvent('MouseEvents');
	myevent.initEvent('click', false, true);

	var i = 0;
	var map = {};
	while(true) {
		var element = document.getElementById('card' + i);
		if(!element)
			break;

		element.dispatchEvent(myevent);
		var color = element.style.backgroundColor;

		if(map[color] || map[color] == 0) {
			var elementX = document.getElementById('card' + map[color]);
			elementX.dispatchEvent(myevent);
			element.dispatchEvent(myevent);
			elementX.dispatchEvent(myevent);
		} else {
			map[color] = i;
		}
		i++;
	}
}

要するに順番にカードをクリックしながらMapに色をどんどん登録していって、過去に同じ色のものが登録されていたら過去のカードと今のカードを適当な回数クリックして揃える操作を実行、というだけのソースです。
色がそろった後のカードは何回クリックしても問題ないことがわかっていたので、揃える操作のクリック回数は本当に適当です。

一人ゲーム

残りの問題の中ではGoが一番簡単そうに見えたのですが、Go書いたことがない & Goの実行環境を構築するだけでも1時間以上はかかりそうだったので、ひとまずAndroidに着手しました。
が、やってる途中で一人ゲームの解法が浮かんできたので、急遽方針転換。
Android用にEclipse立ち上げてたんで、そのままの勢いでJavaで書きました。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class AloneGame {

	public static void main(String[] args) throws IOException {
		new AloneGame().execute();
	}

	public void execute() throws IOException {
		InputStream stream = getClass().getResourceAsStream("AloneGame.dat");
		InputStreamReader reader = new InputStreamReader(stream);
		BufferedReader br = new BufferedReader(reader);

		// ignore first line
		br.readLine();
		
		String line;
		while (null != (line = br.readLine())) {
			int size = Integer.parseInt(line);
			line = br.readLine();
			String[] strs = line.split(" ");
			if (strs.length != size) {
				throw new RuntimeException("invalid data!");
			}
			List<Integer> vals = new ArrayList<Integer>(strs.length);
			for (String s : strs) {
				vals.add(Integer.parseInt(s));
			}
			System.out.println(countMin(vals));
		}
	}

	public int countMin(List<Integer> vals) {
		return countMin(vals, 0);
	}

	private int countMin(List<Integer> vals, int count) {
		count++;
		boolean isAllAvoidOK = true;
		boolean isAllHalfOK = true;
		for (int val : vals) {
			if (val % 5 != 0) {
				isAllAvoidOK = false;
			} else if (val % 10 != 0) {
				isAllHalfOK = false;
			}
		}
		if (isAllAvoidOK)
			return count;
		if (isAllHalfOK)
			return countMin(toHalf(vals), count);
		int case1 = countMin(toHalf(vals), count);
		int case2 = countMin(avoid5(vals), count);
		return case1 < case2 ? case1 : case2;
	}

	private List<Integer> toHalf(List<Integer> vals) {
		List<Integer> newVals = new ArrayList<Integer>(vals.size());
		for (Integer val : vals) {
			newVals.add(val / 2);
		}
		return newVals;
	}

	private List<Integer> avoid5(List<Integer> vals) {
		List<Integer> newVals = new ArrayList<Integer>(vals.size());
		for (Integer val : vals) {
			if (val % 5 != 0)
				newVals.add(val);
		}
		return newVals;
	}
}

つまり、

  1. 全てが5で割り切れるときは終了
  2. 全てが下記どちらかの条件を満たすときは、5で割り切れる数を取り除いても意味がないので半分にする操作を実行
    1. 5で割り切れない
    2. 10で割り切れる
  3. 1, 2以外の場合はどちらの操作が良いのかわからないので、両方やってみて回数が少ない方を採用

という操作を再帰的に実施して回数をカウントするプログラムです。
測ってみたところ、Corei5で100問を200〜300ミリ秒くらいで解くことができていました。

そしてタイムアップ

ここまで解いた時点で、もう朝の5:00くらいでした。
次の日仕事だったためやむなく寝たのですが・・次の日の朝、ボーダーラインが101点前後と判明。
出社途中の電車の中でスライドパズルを数問手作業で解いたりもしたのですが、悪あがきに過ぎませんでした。

感想

結果も残念でしたが、それ以上に残念なことが・・・。
やってみたらすごく楽しかったので、

  • 時間に追われる中でのチャレンジだったこと
  • 最後の問題にチャレンジできなかったこと

が悔やまれます。
またこのような機会があったら、今度は時間をちゃんととってリベンジしたいと思います。

最後に

GDD参加が決定した皆さん、おめでとうございます。私の分まで楽しんできて下されば幸いです。
報告会などがあれば、参加したいと思います。

私も来年こそ参加するつもりですので、よろしく!

「ZusaarNotify-modoki」というChrome Extensionを公開してみました。

「ZussarNotify-modoki」というChrome Extensionを作って、公開してみました。
これ、私がはじめて作成したChrome Extensionです。

ZussarNotify-modoki

インストールすると、Zusaarにイベントが登録されたり更新されたりする度に通知が出るようになります。
設定画面にてキーワードを登録すれば、キーワードに合致したイベントのみが通知されるようになります。
参考にさせて頂いたのは、私が普段からお世話になっている「ATND Notify」です。

ZusaarNotify-modokiの挙動

ZusaarNotify-modokiの動作はものすごく単純です。
ZusaarのイベントサーチAPIを、検索条件をつけずに叩くと更新日時が新しい順に結果を返してくるので、

  1. 5分に1回、1件イベントを取得する
  2. 取得したイベントが前回取得したものと同じなら更新されてないので、通知しないで終了。
  3. 前回取得したものと違っていれば、前回取得したイベントの更新日付より新しいイベントを全て取得してきて、通知する。ただしキーワードが設定されていたら、そのキーワードとマッチしたイベントのみ通知する。

たったこれだけです。
ATND Notifyはちゃんとキーワード検索用のAPIを叩いているのですが、Zusaarは現時点ではまだ全文検索に対応しておらず*1、上記のような手法をとっています。

ZusaarNotify-modokiソースは見易く書き直してから、ATND Notifyと同じMITライセンスで公開しようかと思っています。

謝辞

(はじめての)Chrome拡張勉強会にて、Chrome Extensionを勉強する機会を与えてくださった主催者の@tetsunosukeさん、ZusaarのAPIについて教えていただいた@rakiさん、どうもありがとうございました。
この会がなかったら、そもそもChrome Extensionを作れるようになっていませんでした。

また、TwitterでZusaar APIに関する不躾な質問にも快く答えてくださったZusaarの中の人、@knj77さん、どうもありがとうございました。

そして、ATND Notifyという素晴らしいアプリを開発してくださったid:bluerabbitさん、どうもありがとうございました。
Twitter, Facebook, Google+, Gmail等々、全て使用禁止というリアルタイム情報ゼロの職場環境にいながら、様々なイベントに参加できているのはひとえに「ATND Notify」のお陰です!

ZusaarNotify-modokiの今後

元々Zusaarが全文検索に対応するまでのつなぎアプリになれば充分だと思って開発したので、まだあまり考えてないです。
開発を続ける意思はあるので、もし追加して欲しい機能や要望等がありましたら、コメントするか、Twitterで@tetz42までご連絡ください。

*1:中の人に確認したのですが、ZusaarはGAEの全文検索機能がリリースされたら対応する予定だそうです。

SingletonとExceptionについての自分の結論

SingletonとExceptionについて考えてたら、なんだか良く分からなくなってしまいました。
で、SingletonパターンとExceptionについて考えてみたのですが、良くわからず・・・。
結論として↓の実装を考えてみたものの、問題ない実装であることの証拠も見つけられず・・・。
手詰まりのまま記事を公開していたのですが、その後もう少し調べたところ↓の実装で問題ないことが分かりました。

public class Singleton {

	private static class Inner {
		private static final Singleton singleton = new Singleton();;
	}

	public static Singleton getInstance() {
		try {
			return Inner.singleton;
		} catch (ExceptionInInitializerError e) {
			Throwable original = e.getCause();
			// 何かエラー処理
			throw new ProjectOriginalException("catched by Singleton!", original);
		}
	}

	private Singleton() {
		throw new RuntimeException("Singleton constructor failure!");
	}
}

根拠は下記Java仕様書の「12.4 Initialization of Classes and Interfaces」。
The Java Language Specification Third Edition
重要なところを訳してみると、

Classが初期化されるのは、class or interfaceのTが

  1. Tがclassで、インスタンス化されるとき
  2. Tがclassで、staticメソッドが起動されたとき
  3. Tに定義されたstaticフィールドが割り当てられたとき
  4. Tに定義されたstaticフィールドが使用される かつ そのstaticフィールドがコンスト値*1ではないとき
  5. Tがトップレベルクラス*2で、Tに含まれたassert文が実行されたとき。

上記操作をリフレクションで行ってもClassは初期化される。
上記以外の状況ではclass or interfaceは初期化されない。

と書かれておりました。(※5番の訳は自信ないです。)
よって、今回の↑のSingleton実装ではインナークラスのInnerが初期化されるタイミングは、getInstanceメソッド内部で「Inner.singleton」が呼び出されたタイミングだけ、言い換えると上記4番の条件を満たしたときだけです。
それ以外の状況では初期化されないので、Singletonインスタンス化のときに発生した例外は、必ずgetInstanceメソッド内のtry-catchで処理できることになります。

謝辞

今回の結論を出すきっかけを作ってくれたのは、英語版Wikipediaの下記記事でした。
Sigleton Pattern
自分の書いたSingletonが、真ん中辺りの「The solution of Bill Pugh」のサンプルソースにそっくりなことに気がついて、そこから調査を始めました。
Wikipediaの記事には

The technique known as the initialization on demand holder idiom, is as lazy as possible, and works in all known versions of Java.

とも書いてあったので、「The solution of Bill Pugh」が全バージョンのJava環境で動作することまでは分かったのですが、これは遅延初期化を意図したテクニックなので、Exception処理を意図した↑でも同じ話が通用するのかが分かりませんでした。

何か情報はないかと思って更にググってみたところ、
じゅんいち☆かとうの技術日誌-シングルトンパターンの遅延初期化をスレッドセーフにするには
にたどり着きました。
分かりやすく詳細に書かれていて、とても参考になりました。
ありがとうございます!
上記記事にはJava仕様書のどこが根拠となっているかの記述まで書いてあったので、自分で仕様書をチェックすることができました。
いや、本当に助かりました。

おまけ

上記Java仕様書の翻訳を改めて見てみて気づいたんですが・・・フィールドを持たないinterfaceって初期化されなくないですか?
まぁ確かに、フィールドのないinterfaceは初期化処理なくても成り立ちそうな気はするのですが・・・本当にそうなのかな?
誰か、知ってる人いませんかね・・・?

*1:プリミティブ値 or String型でfinal宣言された、コンパイル時に解決される値

*2:インナークラスじゃないクラス

SingletonとExceptionについて考えてたら、なんだか良く分からなくなってしまいました。

Singletonパターンってあるじゃないですか。
↓みたいな感じのヤツ。

public class Singleton {
	private static final Singleton singleton = new Singleton();

	public static Singleton getInstance() {
		return singleton;
	}

	private Singleton() {
	}
}

このSingletonパターンで、インスタンス生成時に例外が発生するケースについて考えてみたんですが、どうもよく分からなくなってきてしまいました。
とりあえず纏めて置きますので、分かる方がいたら突っ込みをお願いしたいと思います。

背景

例えば上の例で、コンストラクタを↓みたいに書き換えて、

	private Singleton() {
		throw new RuntimeException("Singleton is dead!");
	}

わざと例外を発生させると、なんだか良く分からないエラーが出ます。

Exception in thread "main" java.lang.ExceptionInInitializerError
	at singletontest.Util.main(Util.java:13)
Caused by: java.lang.RuntimeException: Singleton is dead!
	at singletontest.Singleton.<init>(Singleton.java:12)
	at singletontest.Singleton.<clinit>(Singleton.java:5)
	... 1 more

このエラーを避ける為に、以前の私は好んで↓のパターンを使用しておりました。

public class Singleton {

	private static Singleton singleton;

	public static Singleton getInstance() {
		if (singleton == null) {
			synchronized (Singleton.class) {
				if (singleton == null) {
					try {
						singleton = new Singleton();
					} catch (RuntimeException e) {
						// 何かエラー処理
						throw new ProjectOriginalException("catched by Singleton!", e);
					}
				}
			}
		}
		return singleton;
	}

	private Singleton() {
		throw new RuntimeException("Singleton constructor failure!");
	}
}

ところが、、、、知らずに使っちゃってましたが、実はこの書き方はdouble-checked lockingと呼ばれており、「まだコンストラクタで初期化されていないインスタンスが、getInstance()メソッドから返却される可能性がある」という、かなりシャレにならない誤動作をする可能性があることが知られています。
参考:http://www.ibm.com/developerworks/jp/java/library/j-dcl/

で、結局解決策は「同期化を受け入れるか、あるいはstatic field を使用すること」だそうです。
例外が発生する可能性があるSingletonでは「同期化を受け入れる」を選ぶのが確実そうですが・・・やっぱり無駄に同期化のコストを払い続けるのって気分的に嫌なので、「static fieldを使用する」(つまり最初に例示した、static fieldで直接Singletonクラスをnewして代入するやり方)で実現できないか、考えてみることにしました。

ExceptionInInitializerErrorとは

ExceptionInInitializerErrorですが、名前の通りInitializer内でExceptionが発生してしまった場合にthrowされるErrorです。
Errorではありますが、普通にcatchできるし、発生した例外はgetCause()メソッドで取れるし、catchしてからの処理は難しくありません。

		try {
			return Singleton.getInstance();
		} catch (ExceptionInInitializerError e) {
			Throwable original = e.getCause();
			// 何かエラー処理
			throw new ProjectOriginalException("catched by Singleton!", original );
		}

問題はここからです。
↑はSingleton.getInstance()を呼び出してExceptionInInitializerErrorをcatchしてますが、これをgetInstance()メソッド内部で実行するのは不可能です。
なぜなら例外が発生しているのは↓のstaticフィールドへの初期化処理中、つまりクラス・ローディングのタイミングなので、getInstance()メソッドを呼び出す前に発生してしまいます。

	private static final Singleton singleton = new Singleton();

なので、クラスローディングが走る可能性がある箇所全てでExceptionInInitializerErrorをキャッチする必要があることになります。
そんなのやってられないですよね。
F/Wとか使ってて、Exceptionを処理する箇所が決まっているなら単にExceptionInInitializerErrorに対する処理を追記するだけでも良いような気もするのですが、もっと環境に依存せず、Singletonのクラスのみで完結する良い手はないかと考えてみた訳です。

自分の考えた実装

結局、下記のようになりました。

public class Singleton {

	private static class Inner {
		private static final Singleton singleton = new Singleton();;
	}

	public static Singleton getInstance() {
		try {
			return Inner.singleton;
		} catch (ExceptionInInitializerError e) {
			Throwable original = e.getCause();
			// 何かエラー処理
			throw new ProjectOriginalException("catched by Singleton!", original);
		}
	}

	private Singleton() {
		throw new RuntimeException("Singleton constructor failure!");
	}
}

staticフィールドへの初期化処理をgetInstance()でハンドリングするために、インナークラスにフィールドを持たせています。
JVM起動後に、そのクラスを最初に使用する箇所でクラスローディングが発生する」という前提さえ守られていれば、インナークラスが最初に使用されるのは必ずgetInstance内の「return Inner.singleton;」の部分なので、ちゃんとExceptionInInitializerErrorをハンドリングできる、というわけです。
動作テストしてみたところ、少なくとも自分の環境ではちゃんと動きました。

でもこのコード、クラスローディングがいつ発生するのかに強く依存しています。
クラスローディングが起こるタイミングって仕様上はある程度の幅があると聞いたことがあるのですが、そうするとクラスローディングが違うタイミングで発生してしまって、全く関係ないところでExceptionInInitializerErrorが発生する可能性もあるのでしょうか?
分かる方がいたら、突っ込んでいただけると助かります。

ついで。

コンストラクタがthrowするのがチェック済み例外(要するにRuntimeException以外のException)の場合はコンパイルエラーになるので、「Static Initializerでcatch」等の対策が必要です。

public class Singleton {

	private static class Inner {
		private static final Singleton singleton;
		static {
			try {
				singleton = new Singleton();
			} catch (IOException e) {
				throw new ExceptionInInitializerError(e);
			}
		}
	}

	public static Singleton getInstance() {
		try {
			return Inner.singleton;
		} catch (ExceptionInInitializerError e) {
			Throwable original = e.getCause();
			// 何かエラー処理
			throw new ProjectOriginalException("catched by Singleton!", original);
		}
	}

	private Singleton() throws IOException {
		throw new IOException("Singleton constructor failure!");
	}
}