SICP 問題 2.43（非効率な queens に関する考察）

問題

Louis Reasoner は問題 2.42 をやるのに恐ろしく時間がかかった。彼の手続き queens は動くように見えたがすごく遅かった。（Louis は 6×6 を解くのさえ、待つわけにいかなかった。）Louis が Eva Lu Ator に助けを求めた時、彼女は彼が flatmap の写像の入れ子の順を入れ違えて、

(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))

と書いていると指摘した。この入れ替えがプログラムの実行を遅くする理由を説明せよ。問題 2.42 のプログラムがパズルを解く時間を T とし、 Louis のプログラムがエイトクイーンパズルを解くのにどのくらいかかるか推定せよ。

解答

queen-cols の呼び出し回数が全然違うんじゃね？
flatmap に対する母集団としてのリストに enumerate-interval を適用してて、
その各要素に対して適用する (lambda (new-row) (...)) 内で queen-cols を何度も何度も呼び出してる。こりゃ遅くもなるだろう。
問題 2.42 の queens をちょっと改造して queen-cols が何回呼ばれるか調べてみよう。

(define (queens board-size)
  (define queen-col-count 0)
  (define (queen-col k)
    (set! queen-col-count (+ 1 queen-col-count))
    (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-col (- k 1))))))
  (print (queen-col board-size))
  (newline)
  (newline)
  (print queen-col-count))

実行してみる。

gosh> (queens 8)

((4 2 7 3 6 8 5 1) ... 略 ... (5 7 2 6 3 1 4 8) )

9

#

gosh> 

9回呼び出されてる。ただし最後の呼び出しは空リストが買えるので実質的には8回か？
これが、問題 2.43 の場合だと、べき乗の速度で増加していくんじゃない？

1回呼ばれると、(1 2 3 4 5 6 7 8) それぞれに対して呼ばれるから 8 回
上の各々で呼ばれると、一回につき更に 8 回づつ呼ばれる。
この繰り返しで考えると、・・・ 8^8回？いや、最後は空リストが戻るから呼ばれないか。
てことは 8^7回？

というわけで、

8^7/8・T = 8^6回

細けぇことはわからんが、大体こんな感じじゃない？