Exercise 2.43. Louis Reasoner is having a terrible time doing exercise 2.42. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6× 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, writing it as
(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))
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis’s program to solve the eight-queens puzzle, assuming that the program in exercise 2.42 solves the puzzle in time T.
这个效率低下的整个过程如下：
(define (queens 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))
我们可以倒着，从 k = 1 的时候开始分析。
当 k = 1 的时候，flatmap 去执行的过程 (lambda (new-row)..) 会被调用 board-size 次。 其中的每一次将会去调用 (lambda (rest-of-queens)..) 这个过程 (queen-cols (- k 1)) 次。
正确的调用过程，queen-cols 总共仅被调用 8 次而已。但在这个效率不高的过程里，当 board-size 为 8 ， k = 1 的时候，(queen-cols 0) 被调用了 8 次。k = 2 的时候，(queen-cols 1) 被调用了 8 次，(queens-cols 0) 被调用了 64 次。以此类推，k = 8 的时候，
- (queen-cols 7) 被调用了 8 次
- (queen-cols 6) 被调用了 64 次
- (queen-cols 5) 被调用
$8^3$ 次 - 可以知道，(queen-cols n) 会被调用
$8^{8-n}$ 次
如果以前正确的过程需要时间 T，那么现在的过程则需要时间：