Hatena::Groupcsnagoya-sicp

gabuchanの日記

2008-11-10

問題1.14

| 15:28

木構造のイメージでも作ろうかと思ったけど面倒なのでダラダラ出力させてみた。

(define (count-change amount)
  (cc amount 5 0))

(define (cc amount kinds-of-coins space)
  (print #`",(make-string space #\\-)(cc ,amount ,kinds-of-coins)")
  (cond [(= amount 0) 1]
        [(or (< amount 0) (= kinds-of-coins 0)) 0]
        [else (+ (cc amount
                     (- kinds-of-coins 1)
                     (+ space 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins
                     (+ space 1)))]))

(define (first-denomination kinds-of-coins)
  (cond [(= kinds-of-coins 1) 1]
        [(= kinds-of-coins 2) 5]
        [(= kinds-of-coins 3) 10]
        [(= kinds-of-coins 4) 25]
        [(= kinds-of-coins 5) 50]))

(count-change 11)
$ gosh 1.14.scm
(cc 11 5)
-(cc 11 4)
--(cc 11 3)
---(cc 11 2)
----(cc 11 1)
-----(cc 11 0)
-----(cc 10 1)
------(cc 10 0)
------(cc 9 1)
-------(cc 9 0)
-------(cc 8 1)
--------(cc 8 0)
--------(cc 7 1)
---------(cc 7 0)
---------(cc 6 1)
----------(cc 6 0)
----------(cc 5 1)
-----------(cc 5 0)
-----------(cc 4 1)
------------(cc 4 0)
------------(cc 3 1)
-------------(cc 3 0)
-------------(cc 2 1)
--------------(cc 2 0)
--------------(cc 1 1)
---------------(cc 1 0)
---------------(cc 0 1)
----(cc 6 2)
-----(cc 6 1)
------(cc 6 0)
------(cc 5 1)
-------(cc 5 0)
-------(cc 4 1)
--------(cc 4 0)
--------(cc 3 1)
---------(cc 3 0)
---------(cc 2 1)
----------(cc 2 0)
----------(cc 1 1)
-----------(cc 1 0)
-----------(cc 0 1)
-----(cc 1 2)
------(cc 1 1)
-------(cc 1 0)
-------(cc 0 1)
------(cc -4 2)
---(cc 1 3)
----(cc 1 2)
-----(cc 1 1)
------(cc 1 0)
------(cc 0 1)
-----(cc -4 2)
----(cc -9 3)
--(cc -14 4)
-(cc -39 5)

問われているスペースとステップ数の増加の程度は後で書く。

問題1.15

| 15:38

考えるよりもプログラムが書きたいので問われているステップ数を数えるプログラムを書いたら、問題のプログラムとほぼ同じものが出来たというオチ。

(define (step n)
  (define (step-iter n count)
    (if (not (> n 0.1))
        count
        (step-iter (/ n 3.0) (+ count 1))))
  (step-iter n 0))

(print (step 12.15))

ということで、a.の答えは

$ gosh 1.15.scm
5

悩むのはb.のスペースとステップ数。。。

ステップ数は

(p (sine (p (sine ...

って増えていくから、2n なんだけどSICPが言う「増加の程度」としては、

n^2 ステップが必要なプロセスも、1000n^2 ステップが必要なプロセスも 3n^2 + 10n + 17 ステップが必要なプロセスもすべてΘ(n^2)の増加の程度という.

なので、よりスペースやステップに影響を与える変数に着目して、2n ステップは答えとしてはΘ(n) かなぁ。(かなり自信ないです。)

スペースも同様にΘ(n) かなぁ。(かなり自信ないです。)

問題1.16

| 15:55

fast-exptを反復的プロセスな手続きにしてみた。

(define (fast-expt b n)
  (define (square x) (* x x))
  (define (fast-expt-iter b n a)
    (cond [(= n 0) a]
          [(even? n) (fast-expt-iter (square b) (/ n 2) a)]
          [else (fast-expt-iter b (- n 1) (* a b))]))
  (fast-expt-iter b n 1))

Gaucheは組み込みで even? が使えるっぽい。

問題1.17

| 16:03

対数的ステップ数の乗算手続き。

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (mul x y)
  (cond [(= y 0) 0]
        [(even? y) (double (mul x (halve y)))]
        [else (+ x (mul x (- y 1)))]))

問題1.18

| 16:03

問題1.17は再帰的プロセスを生成するので反復的プロセスな手続きにしてみる。

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (mul x y)
  (define (mul-iter x y result)
    (cond [(= y 0) result]
          [(even? y) (mul-iter (double x) (halve y) result)]
          [else (mul-iter x (- y 1) (+ result x))]))
  (mul-iter x y 0))

問題1.20

| 16:29

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(gcd 206 40)

こんな最大公約数を求める手続きがあったとして、「正規順序評価と作用的順序評価で remainder 演算がそれぞれ何回実行されるか。」という問題。

手動デバッグが面倒なのでプロファイルを使いました。

$ gosh -ptime 1.20.scm | grep remainder
remainder                                                4  0.0000     0(  0%)

作用的順序で評価する Gauche では4回だそうです。つまり、作用的順序評価では4回。

正規順序といえば・・・やっぱり Haskell ですよね。

main = print $ Main.gcd 206 40

gcd :: Integer -> Integer -> Integer
gcd a 0 = a
gcd a b = Main.gcd b $ remainder a b

remainder :: Integer -> Integer -> Integer
remainder a b = a `rem` b

組み込みで gcd 関数があるので、明示的にMain.を追加しています。remainder 手続きは rem 関数があるのですが、組み込み(?)関数はプロファイルに上がってこないので、ユーザ定義でラッパーを作りました。

プロファイルを有効にしてコンパイル

$ ghc -prof -auto-all -o haskell_gcd 1.20.hs

プロファイルを有効にして実行

$ ./haskell_gcd +RTS -p

プログラム名.prof というファイルが作られるので見ます。

$ less haskell_gcd.prof
        Mon Nov 10 15:10 2008 Time and Allocation Profiling Report  (Final)

           haskell_gcd +RTS -p -RTS

        total time  =        0.00 secs   (0 ticks @ 20 ms)
        total alloc =      17,832 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

CAF                            GHC.Handle             0.0   48.3
CAF                            Main                   0.0   50.5


                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0     0.0  100.0
 CAF                     Main                                                 152           3   0.0   50.5     0.0   51.7
  main                   Main                                                 158           1   0.0    0.1     0.0    1.2
   gcd                   Main                                                 159           5   0.0    0.9     0.0    1.0
    remainder            Main                                                 160           4   0.0    0.2     0.0    0.2
 CAF                     GHC.Handle                                           104           4   0.0   48.3     0.0   48.3

remainder関数は4回。正規順序でも4回か。