maoeの日記

ここは研究室関連の話題専用です.メインのブログはmaoeのブログです.VMware Playerの情報を求めて飛んできた方は報告: VMware Playerへどうぞ.

SICP勉強会関連はキーワード「SICP勉強会」からどうぞ.

2009-12-21

みなさん元気ですか?僕は相変わらずHaskell Haskell言ってます。

ところで、土居先生が退官されますね。みんな祝賀会には参加するのかなあ?

2009-03-23

隊長 11:35

祝賀会に来たらしいが、連絡が取れない。

メール 11:35

突然メールを送ってすんません。お手伝い要請が来たのです。興味がある方は是非に。あるいは興味がありそうな人がいたら是非。

2006-06-26

[] N-Queens 05:50

今日の問題2.42は非常に時間がかかった.驚いたのはsafe?の考え方の違い.やっぱり複数でやると人それぞれ解き方が違うので面白い.

以下,答えなのでやってない人は見ないように.

考え方としては直感通りにやればよい.つまり,次の3点*1について考えればよい.

新たに配置するクイーンに対して,

をすべて満たせばその場所は妥当であるといえる.図にすると以下の通り.

f:id:maoe:20060627053307p:image

これをそのままコードに落とせばよい.

(define empty-board '())

(define (adjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

(define (safe? k positions)
  (let ((head (car positions)))
    (let rec ((i 1) (positions (cdr positions)))
      (if (null? positions)
          #t
          (and (not (= head (car positions)))
               (not (= (+ head i) (car positions)))
               (not (= (- head i) (car positions)))
               (rec (+ i 1) (cdr positions)))))))

上記のsafe?のように内部カウンタ変数を持たせればadjoin-positionでkを使用する必要が無くなり若干メモリ効率がよい.さらに各チェックをandでまとめているが,andはR5RSより最初に偽の値を返したところで評価が止まり, 偽の値が返され,残りの式は評価されないので実行効率も良い.

OSS WEBの解答SICP memoの解答とともにプロファイルを取ってみた.

テストはsafe?とadjoin-positionを各解答ごとに用意し,その他の関数はすべて同じものを使用した.以下に(queens 12)を評価した結果を示す.

$ gosh -ptime maoe.scm
Profiler statistics (total 3960 samples, 39.6 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
safe?                                              10103868  0.0017  1729( 43%)
flatmap                                                 12 335.0000   402( 10%)
enumerate-interval                                 10945857  0.0004   389(  9%)
filter                                             10103880  0.0003   344(  8%)
adjoin-position                                    10103868  0.0003   301(  7%)
...

$ gosh -ptime oss-web.scm
Profiler statistics (total 9176 samples, 91.76 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
safe?                                              10103868  0.0043  4296( 46%)
(safe? #f)                                         37512342  0.0006  2342( 25%)
adjoin-position                                    10103868  0.0006   650(  7%)
enumerate-interval                                 10945857  0.0005   497(  5%)
append                                              841989  0.0039   327(  3%)
...

$ gosh -ptime sicp-memo.scm
Profiler statistics (total 6012 samples, 60.120000000000005 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
conflicts?                                         37512342  0.0005  1815( 30%)
safe?                                              10103868  0.0008   841( 13%)
abs                                                75024684  0.0001   672( 11%)
adjoin-position                                    10103868  0.0007   666( 11%)
enumerate-interval                                 10945857  0.0005   525(  8%)
...

*1:上下で2点と数える

tcublolotumtcublolotum2007/04/04 06:50<a href=http://lianejensen1976.funpic.de/1.html>cheap airline tickets</a> cheap airline tickets http://lianejensen1976.funpic.de/1.html cheap airline tickets

ryhwepempyporyhwepempypo2007/04/07 01:28 First, to get that <a href=http://myurl.com.tw/kj1m>lindsay lohan naked</a> [url=http://myurl.com.tw/kj1m]lindsay lohan naked[/url] considering your opinion of the home to be back. He broke it off, and she <a href=http://myurl.com.tw/emd3>gallery of lindsay lohan</a> [url=http://myurl.com.tw/emd3]gallery of lindsay lohan[/url] was embarrassed, everyone rose when to.

hloqubihiphloqubihip2007/04/08 03:55 Now i took the dorm mothers that i took the <a href=http://ls.tc/short/QEZUF/>jennifer aniston nude</a> jennifer aniston nude http://ls.tc/short/QEZUF/ jennifer aniston nude little slave - first man.

amvockelamvockel2007/04/11 12:49<a href=http://roccofoloper.sblog.cz>sauna belt</a> sauna belt http://roccofoloper.sblog.cz sauna belt

pziwrvkbizpziwrvkbiz2014/12/02 17:56wyoloepjmbc, <a href="http://www.evtxhiondw.com/">lcpechucdk</a> , [url=http://www.ieocmyblmg.com/]udlddnlopv[/url], http://www.jnknyijfvx.com/ lcpechucdk

2006-06-12

[] 型を意識したプログラミング 04:18

今日は問題2.29に手こずった.みんなが解いているところを見ていると,その理由はプログラミングの際に型を意識していないことが原因のように思われた.この問題では構成子make-mobileとmake-branchという2つの型を使って2進モービルを表現しているので,Schemeのような静的な片づけを行わない言語を利用すると,再帰して木を下っていく際にどちらの型の引数を取るのかわかりにくい.そこでHaskellで書き直してみる*1

data Mobile = Mobile Branch Branch | Weight Int deriving Show
data Branch = Branch Int Mobile deriving Show

leftBranch :: Mobile -> Branch
leftBranch (Mobile l r) = l
leftBranch _            = error "no branch"
rightBranch :: Mobile -> Branch
rightBranch (Mobile l r) = r
rightBranch _            = error "no branch"
branchLength :: Branch -> Int
branchLength (Branch l m) = l
branchStructure :: Branch -> Mobile
branchStructure (Branch l m) = m

totalWeight :: Mobile -> Int
totalWeight (Weight w) = w
totalWeight (Mobile l r) = totalWeight l' + totalWeight r'
    where (l',r') = (branchStructure l,branchStructure r)

isBalanced :: Mobile -> Bool
isBalanced (Weight w) = True
isBalanced (Mobile l r) = moment l == moment r && isBalanced l' && isBalanced r'
    where moment :: Branch -> Int
          moment (Branch l m) = l*totalWeight m
          (l',r') = (branchStructure l,branchStructure r)

-- test data
e0,e1,e2 :: Mobile
e0 = Weight 0
e1 = Mobile (Branch 1 (Weight 2)) (Branch 2 (Weight 1))
e2 = Mobile (Branch 1 (Mobile (Branch 1 (Weight 2))
                              (Branch 2 (Weight 1))))
            (Branch 3 (Weight 1))
e3 = Mobile (Branch 1 (Mobile (Branch 1 (Weight 1))
                              (Branch 2 (Weight 2))))
            (Branch 3 (Weight 1))

Haskellではdata宣言を用いることで構築子を直截的*2に表現できる.インタプリタ上で:t 構築子して型を確認すると以下のようになる.

> :t Mobile
Mobile :: Branch -> Branch -> Mobile
> :t Weight
Weight :: Int -> Mobile
> :t Branch
Branch :: Int -> Mobile -> Branch

さらにサンプルを使ってテストしてみると以下のようになる.

> totalWeight e0
0
> totalWeight e1
3
> totalWeight e2
4
> totalWeight e3
4
> isBalanced e0
True
> isBalanced e1
True
> isBalanced e2
True
> isBalanced e3
False

*1:errorは初めて使う.こんな使い方でよいのだろうか.

*2SICPっぽくしてみた

2006-05-10

[] 素人くさいSICP読書会を抜いたみたいだよ 14:52

定期開催にしてからここに書く意味が薄れてきた.まあいいか.

ところで,週2回かつ一度に4時間くらいやっているおかげか,気がついたら素人くさいSICP読書会を追い抜いていたらしい.これですんなりと素人くさいSICP読書会に潜入する準備が整ったわけだ.あとはノートPCがあればなぁ,と寂しい懐を確認するある日の午後.