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

しょうもないミスをしていたのと、2分探索の過程で明らかに無駄な計算をしていたので修正。

ogr6_.hs

改めて計算時間を測定。

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.002u 0.001s 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.005u 0.001s 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.031u 0.001s 0:00.03 100.0%    720+816k 0+0io 0pf+0w
8:([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
0.389u 0.007s 0:00.39 97.4%     738+837k 0+0io 0pf+0w
9:([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
5.128u 0.001s 0:05.12 100.0%    719+815k 0+0io 0pf+0w
10:([0,1,6,10,23,26,34,41,53,55],[0,2,14,21,29,32,45,49,54,55])
91.360u 0.105s 1:31.48 99.9%    717+813k 0+0io 0pf+0w

n=10も正しい計算結果が得られているし、計算時間も削減されている。
n=11は計算中なので、完了後追記。

追記:
n=11の計算が完了。
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])
1946.184u 1.594s 32:33.37 99.7% 717+813k 0+0io 0pf+0w

思っていたよりも、相当早く完了したので、ついでにn=12にもチャレンジ中。

追記’:
n=12の計算が完了。
12:([0,2,6,24,29,40,43,55,68,75,76,85],[0,9,10,17,30,42,45,56,61,79,83,85])
9803.742u 9.778s 2:43:56.58 99.7%       717+813k 0+0io 0pf+0w

あれ? 1日ぐらいはかかるかと思ってたのに、3時間足らずで計算できちゃった。結果も間違ってないようだし。
んでは、n=13もチャレンジしてみますか。

ただいま

本日、実家から帰宅。

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

高校時分の友人が子連れ(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)。
う~ん、なんか探索漏れがあるっぽいような。

Haskell::GR-nの生成(その7)

もう飽きたと言いつつ高速化のネタを思いついたのでその6のコードを修正。

gr7.hs

関数grの返り値をGRとそのdiff_setのタプルのリストに変更した。
目的はずばりdiff_set関数のメモ化による時間計算量の削減にある。

その6のコードと同じ条件で計算時間を比較してみる。

その6:
40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
191.898u 0.381s 3:36.65 88.7%    513+665k 0+0io 0pf+0w
その7:
[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
107.748u 0.154s 1:59.35 90.3%    544+631k 0+0io 0pf+0w

さらに半分程度に計算時間を削減できている。

diff_setの結果がメモ化されているのはもちろんだが、g∈GR-nでgの計算に使用したg’∈GR-(n-1)、diff_set(g’)が既知の時、max(g)、g’、diff_set(g’)よりdiff_set(g)が容易に計算できる。このため、diff_set関数そのものが不要になった。詳しくはコードを参照のこと。

もちろん、メモ化により領域計算量は増加している訳で、その5の時のコードと比べてもヒープメモリの使用量は増加している。

それでも、その4の時の計算時間から比べるとオーダで1桁以上高速化が達成できているので、GR-100の計算も現実的になってきたと思う。GR-100近辺での平均的なマーク長を推定する上でもぜひ、GR-100の計算はやっておきたい。

と言う訳で、現在GR-3からGR-100までの一つ目の結果を順次計算中。
GR-68の計算が完了して、その計算時間に5851秒かかっている。
後2日程度でGR-100まで手が届くかな?

その時には、改めてGR-nの計算にかかる時間計算量コストの推定を行いたいと思う。

追記:1/6 11:55
現在GR-79の計算が完了し、その計算時間が24863秒。
今週中にGR-100までは無理っぽいかなぁ。

Haskell::GR-nの生成(その6)

Data.Array.Unboxedを使用し、計算量の削減を図れないか試してみる。

gr6.hs

Data.Array.Unboxedはimmutable objectであることを除けば、Cの配列に要素の型とインデックスの範囲情報が付加されたものと思えば良いらしい。リストに比べるとメモリ占有量、ランダムアクセス速度に優れる。反面、個々の要素の操作のバリエーションはリストに比べると、やや制限がかかるので計算の柔軟性には欠ける面があると言える。

今までのコードではGR-nの個々の計算結果を Int 型のリストで実装していたが、今回のコードでは要素の型が Int16 の Data.Array.Unboxed に格納するように実装した。ちなみにGR-nのマークの型をInt16にすると、計算中の桁溢れの恐れがあるが、長さの下限の推定値の式 n(n-1)/2 から

n=50 -> 1225
n=100 -> 4950
n=200 -> 19900
n=256 -> 32640
n=257 -> 32896

なので、n=100程度までの生成・探索に問題とはならないとは思われる。

これで全体としてのメモリ消費量が抑えられる事が予想される。
一方、一つ一つのGRの計算時にArray <-> リストの変換によるオーバーヘッドが伴うので計算時間の面で有利かどうかは実際に測定してみないとはっきりしない。

で、まずはプロファイルオプション無しでコンパイルしたバイナリでGR-40の一つ目を計算するのにかかる時間を測定し、その5’のコードと比較してみる。

その5′:
40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
441.522u 0.388s 8:14.67 89.3%    496+681k 0+0io 0pf+0w

その6:
40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
191.898u 0.381s 3:36.65 88.7%    513+665k 0+0io 0pf+0w

おお、倍ぐらいにスピードアップしてるじゃまいか。

次にプロファイルオプション付きでコンパイルしたバイナリでプロファイルを測定。

結果の抜粋。

        Thu Jan  1 01:57 2009 Time and Allocation Profiling Report  (Final)
gr6 +RTS -hd -p -RTS 40 1
total time  =      321.24 secs   (16062 ticks @ 20 ms)
total alloc = 38,033,292,852 bytes  (excludes profiling overheads)
COST CENTRE                    MODULE               %time %alloc
intersect_p                    Main                  51.3    3.2
diff_set                       Main                  30.3   85.4
l2a                            Main                  13.9    2.9
gr                             Main                   2.9    6.5
gr_p                           Main                   1.6    1.9

intersect は Array に適した実装に変更したので、時間計算量コストの割合は結構低下した。反面diff_setのコストの割合が上昇しているので合わせてのコストの割合はそれ程低下していない。さらにリストからArrayへ変換するコストもそれなりに占めているので、ループ内の時間計算量コストの割合はそれ程変化していないとも言える。
ただ、全体の計算時間は半分にまで削減できているので、時間計算量の面では Unboxed Array を実装に用いたのは正解のようだ。

次にヒープメモリの使用量をグラフにする。

gr6.png

その5’の結果に比べれば一目瞭然でヒープメモリの使用量が1/3程度まで削減できている。
ところで、一定の時間間隔で使用量がちょこっと下がっている所がある。このタイミングで、GCのgeneration scavenging が行われているのかな?

これはなかなか幸先の良い結果が得られましたね。

OGR-n の探索にも Unboxed Array の摘要が良さげな感じ。

Haskell::GR-nの生成(その5′)

去年は(O)GR-n関連のコードをいろいろ書き散らかしてはみたが、まだ真面目に性能測定をやっていないので、そろそろプロファイル測定に手を付けてみる。

そこでプロファイル測定用にその5のコードを若干修正してみた。

gr5_.hs

GHCのプロファイラではトップレベルの関数単位でしか測定できないので、gr_p、diff_set、intersect(myIntersectでラップ)の性能上のポイントになりそうな関数をトップレベルに移動してある。

GR-40の一つ目を計算する時のプロファイル測定の結果の一部を抜粋

        Thu Jan  1 00:12 2009 Time and Allocation Profiling Report  (Final)
gr5 +RTS -hd -p -RTS 40 1
total time  =      700.94 secs   (35047 ticks @ 20 ms)
total alloc = 28,245,003,008 bytes  (excludes profiling overheads)
COST CENTRE                    MODULE               %time %alloc
myIntersect                    Main                  86.1    1.0
diff_set                       Main                   9.2   89.2
gr_p                           Main                   3.6    2.9
gr                             Main                   1.1    6.9

非常に当たり前の結果だが、ループの一番内側で呼び出している関数 intersect、diff_set の実行時間が合わせて全体の95%を占めていることがわかる。

さらに、ヒープメモリの使用量をグラフ化してみた。
gr5_.png
こちらも非常にわかりやすい結果になった。

これを基準に、GR-nの計算にData.Array等を使った場合にどのように変化するか調べてみたいと思う。

明けましておめでとうございます

という訳で、記念かきこ。

お陰様でブログを始めて(3週間程度^_^;ですが)から、目出度く年を越すことができました。

これからもどうでもいいことを適当に書き綴っていけたらいいなと思ってますので、物好きな方は生温かい目で見守ってやってくださいまし。

ゆるめのつっこみも歓迎です(きつめのは本人がへこみますので、適当に手加減をしてくれると有難いです)。