タグ別アーカイブ: haskell

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

ようやくStateモナドに開眼した気がするので、その9のコードを書き換えてみる。

ogr10.hs

時間/領域計算量における性能はその9とさして変わってないので念の為。

なるほど、コードは大分シンプルになったと思う。
ただ、ある程度慣れないと状態の受け渡しがどのように行われるのか、さっぱり見当がつかない。

結局、doブロックが(Stateモナドにおいても)単なる糖衣構文であることと、Stateモナドにおける>>=、returnの役割が飲み込めれば、Stateモナドもそれ程難しい概念ではないことが分かる。
とは言っても実際に手を動かしてコードを書いてみないとその辺りの実感が湧かないのも確か。

まあ、計算パラダイムが今まで慣れ親しんできた手続き型言語とまるで違うんだから、当たり前と言えば当たり前な話なんだが。
やはり頭の柔らかい若い内にいろんな計算概念に馴染んでおいた方が良いね。でないと、自分の様にちょっとしたことでもうんうん唸るはめになる。

Haskell::GR-nの生成/OGR-nの探索(その9)

OGR-nの探索もちょっと煮詰まってきたっぽいので、目先を変えてgr〜.hs、ogr〜.hsでGR型に関連した共通のコードを整理してモジュール化。両者で共用できるようにしてみた。

GR.hs

GR型もEq、Showクラスのインスタンスとすることで、(==)、showをそのまま適用できるようにしたので、プリティプリントのコードなども多少簡素になっている。

コンパイルは

% ghc -O2 –make gr9.hs

% ghc -O2 –make ogr9.hs

で、必要な依存関係を解決してくれるので、特にMakefileなどを用意する必要もない。

GRのモジュール化でgr9.hsも相当シンプルになった。

最初は必要性が分からなかった flip や、Maybe型に対応した関数の使い方に慣れてくると、その便利さがだんだん実感できてきて面白いね。

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

Stateモナドが理解できんと言っててもしゃあないので、まずは持ち回し方式でその7のコードをメモ化。

ogr8.hs

メモ化にあたって、コードを大幅に整理。

  •  GRを単なるタイプエイリアスから、マークの配列とその差分セットの配列をメンバーに持つdata typeとして定義。それに合わせてインタフェースとなる関数(fromList、newRank、===)などを定義
  • 関数pgr(n,m)をGR-nの内長さがmのものだけを計算するように仕様を変更(従来は、m以下のもの全てを計算していた)

今回はまずメモ化が実効的な手段足り得るかを確認するのが目的なので、その7で実装したような計算済みのOGRのsave/loadの機能はわざと省いてある。

で、まず計算時間をn=3〜10で測ってみる。

