SICP 読書ノート#60 - 4.3.1 ambと探索 (pp.246-248)
前回のエントリで実装したambオペレータを使って練習問題を解いていきます。
問題 4.35
二つの境界値の間の整数を返す手続き an-integer-between
を実装する。いくつか方法はあると思うが、§2で登場した enumerate-interval
を流用してみた。
(define (enumerate-interval low high) (if (> low high) '() (cons low (enumerate-interval (+ low 1) high)))) (define (an-integer-between low high) (an-element-of (enumerate-interval low high)))
ピタゴラス三角形の辺の組み合わせを求める a-pytagorean-triple-between
を動かしてみる。
(define (a-pythagorean-triple-between low high) (let ((i (an-integer-between low high))) (let ((j (an-integer-between i high))) (let ((k (an-integer-between j high))) (req (= (+ (* i i) (* j j)) (* k k))) (list i j k)))))
テスト。
racket@> (a-pythagorean-triple-between 1 20) '(3 4 5) racket@> (try-again) '(5 12 13) racket@> (try-again) '(6 8 10) racket@> (try-again) '(8 15 17) racket@> (try-again) '(9 12 15) racket@> (try-again) '(12 16 20) racket@> (try-again) '(there are no more values)
問題 4.36
テキストの例では、
(define (a-pythagorean-triple) (let ((i (an-integer-starting-from 1))) (let ((j (an-integer-starting-from 1))) (let ((k (an-integer-starting-from 1))) (req (= (+ (* i i) (* j j)) (* k k))) (list i j k)))))
i,j,kの組み合わせが [1,1,1] => [1,1,2] => [1,1,3] => ... => [1,1,N] => ...
と k
ばかり増えてしまうため、永遠に返ってこない。
これを回避するには、i,j,kの組み合わせを、
=> [1,1,1] => [1,1,2] => [1,2,2] => [2,2,2] => [1,1,3] => [1,2,3] => [2,2,3] => [1,3,3] => [2,3,3] => [3,3,3] => ...
のように進めていけばよいので、以下のような実装となる。
(define (a-pythagorean-triple) (let* ((k (an-integer-starting-from 1)) (j (an-integer-between 1 k)) (i (an-integer-between 1 j))) (req (= (+ (* i i) (* j j)) (* k k))) (list i j k)))
テスト。
racket@> (a-pythagorean-triple) '(3 4 5) racket@> (try-again) '(6 8 10) racket@> (try-again) '(5 12 13) racket@> (try-again) '(9 12 15) racket@> (try-again) '(8 15 17) racket@> (try-again) '(12 16 20) racket@> (try-again) '(15 20 25) ;; => 以降、永遠につづく…
問題 4.37
問題 4.35 と比べると、今回の実装の方がずっと効率がよい。
(define (a-pythagorean-triple-between-ex low high) (let ((i (an-integer-between low high)) (hsq (* high high))) (let ((j (an-integer-between i high))) (let ((ksq (+ (* i i) (* j j)))) (req (>= hsq ksq)) (let ((k (sqrt ksq))) (req (integer? k)) (list i j k))))))
理由は以下の通り。
k
の走査がないj
の取りうる範囲がせまくなっている
どの程度効率がよくなっているかは、バックトラックの実施数をカウントすれば分かる。
(define *backtrack-count* 0) (define (req p) (if (not p) (begin (set! *backtrack-count* (add1 *backtrack-count*)) (amb)) false))
テスト。まずは問題 4.35 の実装。
racket@> (a-pythagorean-triple-between 1 20) '(3 4 5) racket@> (try-again) '(5 12 13) racket@> (try-again) '(6 8 10) racket@> (try-again) '(8 15 17) racket@> (try-again) '(9 12 15) racket@> (try-again) '(12 16 20) racket@> (try-again) '(there are no more values) racket@> *backtrack-count* 1584
次に問題 4.37の実装。
racket@> (a-pythagorean-triple-between-ex 1 20) '(3 4 5) racket@> (try-again) '(5 12 13) racket@> (try-again) '(6 8 10) racket@> (try-again) '(8 15 17) racket@> (try-again) '(9 12 15) racket@> (try-again) '(12 16 20) racket@> (try-again) '(there are no more values) racket@> *backtrack-count* 225
差は歴然である。。
次回は「§4.3.2 非決定性プログラムの例」から。