maoeの日記

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

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

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点と数える

tcublolotumtcublolotum 2007/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

ryhwepempyporyhwepempypo 2007/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.

hloqubihiphloqubihip 2007/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.

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

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

ゲスト



トラックバック - http://doilab.g.hatena.ne.jp/maoe/20060626