nisshiee / takashi Goto Github PK

akkaのメッセージベース再帰探査をやってみる

http://www-erato.ist.hokudai.ac.jp/html/php/seminar.php?day=20110520

おそらくケースバイケース。

普通のFieldなら、Trampoline無しでいい。
スタックの深さはMaxで「0」のマスの数なので、
10 x 10Fieldでも100しか掘らないし、この領域なら計算時間の方がボトルネック。

ただ、極端な例だと、Stackの深さがボトルネックに成り得る。
例えば1 x 10000Fieldだと分岐なしで探査終わるので計算時間は一瞬だが、
スタック掘るとたぶん落ちる。

「0」のマスの数を基に、適当な閾値で切り替えるとか？

再帰探査に入る前に到達可能性のチェックを入れるべき。
到達可能性判定はO(n log n)（nはマス数。たぶん。もしかしたらO(n)いけるかも）でいけるので、例えば以下のようなworstケースで0を返す時間に差が出る。

0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,0,1,0

• Scala 2.10.0
• sbt 0.12.2
• scalaz 7.0.0-M8
• scala-csv 0.7.0

• Goal判定が二重
• implicit conversionでTuple->Point変換を毎回入れてるのはさすがに無駄