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化はこの冬の宿題ってところですかね。

iPodTouch



長年使用してきたiPod mini(6GB)のバッテリが大分へたってきたので、帰省前にiPodTouchを衝動的に購入。
購入当初は、6GBで収まりきらなくなったミュージックライブラリと、ムービーがある程度持ち出せるようになればそれでいいやと思っていたので、それ以上の利用スタイルは全然想定していなかった。

ところが、帰省して実家のWi-Fiな環境下で使うようになって考えを改めた。

思いの他Safari、メーラの使い勝手が良く、Gmailのチェック、ちょっとした検索には結構事足りる。
今は無料Appを落としまくっていろいろと試しているところ。

実家はWi-Fiな環境をしっかり整備しておいたのだが、自宅では手に届く範囲にLANハブがあるので今まで敢えてWi-Fiな環境を整える気にはならなかった(一応ルータは802.11b/g対応なんだが、AP機能を有効にして長期間起動状態が続くと動作が不安定になることがあったので、AP機能は切っている)。DS、PSPも別に無線で繋ぎたいほどには使っていなかったし。
この機会にAPを導入しようかしらね。

手にしてしばらくはタッチスクリーンの操作(特にソフトウェアキーボードでの入力)でいらっと来ることも多かったけど、慣れてくるとこれが当たり前に思えてくるからなんとも面白い。

カバーフローとかビジュアル的なところはかっちょいいとは思うけど、まあそれだけかな。
音楽を聞くときはプレイリストかアルバム単位でしか聞かないので、classic なUIでも自分には十分な気がする。これも慣れの問題か。

帰省

昨日より7ヶ月ぶりに実家に帰省。

山形新幹線が何かトラブっていたようだが、自分はひかり乗車だったので問題無し。

乗車率もピークではなかったようで、乗降車も苦労なく無事家に帰り着けた。

にしても、自宅(千葉)と実家(京都)でなんでこんなに気温差があるんですかね。
出発の時はダウンコートを着てたら結構汗をかく位だったのに、京都駅に着いたら吐く息が白いんですけど。
ここのところ関東が好天続きだったせいか余計に気温差を感じる。

ま、実家にいれば上げ膳据え膳だし、何より落ち着くのが有難いんですけどね。

コンピューティング環境が貧弱になるのはちょっと難点だが。

親知らず抜歯その後

先ほど、歯科医に行ってきて経過観察と傷口の消毒をしてもらってきた。

昨晩は、寝る前にちょっと疼く感じがあったので一応鎮痛剤を1錠のんだ。出血も多少続いていたみたいでずっと血の味が口の中に残っていた。

今朝起きた時は痛みも無く、出血も止まっていたようだ。歯を磨いたときは見事に口の中がイチゴ色になったけど。特に顔が腫れるようなことも無く(頬の脂肪にまぎれているだけかも^_^;)話に聞くような後遺症とはほとんど無縁ですみそうな感じ。
口を大きめに開けると多少違和感はあるかな?

ちなみに傷口はすぐに塞がるけど、抜いた後の歯肉が盛り上がって平坦な状態になるには3ヶ月ほどかかるらしい。

次の左側の抜歯の予約を入れる時、受付の看護師さんに「先生が左のほうが面倒かもなぁ、て言ってましたよ」と、さらっと脅し文句を聞かされる。

小心者なんであんまり怖いことは言わないでください。

親知らず(右下)の抜歯

本日は半日病院通いだったのだが、終わった後一旦家に帰り先のブログを書いて一服してから歯科医に向かった。

今回は右下の親知らずの抜歯。

手前の奥歯に引っかかっている部分をドリルでカット。この時先生が「う~ん、面倒やなぁ」とかこっちが顔面蒼白になりそうなことをつぶやくので、これはいよいよ噂に聞く怖い治療が始まるのか?!と身構えたり。

ドリルでの作業が終わると、ステンレス製のやっとこ(のようなもの?顔にタオルをかけられていたので形状は見えなかった)で一気に抜いたらしい。というか、麻酔が完璧に効いていたのでいつ抜かれたのか全然わからなかった。
その後は止血綿を銜えさせられてしばらく放置プレイ。実はこの時点でも抜かれたのかどうかわかっていなかった。

5分ほどして、「は~い、これで終わりです。口ゆすいでくださいねぇ」と言われて初めて抜歯されてたことに気が付く。ちょっと間抜けっぽいんですけど。

その後先生の説明。抜いた現物を見せながら、先生曰く抜歯した歯の根元の部分が結構太めしっかりしているらしく、もっと歳をとって骨が硬くなって(柔軟性がなくなって)からだと抜くのが大変になるらしい。

折角なので抜いた現物は記念にもらって帰ることに。歯肉がちょっとこびりついていて微妙にグロい。

鎮痛薬と抗生物質の処方箋を出してもらって、帰りに薬局へ。
明日、経過観察と傷口の消毒にもう一度通院することになった。

それにしても、トータルの治療時間で40分もかかってなかったんですけど。治療内容もえらいあっさりしてた気がするし。あんなに怖がって損した気分。
それとも実はとっても腕のいい先生だったりするんですかね。

今のところ麻酔が効いているのか、痛みはほとんど無い。口内から血の味が抜けないのはまだ微妙に出血してるんかな。

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の計算でいきなり計算時間が大爆発してるなぁ。

クリスマスパーティ

昨晩行きつけのバーのクリスマスパーティがあったので顔を出してきた。

昨日はあまり体調が良くなかったのだが、夕方には気分も良くなり遅めの時間にバーに向かう。
まあ、年の瀬の挨拶でもあるしね。

到着した時には既に出来上がっている人累々で、かなりカオスな状態。
最初はシャンパンをちびちび適当に回りの人と話をしていただけだが、23:00頃には人もはけてきて落ち着いて飲めるようになってきた。

料理もいろいろ用意されて、遅い時間に行ったにも関わらずしっかりパーティを堪能させていただきました。

パーティ後は終電で帰宅。さっさと歯を磨いて就寝。

今日の気分はそれなり。

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

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