ただいま

本日、実家から帰宅。

骨休めができたのか微妙な点はあったが、久々に実家の食事を堪能させていただきました。

高校時分の友人が子連れ(3歳)で遊びに来るなどそれなりにイベントもあり、いい気分転換にはなったと思う。

正月早々「年の始めはさだまさし」を横目に、Haskellのコードとにらめっこしてたような気もするが新年のスタートとしては悪くないだろう。

そう言えばクロノトリガーをプレイするのを忘れていた。折角DS持って帰ってたのに。

Haskell::OGR-nの探索(その6)

GR-nの生成(その6、7)で得られた知見をその5にぶちこんでみた。

ogr6.hs

こっそりGREの型をWord16(16bit unsigned int相当)に変更。n=10程度で心配する必要もないが、一応桁溢れに考慮。実際にunsignedな計算しかしてないしね。ちなみに下記の2分探索でも念の為桁溢れを起こさないように中間値を計算している。

その5ではスキャンオーダを長さ順になるように変更したが、思いの外パフォーマンス上よろしくないようなので、一旦その4の方式に戻した。
また、探索方法を下限推定値からGR-nが見つかるまで線形に探索を行っていた所を、再びGR-nのサンプル値から上限を求め、下限推定値と上限の間で2分探索を行うように変更。これで、下限推定値と上限値が1000離れていても高々10回の試行で見つかることになりスピードアップが期待できるはず。

で、実際に計算時間を測ってみると

3:([0,1,3],[0,2,3])
0.000u 0.001s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
4:([0,1,4,6],[0,2,5,6])
0.000u 0.001s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
5:([0,1,4,9,11],[0,2,7,10,11])
5:([0,2,7,8,11],[0,3,4,9,11])
0.000u 0.002s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
6:([0,1,4,10,12,17],[0,5,7,13,16,17])
6:([0,1,4,10,15,17],[0,2,7,13,16,17])
6:([0,1,8,11,13,17],[0,4,6,9,16,17])
6:([0,1,8,12,14,17],[0,3,5,9,16,17])
0.007u 0.000s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
7:([0,2,3,10,16,21,25],[0,4,9,15,22,23,25])
7:([0,1,4,10,18,23,25],[0,2,7,15,21,24,25])
7:([0,1,7,11,20,23,25],[0,2,5,14,18,24,25])
7:([0,1,11,16,19,23,25],[0,2,6,9,14,24,25])
7:([0,2,7,13,21,22,25],[0,3,4,12,18,23,25])
0.072u 0.007s 0:00.08 87.5%     848+906k 0+0io 0pf+0w
8:([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
0.967u 0.001s 0:00.96 100.0%    720+821k 0+0io 0pf+0w
9:([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
13.301u 0.022s 0:13.32 100.0%   715+816k 0+0io 0pf+0w
10:([0,2,15,21,22,32,46,50,55,58],[0,3,8,12,26,36,37,43,56,58])
375.846u 0.443s 6:18.22 99.4%   717+818k 0+0io 0pf+0w
11:([0,1,4,13,28,33,47,54,64,70,72],[0,2,8,18,25,39,44,59,68,71,72])
11:([0,1,9,19,24,31,52,56,58,69,72],[0,3,14,16,20,41,48,53,63,71,72])
5403.706u 6.100s 1:30:20.05 99.8%       717+818k 0+0io 0pf+0w

n=10では計算時間は増加しているが、n=11は半分の時間で計算できている。

この分ならn=12は1〜2日間で計算できますかねぇ。

追記:22:00
あれ、n=10の計算結果が間違ってるな(正しくは最長マーク長55)。
う~ん、なんか探索漏れがあるっぽいような。