Scheme - データによる抽象の構築(階層データ構造と閉包性(公認インターフェースとしての並び(写像の入れ子(エイトクィーンパズル(写像の入れ子の順序と実行速度の違い))))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.2(階層データ構造と閉包性)、2.2.3(公認インターフェースとしての並び)、写像の入れ子、問題 2.43.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 2.43.

問題のコードの部分について、問題 2.42のプログラムが(queens-cols (- k 1))を評価する回数は1回、(enumerate-interval 1 board-size)を評価する回数は(length (queen-cols (- k 1)))回、問題 4.23のプログラムの手続きが(queen-cols (- k 1))を評価する回数はboard-size回、(enumerate-interval 1 board-size)を評価する回数は1回となり、また、(queen-cols (- k 1)))の評価するのにかかる時間は、(enumerate-interval 1 board-size)を評価するのにかかる時間よりはるかに長いので、(queens-cols (- k 1))の評価についてのみ考慮して 、問題2.43のコードのプログラムは、問題の2.42のコードのプログラムより時間がかかるようになる。

問題 2.42のプログラムがパズルを解く時間をTとする。

(queen-cols k)

を 評価するのにかかる時間は、

(enumerate-interval 1 board-size)

を評価するのにかかる時間よりはるかに長いので、

(queens-cols (- k 1))

の評価についてのみ考慮して、2.42のプログラムの実行時間を推定する。問題2.42では、再帰的に、手続き queen-cols は

1 + board-size

回呼び出される。2.43のプログラムは再帰的に、手続き queen-cols は

1 + board-size ^ board-size 

回呼び出される。よって、問題2.43のプログラムの実行時実行時間は約

T * (bord-size ^ (board-size board-size - 1))

となる。

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

;; これまでに書いた手続き
(load "./procedures.scm")

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions)
           (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens
          (list (cons new-row k))))

(define empty-board nil)

(define (safe? k positions)
  (define k-row (car (car (last-pair positions))))
  (define (iter n positions)
    (cond ((= n k) #t)
          ((= k-row (car (car positions))) #f)
          (else (iter (+ n 1) (cdr positions)))))
  (iter 1 positions))                      

(define (queens-slow board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions)
           (safe? k positions))
         (flatmap
          (lambda (new-row)
            (map (lambda (rest-of-queens)
                   (adjoin-position new-row k rest-of-queens))
                 (queen-cols (- k 1))))
          (enumerate-interval 1 board-size)))))
  (queen-cols board-size))

(for-each (lambda (proc)
            (time (proc 7)))
          (list queens queens-slow))

入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))

$ ./sample.scm
;(time (proc 5))
; real   0.007
; user   0.010
; sys    0.000
;(time (proc 5))
; real   0.132
; user   0.060
; sys    0.010
$