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の割当量は低減できるかもしれない。

桂冠詩人(ALI PROJECT)


久々のALI PROJECTのシングルコレクション + PV DVDということで購入。
どちらかというと、DVD目当て。

相変わらずのコスプレっぷりが素晴らしいというか、凄まじい。PVのセットの作りこみも力が入ってるわぁ。
デフォルトのゴスロリ(白/黒)はもちろんだが、「勇侠青春謳」の極妻コスプレがすごいつぼにはまった。
Voの宝野アリカに和装+日本髪+刺青がこれほどお似合いになるとは思わなんだ。
改めてみると、宝野アリカってやっぱり美人さんやねぇ。

「我が﨟たし悪の華」は割と今までのALI PROJECTらしいPVでまあおとなしめの感じ。って、この出来でおとなしめな印象になってしまうのもある意味凄いが。

「鬼帝の剣」では衣装やメイクは妖艶な感じでかっちょいいんだが、バストショットの映像とそのエフェクトがメインなのでPVとしては面白みに欠けるか。

それにしても、よくこんな文語調というか書き言葉で作詞ができるなぁ。それでのりのりのメロディラインで歌えちゃうし。
相当な文学オタ少女だったと見るがどうか。

奥歯欠けた(泣)

昨夜、酒のつまみにクラッカーを齧ってると「じゃりっ」と違和感が。

吐き出してみると歯の欠片の模様。確かに、舌で右上の奥歯の辺りを触ると鋭い断面ができるようだ。欠片の大きさは3mm角程度でさすがに奥歯が割れたというところまでいかなかったようだ。痛みは全然ないので神経の部分までは達していないのか。

何はともあれ、診察の予約を入れることに。

しばらくの間歯科からおさらばできるかと思ってたのに、また通院の日々が始まるのね(泣)。