[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[jfriends:00488] 第１６会読書会議事録
こんにちは。
鈴木＠二村研です。
まず、読書会の一番最後で私が申し上げた
Portable Scheme Debugger (PSD) の URL です。
http://www.cs.tut.fi/staff/pk/scheme/psd/article/article.html
議事録です。
第１６回 SICP読書会議事録
向原住区センターにて
横山さん えんどうさん
___________________
阿部さん| |
| |
和田先生| |
|___________________|
やましたさん 鈴木
本日は 3.5.3 "ストリームパラダイムの開発"から
第３章
問題3.63
何故かメモ無しバージョンの方がはやい
;; memo ありバージョン （memo-proc）
==> (define louis-s (louis-sqrt-stream 2))
;Evaluation took 0 mSec (0 in gc) 80 cells work, 21 env, 41 bytes other
louis-s
==> (stream-ref louis-s 50)
;Evaluation took 161 mSec (63 in gc) 29287 cells work, 54466 env, 34441 bytes other
1.414213562373095
;; memo ありバージョン （memo-proc2）
==> (define louis-s (louis-sqrt-stream 2))
;Evaluation took 0 mSec (0 in gc) 80 cells work, 21 env, 41 bytes other
louis-s
==> (stream-ref louis-s 50)
;Evaluation took 154 mSec (49 in gc) 29342 cells work, 54535 env, 34441 bytes other
1.414213562373095
;; scm 上の delay
==> (define louis-s (louis-sqrt-stream 2))
;Evaluation took 0 mSec (0 in gc) 52 cells work, 9 env, 41 bytes other
louis-s
==> (stream-ref louis-s 50)
;Evaluation took 119 mSec (28 in gc) 18263 cells work, 34174 env, 33433 bytes other
1.414213562373095
;; delayをメモ無しバージョンにした場合
==> (define louis-s (louis-sqrt-stream 2))
;Evaluation took 0 mSec (0 in gc) 75 cells work, 14 env, 41 bytes other
louis-s
==> (stream-ref louis-s 50)
;Evaluation took 112 mSec (35 in gc) 16885 cells work, 36199 env, 34433 bytes other
1.414213562373095
問題3.64
==> (my-sqrt 2.0 0.1)
1.4166666666666665
==> (my-sqrt 2.0 0.01)
1.4142156862745096
==> (my-sqrt 2.0 0.001)
1.41421356237469
==> (my-sqrt 2.0 0.0001)
1.41421356237469
==> (sqrt 2.0)
1.4142135623730951
問題3.65
(define ln2-stream
(partial-sums (ln2-summands 1)))
(define ln2-accelerated-stream
(accelerated-sequence euler-transform ln2-stream))
==> (display-n-stream ln2-stream 10)
1.0
0.5
0.8333333333333332
0.5833333333333332
0.7833333333333332
0.6166666666666666
0.7595238095238095
0.6345238095238095
0.7456349206349207
0.6456349206349207
done
==> (display-n-stream ln2-accelerated-stream 10)
1.0
0.7
0.6932773109243698
0.6931488693329254
0.6931471960735491
0.6931471806635637
0.6931471805604039
0.6931471805599445
0.6931471805599427
0.6931471805599454
done
==> (log 2)
0.6931471805599453
問題3.66
(define integers (integers-starting-from 1))
(define int-pairs (pairs integers integers))
==> (display-n-stream int-pairs 10)
(1 1)
(1 2)
(2 2)
(1 3)
(2 3)
(1 4)
(3 3)
(1 5)
(2 4)
(1 6)
この座標の動きから推測して，
==> (stream-ref int-pairs 197)
(1 100)
(1 n) = (stream-ref int-pairs (- (* n 2) 3))
==> (stream-ref int-pairs 0)
(1 1)
==> (stream-ref int-pairs 2)
(2 2)
==> (stream-ref int-pairs 6)
(3 3)
==> (stream-ref int-pairs 14)
(4 4)
==> (stream-ref int-pairs 30)
(5 5)
==> (stream-ref int-pairs 62)
(6 6)
a(0) = 0
a(1) = 2
a(2) = 6
a(3) = 14
a(4) = 30
a(5) = 62
a(n) = 2 * a(n - 1) + 2 と，予測でき，
= 2 * {2 * a(n - 2) + 2 } + 2
= 2^2 * a(n - 2) + 2^2 + 2
= 2^2 * {2 * a(n - 3) + 2 } + 2^2 + 2
= 2^3 * a(n - 3) + 2^3 + 2^2 + 2
= 2^(n - 1) * a(1) + Σ(i = 1 to n - 1) 2^i
= 2^n + 2^n - 2
= 2^(n + 1) - 2
a(100) = 2^101 - 2
よって (11 11) を見つけるには，
==> (stream-ref int-pairs (- (expt 2 11) 2))
(11 11)
よって (100 100) を見つけるには
(stream-ref int-pairs (- (expt 2 100) 2))
すれば良い．
==> (stream-ref int-pairs 1)
(1 2)
==> (stream-ref int-pairs 4)
(2 3)
==> (stream-ref int-pairs 10)
(3 4)
==> (stream-ref int-pairs 22)
(4 5)
a(0) = 1
a(1) = 4
a(2) = 10
a(3) = 22
a(n) = 2 * a(n - 1) + 2 と，予測でき，
= 2^(n - 1) * a(1) + Σ(i = 1 to n - 1) 2^i
= 2^(n - 1) * 4 + 2^n - 2
= 2^(n + 1) + 2^n - 2
= 3 * 2^n - 2
よって (11 12) を見つけるには
==> (stream-ref int-pairs (- (* 3 (expt 2 10)) 2))
(11 12)
==> (stream-ref int-pairs (- (* 3 (expt 2 11)) 2))
(12 13)
よって (99 100) を見つけるには
(stream-ref int-pairs (- (* 3 (expt 2 98)) 2))
すればよい
問題3.67
(define integers (integers-starting-from 1))
(define int-pairs-ex (pairs-ex integers integers))
==> (display-n-stream int-pairs-ex 30)
(1 1)
(1 2)
(2 1)
(1 3)
(2 2)
(1 4)
(3 1)
(1 5)
(2 3)
(1 6)
(4 1)
(1 7)
(3 3)
(1 8)
(5 1)
(1 9)
(2 4)
(1 10)
(6 1)
(1 11)
(3 4)
(1 12)
(7 1)
(1 13)
(2 5)
(1 14)
(8 1)
(1 15)
(4 4)
(1 16)
done
問題3.68
(define integers (integers-starting-from 1))
==> (define a (louis-pairs integers integers))
a
==> (define b (pairs integers integers))
b
==> (display-n-stream a 10)
;;とまらない
==> (display-n-stream b 10)
(1 1)
(1 2)
(2 2)
(1 3)
(2 3)
(1 4)
(3 3)
(1 5)
(2 4)
(1 6)
done
とまらないのは
stream-map pairs stream-map pairs
とよびつづけるから。applicative-orderがいけない。
問題3.69
(define integers (integers-starting-from 1))
(define int-triples (triples integers integers integers))
(define pythagoras (stream-filter
(lambda (x)
(let ((i (car x))
(j (cadr x))
(k (caddr x)))
(= (expt k 2) (+ (expt i 2) (expt j 2)))))
int-triples))
delayはscm上の物を利用
==> (display-n-stream pythagoras 5)
(3 4 5)
(6 8 10)
(5 12 13)
(9 12 15)
(8 15 17)
done
問題3.70
a.
(define a
(weighted-pairs (lambda (x) (+ (car x) (cadr x)))
integers
integers))
==> (display-n-stream a 10)
(1 1)
(1 2)
(1 3)
(2 2)
(1 4)
(2 3)
(1 5)
(2 4)
(3 3)
(1 6)
done
b.
(define (not235times x)
(not (or (= 0 (remainder x 2))
(= 0 (remainder x 3))
(= 0 (remainder x 5)))))
(define (W_b x)
(let ((i (car x)) (j (cadr x)))
(+ (* 2 i) (* 3 j) (* 5 i j))))
(define S (stream-filter not235times integers))
(define b
(weighted-pairs W_b S S))
==> (display-n-stream b 20)
(1 1) ==> 10
(1 7) ==> 58
(1 11) ==> 90
(1 13) ==> 106
(1 17) ==> 138
(1 19) ==> 154
(1 23) ==> 186
(1 29) ==> 234
(1 31) ==> 250
(7 7) ==> 280
(1 37) ==> 298
(1 41) ==> 330
(1 43) ==> 346
(1 47) ==> 378
(1 49) ==> 394
(1 53) ==> 426
(7 11) ==> 432
(1 59) ==> 474
(1 61) ==> 490
(7 13) ==> 508
done
問題3.71
(define integers (integers-starting-from 1))
(define (W71 x)
(let ((i (car x)) (j (cadr x)))
(+ (expt i 3) (expt j 3))))
(define s (weighted-pairs W71 integers integers))
(define ramanujans (eq-next-to W71 s))
==> (display-n-stream ramanujans 20)
(1 12) ==> 1729
(9 10) ==> 1729
(2 16) ==> 4104
(9 15) ==> 4104
(2 24) ==> 13832
(18 20) ==> 13832
(10 27) ==> 20683
(19 24) ==> 20683
(4 32) ==> 32832
(18 30) ==> 32832
(2 34) ==> 39312
(15 33) ==> 39312
(9 34) ==> 40033
(16 33) ==> 40033
(3 36) ==> 46683
(27 30) ==> 46683
(17 39) ==> 64232
(26 36) ==> 64232
(12 40) ==> 65728
(31 33) ==> 65728
done
問題3.72
(define (W72 x)
(let ((i (car x)) (j (cadr x)))
(+ (* i i) (* j j))))
(define s (weighted-pairs W72 integers integers))
(define result (eq-3pairs W72 s))
==> (display-n-stream result 12)
(1 18) ==> 325
(6 17) ==> 325
(10 15) ==> 325
(5 20) ==> 425
(8 19) ==> 425
(13 16) ==> 425
(5 25) ==> 650
(11 23) ==> 650
(17 19) ==> 650
(7 26) ==> 725
(10 25) ==> 725
(14 23) ==> 725
問題3.73
(define 0s (fold-right cons-stream the-empty-stream '(0 0 0 0 0 0 0 0 0)))
(define i (cons-stream 1 i))
(define v 7)
(define RC1 (RC 5 1 0.5))
(define result (RC1 v (stream-append 0s i)))
==> (display-n-stream result 20)
7
7.0
7.0
7.0
7.0
7.0
7.0
7.0
7.0
7.0
7.5
8.0
8.5
9.0
9.5
10.0
10.5
11.000000000000001
11.499999999999999
12.0
done
問題3.74
(define sense-data
(fold-right cons-stream
the-empty-stream
'(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))
(define zero-crossings (make-zero-crossings sense-data 0))
(define eva-zero-crossings
(stream-map sign-change-detector
sense-data
(cons-stream 0 sense-data)))
==> (display-n-stream eva-zero-crossings 20)
0
0
0
0
0
-1
0
0
0
0
1
0
0
done
==> (display-n-stream zero-crossings 13)
0
0
0
0
0
-1
0
0
0
0
1
0
0
ERROR: car: Wrong type in arg1 #f
問題3.75
(define sense-data
(fold-right cons-stream
nil
'(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))
(define (make-zero-crossings input-stream last-value av-last-value)
(let ((avpt (/ (+ (stream-car input-stream) last-value) 2))
(cons-stream (sign-change-detector av-last-value avpt )
(make-zero-crossings (stream-cdr input-stream)
(stream-car input-stream)
avpt))))
問題3.76
(define sense-data
(fold-right cons-stream
nil
'(1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4)))
(define (make-zero-crossings2 input-stream last-value preprocessor)
(define (make-zero-crossings input-stream last-value)
(cons-stream
(sign-change-detector (stream-car input-stream) last-value)
(make-zero-crossings (stream-cdr input-stream)
(stream-car input-stream))))
(make-zero-crossings (preprocessor input-stream) last-value))
preprocessor にも last-valueがつくのでこれじゃ甘い
問題3.77
(define (solve f y0 dt)
(letrec ((y (lambda () (exercise-integral (delay dy) y0 dt)))
(dy (stream-map f (y))))
(y)))
これでもできないので宿題
問題3.78
問題3.79
問題3.80
78,79,80 はとばして
p208 正規順序の評価 からよむ
問題3.81
リセットから始めなければならない
(define reset-stream
(cons-stream 0
(cons-stream
nil
(cons-stream
nil
(cons-stream
nil
(cons-stream
nil
reset-stream))))))
(define s (rand reset-stream))
==> (display-n-stream s 20)
0
26
93
124
72
0
26
93
124
72
0
26
93
124
72
0
26
93
124
72
問題3.82
値が近付いていかないのは random-in-rangeで
返ってくる数値が整数だけなので、整数の座標しか
返ってこないのでいつまでたっても値が近付いていかないのです。
修正したバージョンでやってみました
(require 'random)
(define (rand-update x)
(random 1.0))
(define (random-in-range low high)
(define reset-stream (cons-stream nil reset-stream)) ;; don't reset
(stream-map (lambda (x) (let ((range (- high low)))
(+ low (* x range))))
(rand reset-stream)))
(define result (estimate-integral check 2 8 4 10))
==> (* (* 4 (atan 1)) 3 3)
28.274333882308138
(stream-ref result 100)
26.73267326732673
==> (stream-ref result 1000)
28.95104895104895
==> (stream-ref result 10000)
28.325567443255676
==> (stream-ref result 20000)
28.21718914054297
==> (stream-ref result 30000)
28.299856671444283
たしかに近付いて行くのがわかる。
------------------------------------------------------------------------
★ 一票いっとく？ ★
http://isweb.infoseek.co.jp/hp_daiou/?svx=971122