3:([0,1,3],[0,2,3])
0.001u 0.000s 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,2,7,8,11],[0,3,4,9,11])
5:([0,1,4,9,11],[0,2,7,10,11])
0.000u 0.002s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
6:([0,1,4,10,12,17],[0,1,8,11,13,17])
6:([0,4,6,9,16,17],[0,5,7,13,16,17])
6:([0,1,8,12,14,17],[0,3,5,9,16,17])
6:([0,1,4,10,15,17],[0,2,7,13,16,17])
0.000u 0.004s 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,2,7,13,21,22,25],[0,3,4,12,18,23,25])
7:([0,1,4,10,18,23,25],[0,2,7,15,21,24,25])
7:([0,1,11,16,19,23,25],[0,2,6,9,14,24,25])
7:([0,1,7,11,20,23,25],[0,2,5,14,18,24,25])
0.035u 0.007s 0:00.03 100.0%    906+1020k 0+0io 0pf+0w
8:([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
0.359u 0.007s 0:00.36 97.2%     746+839k 0+0io 0pf+0w
9:([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
3.885u 0.075s 0:03.98 99.2%     725+815k 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])
921.774u 1.211s 15:24.96 99.7%  723+813k 0+0io 0pf+0w

悪くはないが、良くもない。n=10ではその7にも負けてるし。
しかも、n=10の時にtopで大雑把にメモリ消費量を見てみると2GBを越えているので、これではn=11以降の計算には使い物にならない。

ただ、メモ化のテーブルだけでn=10時点でそこまでメモリを消費するとも思いがたいので、n=9で実行時のプロファイルを取ってみる。

ogr8.prof

先頭部分を抜粋

        Tue Jan 20 18:22 2009 Time and Allocation Profiling Report  (Final)
ogr8 +RTS -p -hd -RTS 9
total time  =        5.64 secs   (282 ticks @ 20 ms)
total alloc = 3,508,133,336 bytes  (excludes profiling overheads)
COST CENTRE                    MODULE               %time %alloc
intersect_p                    Main                  38.3   23.3
e_diff_a                       Main                  21.6   29.0
l2a                            Main                  13.5    7.5
pgr                            Main                   8.9    7.4
a2l                            Main                   5.7   18.8
newRank                        Main                   3.5    1.3
pgr_lt                         Main                   3.2    2.9
a_add_a                        Main                   3.2    6.5
a_add_e                        Main                   2.1    3.3

メモリ割当量がintersect_p、e_diff_a、a2lで結構な割合を占めている。

次に、ヒープメモリの種類別割当状況のグラフを見てみると、

ogr8-n9.png

UArrayはまあ順当に割当量が増加しているが、同様にARR_WORDSの割当量も相等に増加している。ARR_WORDSはクロージャやサンクを含むワーキングメモリなので、メモリ使用量の増加はメモ化のテーブルそのものと、メモ化の過程で使用したワーキングメモリの領域漏れの両方によるものと考えられる。

上記プロファイルの上位の関数について正格評価を行えばARR_WORDSの割当量は低減できるかもしれない。

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

n=13の探索が昨日ようやく完了。

13:([0,2,5,25,37,43,59,70,85,89,98,99,106],[0,7,8,17,21,36,47,63,69,81,101,104,106])
372392.773u 437.249s 227:30:46.57 45.5% 1841+1526k 0+0io 0pf+0w

結局9日以上かかったことになる。爆発どころの騒ぎじゃない。
やっぱり下位のGRの生成時のメモ化を実装せんと話にならん。

けど、Memoiseを何度読み返してもしっくりこんのよねぇ。
頭固くなってるなぁ。

しかも、下位のGRは探索の過程で爆発的に増加していくので、メモ化のためのテーブルの構造も工夫せんとすぐにメモのサーチにかかる計算コストが問題になってくるだろうし。
となるとData.MapやらSTUArrayやらの理解が必要になりそうだしなぁ。

何とも道は険しい。

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

その7でGR-100までの生成を目指していたが、GR-85時点で67457.77秒かかるようになってしまったので、一旦中止。この調子では後2週間かけてもGR-100まで届きそうにない。

とりあえず現時点での測定結果。

g7.txt

GR-70あたりからの計算時間の増加量が尋常でないようだ。

OGR-nの探索(その7)で計算済みのOGR-nをテキストファイルに書き出すようにしたので、GR-nの生成でも計算に先立ってこれを読み込めば、低位のGR-nの生成のスピードアップが期待できる。
低位のGR-nの生成のスピードアップが図れれば、高位のGR-nについてもそれなりにスピードアップが可能かもしれない。

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

ファイルI/Oの手習いとして、その6’のコードに計算したOGR-nの結果を一通りテキストファイルに書き出す機能を追加。さらに、2回目以降に実行した場合既に計算結果があれば、それを元にOGR-nのリストを作り、途中から計算を始めるようにした。

ogr7.hs

後、2分探索の部分もちょこっとだけ最適化。

ファイル出力の部分はある程度定石を覚えれば、それほど悩むことはない。
問題は、ファイル入力->オブジェクトの生成のようなパターン。

Haskellの遅延I/Oの元ではテキストファイルの入力処理は

do
  inh <- openFile 〜 ReadMode
  cs <- hGetContents inh

  ごにょごにょ

  hClose inh

のような感じで書くことができる。csにはオープンしたファイルの内容がString型として束縛される。一見、ファイルが全てメモリ上にロードされてしまうように見えるが、遅延I/Oのお陰で評価に必要な部分しか読み出されない。
で、ごにょごにょしている部分でcsにいろいろな関数を適用して、必要な計算を行う。
ところが、このごにょごにょの部分も普通は遅延評価されてしまうので、hCloseまでに正格評価を行わないと、必要な評価の前にファイルハンドルがクローズされてしまい、csには空のStringしか束縛されていないということが起こる。

ごにょごにょの部分で作るオブジェクトが単純な値やリストであれば、seqなどの正格評価を摘要するための演算子を用いればいいのだが、複雑な composite object になるとかなり厄介。
そういう用途に、Control.Parallel.Strategyモジュールがあるのだが、このあたりは正直まだ理解不能な領域だったり。

普通にテキストフィルター的な(ファイルのオープン/クローズを気にしなくてもいいような)処理を記述する場合は、遅延I/Oは直観的にコードを書き下せるのでとても便利なんだが。
このあたりの迂遠さというか、正格/非正格評価の区別をプログラマに要求するあたりが、関数型言語板なんかでのHaskell嫌いな人の攻撃材料になってるんだろうなぁと思ったり思わなかったり。

結局、

writeFile “/dev/null” $ show ほにゃらら

みたいに、オブジェクトを一旦プリンタブルな文字列に変換して、出力プリミティブを適用するという、かなり滅茶滅茶なやりかたでその場をしのいでいる。

実際のところの計算時間は、その6’のn=13の計算を一旦キャンセルして再度やり直し中。
n=12まで完了していて、

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.002s 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.000u 0.006s 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.028u 0.001s 0:00.02 100.0%    1264+1048k 0+0io 0pf+0w
8:([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
0.346u 0.001s 0:00.34 100.0%    855+708k 0+0io 0pf+0w
9:([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
4.583u 0.022s 0:04.60 100.0%    840+697k 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])
83.079u 0.120s 1:23.22 99.9%    840+696k 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])
1891.324u 1.534s 31:37.07 99.7% 840+696k 0+0io 0pf+0w
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])
7698.658u 9.628s 2:08:46.74 99.7%       840+696k 0+0io 0pf+0w

