男なら，負けるとわかっていても戦わなければならない時がある．
死ぬとわかってもいても行かねばならない時がある．
Captain Harlock
友人の誘いでHaskellを勉強することにした．
Googleでいろいろと情報をさらっていると，小飼弾氏による「たらいまわし関数」の記事が目に入った．
404 Blog Not Found:たらいを回すならHaskell
後で買った書籍「普通のHaskell」にてもたらいまわし関数の比較が記述されていた．
昔，Prologを習ったときにもこのような再帰関数の処理量が爆発する計算が，Prologならあっという間にできるということをならった気がする．
このような問題はそもそもあちらの言語に圧倒的に有利な問題だ．
どんな問題にも向いている言語があり，問題に向いている言語を使うのがプロのプログラマだ．
またどんな問題にも向いている「銀の弾丸」は存在しない．
しかし，私はJavaが好きだ．
Javaでもそれなりにたらいが回せるはず，そう思った次の瞬間，私はJavaで書き始めていた．
まずは普通に書いてみる．
class Tak {
static int tak(int x, int y, int z) {
return (x <= y) ? y : tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y));
}
static public void main(String args[]) {
int x, y, z;
if (args.length > 2) {
x = Integer.parseInt(args[0]);
y = Integer.parseInt(args[1]);
z = Integer.parseInt(args[2]);
} else {
x = 12; y = 6; z = 0;
}
System.out.println("tak(" + x + ", " + y + ", " + z + ") = " + tak(x, y, z));
}
}実行環境
PentiumM1.8GHｚ, Memory: 1GB
Sun JDK1.5.0_07
実行結果
$ time java Tak 12 6 0 tak(12, 6, 0) = 12 real 0m0.311s user 0m0.010s sys 0m0.000s
この程度の計算量ならJavaの速さが光るだろう．
ちなみに同じマシンでの最適化前のRubyの結果が以下である．
$ time ruby tak.rb 12 6 0 tak(12, 6, 0) = 12 real 0m8.963s user 0m8.892s sys 0m0.040s
PerlはOut of memroyで17秒後に落ちてしまった.
Pythonの実行結果
$ time python tak.py 12 6 0 tak(12, 6, 0) = 12 real 0m5.518s user 0m0.010s sys 0m0.000s
さて，問題はここから．
普通のHaskellでは20,10,5を，さらに弾さんは100,50,0を実行している．
私の環境でのJavaは前者を35秒，後者は終わらないので諦めた．
ここから最適化に入る．
まず普通に考えてPerlと同じように、連想配列ならぬHashMapを使ってMemoizeする．
ただ，最初に私はKeyを以下のようにすれば良いかと思った．
int[] key = {x, y, z};Javaでは配列はオブジェクトであり，HashMapのKeyに使用できる．
しかしこの方法ではint#equalsが中の要素を比較せず，Hashがヒットしないようだ．
intを継承して無名内部クラスを作ろうとしたが，思ったようにうまくいかなかった．
このためしょうがないので内部クラスを作成した．
import java.util.*;
class Tak2 {
static Map pool = new HashMap(5000);
static public class Key {
int x, y, z;
Key(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
public boolean equals(Object o) {
Key other = (Key) o;
return (x == other.x && y == other.y && z == other.z);
}
}
static int tak(int x, int y, int z) {
Key key = new Key(x, y, z);
Integer value = (Integer)pool.get(key);
if (value != null) return value.intValue();
if (x <= y) {
pool.put(key, Integer.valueOf(y));
return y;
} else
return tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y));
}
static public void main(String args[]) {
int x, y, z;
if (args.length > 2) {
x = Integer.parseInt(args[0]);
y = Integer.parseInt(args[1]);
z = Integer.parseInt(args[2]);
} else {
x = 12; y = 6; z = 0;
}
System.out.println("tak(" + x + ", " + y + ", " + z + ") = " + tak(x, y, z));
}
}これを読むとJavaの冗長さが目立つ．鬱だ．
またこのプログラムは大失敗である．
小さな値での実行では遅くなってしまい，大きな値ではOutOfMemory例外で落ちてしまうのだ．
Javaを使って何年にもなるのにマヌケな話なのだが，JavaではMapを使う場合にObject#equalsのみならず，Object#hashCodeも変えねばならないのを理解していなかった．
HashMapのソースを読んでみよう．
HashMapの構造はLinkedListの配列だと思って良い。
まずKeyのhashCodeを取り，配列のインデックスを限定することがわかるはずだ．
つまりequalsだけを修正しても、hashCodeがインスタンスによって異なるようではHashMapはまともに働かないのだ．
上のコードでは本来equals()==trueの意味で同じオブジェクトの場合でも，Object.hashCode()はヒープ上のアドレスに基づき個々のインスタンス別に生成されている．その結果，HashMap上では違うオブジェクトと認識されて異なる場所に格納されている．
このために同じ結果が大量にHashMapに作成されて，OutOfMemoryを引き起こしているのだ．
hashCodeをどうやって計算すれば良いのかはいろいろなところで記事になっている．
IBM Developer 日本語版 : 大変申し訳ありません。このページは無効です。
Hashtables | JavaWorld
http://www.vipan.com/htdocs/hashcode_help.html
ここまで読む途中でお腹いっぱいである．
まとめると，
- equals()を書き換える時にはhashCodeも書き換えなければならない
- equals()にはJoshua Blockの5 step methodが「Effective Java」にまとめられている
- hashCode()には素数の積の和とString化後連結があるがどちらも問題あり
- hashCode()は同じ入力には同じ値を返す事
- hashCode()は異なる入力に対し、同じ値を返しても良い．
今回のプログラムは目的と使用クラスがはっきりしているので適当に実装する．
import java.util.*;
class Tak3 {
static Map pool = new HashMap(5000);
public static class Key {
int x, y, z;
Key(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
public boolean equals(Object o) {
Key other = (Key) o;
return (x == other.x && y == other.y && z == other.z);
}
public int hashCode() {
return x + y * 3 + z * 5;
}
}
static int tak(int x, int y, int z) {
Key key = new Key(x, y, z);
Integer value = (Integer)pool.get(key);
if (value != null) return value.intValue();
if (x <= y) {
pool.put(key, Integer.valueOf(y));
return y;
} else {
int result = tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y));
pool.put(key, Integer.valueOf(result));
return result;
}
}
static public void main(String args[]) {
int x, y, z;
if (args.length > 2) {
x = Integer.parseInt(args[0]);
y = Integer.parseInt(args[1]);
z = Integer.parseInt(args[2]);
} else {
x = 12; y = 6; z = 0;
}
System.out.println("tak(" + x + ", " + y + ", " + z + ") = " + tak(x, y, z));
}
}実行結果
$ time java Tak3 100 50 0 tak(100, 50, 0) = 100 real 0m0.225s user 0m0.010s sys 0m0.000s
大・成・功．
まぁ，宇宙人に勝てはせずとも負けていない数値が出ただろう．
ところでマジメなMemoizeの実装はJavaにも存在する．
DynamicProxyを用いてMemoizeを実装したプログラムが以下の記事である．
Ideas - O'Reilly Media
今回は面倒なのと，速くなるかどうかわからなかった(Interfaceにてクラス大量生産が速いかどうか自信がなかった．）のでどなたか試してみてほしい．
また反則ぎみなコードも実は書いていた．
HashMapなんか重いだろうから，JavaはCの家系らしくbit演算に走るべし，と考えたのが以下のコード．
(x, y, z)が127以下でないと破綻するだろうという制限付きである．
HashMapがこんなに速くなかったらこちらを公開してお茶を濁そうと思っていた．
プログラムの短さならこちらが上である．
public class Tarai {
final static int[] pool = new int[0x1000000];
private static int tak(int x, int y, int z) {
if (x <= y) {
return y;
} else {
int value = (x & 0xff << 16) + (y & 0xff << 8) + (z & 0xff);
if (pool[value] != 0) return pool[value];
int result = tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y));
pool[value] = result;
return result;
}
}
public static void main(String args[]) {
int x = 100;
int y = 50;
int z = 0;
if (args.length > 2) {
x = Integer.parseInt(args[0]);
y = Integer.parseInt(args[1]);
z = Integer.parseInt(args[2]);
}
System.out.println("tak("+x+","+y+","+z+") = " + tak(x, y, z));
}
}実行結果
$ time java -Xmx512M Tarai tak(100,50,0) = 100 real 0m0.279s user 0m0.020s sys 0m0.000s
あまり変わらない．
Javaの実行速度は相当に優秀だ．
というわけでJavaでたらいをまわしてみた．
Javaの実行速度は一級だ．
ただし生産性が良いかどうかは，，，問題による．
このような良質の練習問題が意外に自分の足元を見直す良い機会になるものだった．
今，万感の思いを込めて汽笛が鳴る．
追記
Eclipse3.2からはJavaのクラスに対して自動的にequals()とhashcode()を追加してくれるようになりました．
ソース上で右クリックして，(またはAlt+Shift+S）
Source -> Generate hashCode() and equals()...
を選択するだけです．
上記のクラスKeyに対して実行すると以下の結果となりました．
@Override
public int hashCode() {
final int PRIME = 31;
int result = 1;
result = PRIME * result + x;
result = PRIME * result + y;
result = PRIME * result + z;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Key other = (Key) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
if (z != other.z)
return false;
return true;
}とてもとても便利です．
