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までは無理っぽいかなぁ。