と、n=9以降のスピードアップに貢献してくれている。
n=13は現在計算中。

当初は、nの増加につれてGR-nの生成とは比べ物にならないほどの勢いで計算時間が増加していたので、あまりこの手法の導入に必要性を感じていなかった。
最近のコードの改良である程度実用的な時間で計算できるようになってきたので、計算過程を記録して途中から計算を始めることにもメリットが出てきたと思う。

なお、空でもいいからカレントディレクトリにogr.txt(結果が出力されるファイル)という名前のファイルがないとエラーになるのは、一応仕様です。

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

その4のコードを諸々クリーンアップ。

  • 無駄にhead/tailしていた所をパターンマッチで行うように整理
  • 計算済みのOGR-nを持ち回るようにした
  • PGR(n,m)のスキャンオーダを長さ順に整列されるように変更
  • lm、pgr関数をトップレベルに変更

ogr5.hs

今回は残念ながら若干時間計算量/領域計算量共に増加している。

PGR(n,m)の計算過程で明らかに重複して同じGRを計算している部分があるので、memo化により計算量の削減を図られると予想している。スキャンオーダの変更はこれを見越してのこと。

ただ、memo化のための方策は今の所まだいい案を思いついていない。mutableなオブジェクトを導入すれば今のコードスタイルを崩さずに達成できると思うが、安易にはやりたくない(IO monadicな計算のpure functionへの持ち込み方が理解できていないとも言う)。
かと言って、memoオブジェクトを持ち回るのは明らかに面倒くさい(やりかけて面倒なのでやっぱりあきらめた)。さらにmemoオブジェクトの増大化に連れて更新のコストも増大化することは容易に予想がつく。
再帰関数、メモ化でちょっとググってみると、不動点関数、Yコンビネータなんかがすぐヒットするが、まだまだこのあたりは理解できていない(知識としてはわかっても、コードには結びつかんものですね)。

