Serendip

Web Studio

問題4.39

制限の順序は解には影響しない。
解を見いだす時間は、計算に失敗する場合が多い条件を上にすると速くなる。

問題4.40

(define (multiple-dwelling)
  (let ((backer (amb 1 2 3 4 5)))
       (require (not (= backer 5)))
       (let ((cooper (amb 1 2 3 4 5)))
            (require (not (= cooper 1)))
            (require (distinct? (list backer cooper)))
            (let ((fletcher (amb 1 2 3 4 5)))
                 (require (not (= fletcher 5)))
                 (require (not (= fletcher 1)))
                 (require (not (= (abs (- fletcher cooper)) 1)))
                 (require (distinct? (list backer cooper fletcher)))
                 (let ((miller (amb 1 2 3 4 5)))
                      (require (> miller cooper))
                      (require (distinct? (list backer cooper fletcher miller)))
                      (let ((smith (amb 1 2 3 4 5)))
                           (require (not (= (abs (- smith fletcher)) 1)))
                           (require (distinct? (list backer cooper fletcher miller smith)))
                           (list (list 'backer backer)
                                 (list 'cooper cooper)
                                 (list 'fletcher fletcher)
                                 (list 'miller miller)
                                 (list 'smith smith))))))))

amb 評価器の analyze-amb を評価回数をカウントするように修正を行い、p249 の元の multiple-dwelling 手続きとの効率を比較してみる。

(define *amb-count* 0)

(define (analyze-amb exp)
  (let ((cprocs (map analyze (amb-choices exp))))
       (lambda (env succeed fail)
               (define (try-next choices)
                 (if (null? choices)
                     (fail)
                     ((car choices) env
                                    succeed
                                    (lambda ()
                                            (set! *amb-count* (+ *amb-count* 1)) (try-next (cdr choices))))))
               #?=(try-next cprocs))))

実行結果

結果の後ろにある数値が try-next の実行回数。

p249 の元の multiple-dwelling の場合

;;; Amb-Eval value:
((backer 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))1835

効率化を施した multiple-dwelling の場合

;;; Amb-Eval value:
((backer 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))95

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る