@uents blog

Code wins arguments.

SICP 読書ノート#60 - 4.3.1 ambと探索 (pp.246-248)

SICP Scheme

前回のエントリで実装した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 非決定性プログラムの例」から。

※「SICP読書ノート」の目次はこちら