memo化はこの冬の宿題ってところですかね。

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

次の2点を元にその3のコードを書き直してみた。

  1. GR-nの長さの下限をn*(n-1)/2で推定していたが、今はOGR-nが計算できるのでOGR-nの探索に当たって、あらかじめOGR-(n-1)以下を計算しておき、これを下限値とする。また、OGR-nの長さの下限値をOGR-(n-1)の長さ+1で推定する。
  2. その3まではOGR-nの探索に当たってGR-nの長さのサンプルを取り、サンプルの最小値からn*(n-1)/2までの間で最小となる組み合わせを探索してOGR-nとしていた。今回は上記1の推定値との組み合わせから長さを増加させていき、最初にGR-nの条件を満たしたものをOGR-nとする。

ogr4.hs

このコードによるn<=11までの計算時間の測定値は次の通り。なお、コマンドラインオプションについている +RTS -K1024Mは実行ファイルに組み込まれているランタイムシステムに対して指示を与えるためのもので、スタック領域を最大1024MBまで拡張することを許可する(デフォルトで最大8MBまで)。

% time ./ogr4 7 +RTS -K1024M
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,3,10,16,21,25],[0,4,9,15,22,23,25])
7:([0,2,7,13,21,22,25],[0,3,4,12,18,23,25])
0.148u 0.001s 0:00.14 100.0%    708+937k 0+0io 0pf+0w
% time ./ogr4 8 +RTS -K1024M
8:([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
2.088u 0.000s 0:02.08 100.0%    662+876k 0+0io 0pf+0w
% time ./ogr4 9 +RTS -K1024M
9:([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
25.232u 0.022s 0:27.17 92.9%    659+872k 0+0io 0pf+0w
% time ./ogr4 10 +RTS -K1024M
10:([0,1,6,10,23,26,34,41,53,55],[0,2,14,21,29,32,45,49,54,55])
288.654u 0.255s 4:48.95 99.9%   659+872k 0+0io 0pf+0w
% time ./ogr4 11 +RTS -K1024M
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])
10576.996u 8.109s 2:56:47.39 99.7%      659+872k 0+0io 0pf+0w

OGR-11で計算時間が爆発しているのは同様だが、計算時間そのものは40%程度削減できている。
OGR-8、9、10では逆に計算時間が増大しているがこれは長さの下限の推定値がn*(n-1)/2を下回っているのとOGR-(n-1)以下をあらかじめ計算することによるオーバーヘッドから来るものと予想される。n>=11以降では1の推定値のほうが上回っているようなので、今回のコードのほうが計算上有利だと思われる。

1はOGR-nの探索のためのコードを書き出した頃から考えていたのだが、計算した長さのリストを各関数に持ち回るのが面倒だったので今まで伸ばし伸ばしにしてきた。今回、コードを書き直すに当たって下限の推定値を求める関数 lm を呼び出している関数全てを calc_ogr 関数のwhere節以下に移動し、長さのリストをcalc_ogrに渡す以外は前と同様に lm を呼び出すことで1の推定値が得られるように変更した。

1を反映させたコードを昨晩書き走らせてみたのだが、OGR-11の計算で4時間たっても終わらなかったので、あきらめて寝てしまった。
ところが今朝起きて一番に2のアイデアがひらめき、10分でコードを書き直せた。その3のコードのように計算のキャンセルを考える必要もなくなり、GR-nのサンプルも計算しなくて良くなったので想像以上にコードがシンプルになって我ながらびっくりな感じ。

このような形で閃きが得られたのは本当に久しぶりな気がする。
λの神様のクリスマスギフトか、はたまたH.カリーさんのお恵みか。
ま、思考のピースが寝ている間に適当にガベージコレクションされただけってところかも知れないが、ちょっとだけ幸せなクリスマスになった。

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

その2のコードを諸々クリーンアップした。
ついでに、結果をプリティプリントする関数を追加。

ogr3.hs

で、計算時間を測ってみる。

% time ./ogr3 7
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,3,10,16,21,25],[0,4,9,15,22,23,25])
7:([0,2,7,13,21,22,25],[0,3,4,12,18,23,25])
0.068u 0.001s 0:00.06 100.0%    768+966k 0+0io 0pf+0w
% time ./ogr3 8
8:([0,1,4,9,15,22,32,34],[0,2,12,19,25,30,33,34])
1.000u 0.001s 0:01.00 100.0%    680+856k 0+0io 0pf+0w
% time ./ogr3 9
9:([0,1,5,12,25,27,35,41,44],[0,3,9,17,19,32,39,43,44])
13.468u 0.015s 0:13.48 99.9%    681+857k 0+0io 0pf+0w
% time ./ogr3 10
10:([0,1,6,10,23,26,34,41,53,55],[0,2,14,21,29,32,45,49,54,55])
142.480u 0.090s 2:22.59 99.9%   680+856k 0+0io 0pf+0w
% time ./ogr3 11 +RTS -K1024M
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])
17150.461u 3.979s 4:46:30.88 99.7%      680+856k 0+0io 0pf+0w

う~ん、OGR-11の計算でいきなり計算時間が大爆発してるなぁ。

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

最近、Haskellのコードを書き散らかして多少なりとも勘所が見えてきたのか、ちょっと前に書いたコードの不恰好な所が目に付く様になってきた。

で、今の知識でGR-nを生成するコードを書き下してみる。

-- gr5.hs
import System
import List
main :: IO ()
main = do { args <- getArgs
; let [n, m] = if length args == 2 then map read args else [4,20]
; putStrLn $ unwords $ map show $ take m $ gr n
}
gr :: Int -> [[Int]]
gr n
| n<1         = []
| n==1        = [[0]]
| n==2        = [[0, x] | x<-[1..]]
| otherwise   = scanline 1
where
grs = gr $ n - 1
lm = n * (n - 1) `div` 2
scanline :: Int -> [[Int]]
scanline m = let {
; zs = filter gr_p $ zip [lm..(lm + m -1)] $ reverse $ take m grs
} in [ys ++ [x] | (x, ys)<-zs] ++ (scanline $ m + 1)
where
gr_p :: (Int, [Int]) -> Bool
gr_p (x, ys)
| x <= last ys        = False
| otherwise           = null $ intersect [x-y|y<-ys] $ diff_set ys
diff_set :: [Int] -> [Int]
diff_set []     = []
diff_set (x:xs)
| null xs     = []
| otherwise   = [x'-x|x'<-xs] ++ diff_set xs
--

書き直すに当たって、

  • リスト処理をもっと工夫できないか見直す(標準プレリュードの関数をある程度把握できれば、無駄なコードを省けるようになってくる)
  • !!演算子(リストのインデックスアクセス)に頼らない
  • map式をlist comprehensionで書き直せないか検討する(単純なmap式なら書き直したほうが見やすい場合が結構ある。ただし、$でつながれた式などの途中のmapを書き換えると逆に意味が取りにくくなることもあるので無闇に書き換えない)
  • 無駄な引数渡しをしてないかチェック
  • パターンマッチング(x:xsなど)の活用

などに注意してみた。これは、Haskellに限らずLispなどの処理系でも当てはまる点は多いと思う。

ちなみに、書き直したコードでGR-40の一つ目を計算するのにかかる時間を測定すると、

% time ./gr5 40 1
[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]
517.714u 0.278s 8:39.96 99.6%   654+877k 0+0io 0pf+0w

と多少高速化できた。やはり無駄なことをやっていた所がそれなりにあったということなのだろう。