2.43

练习 2.43 Louis Reasoner 在做练习2.42遇到了麻烦，他的queens过程看起来能行，但却运行得极慢（Louis居然无法忍耐到它解出6x6棋盘的问题）。当Louis请Eva Lu Actor帮忙时，她指出他在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))

请解释一下，为什么这样交换顺序会使程序运行得非常慢。估计一下，用Louis的程序去解决八皇后问题大约需要多少时间，假定练习2.42中的程序需要时间 T 求解这一难题。

将上述代码放入原来的代码中仔细查看，会发现 queen-cols 是一个递归调用。现在这个 queen-cols 被放入了第二个 map 里，嵌套更深，所以更慢。

也就是说，原来 queen-cols 是在 flatmap 里被调用的，现在被放入了 flatmap 里的 map 中。原来一旦得到 queen-cols 在 k-1 处的结果，只需要执行 board-size 次的 adjoin-position。现在，对于试图尝试的每一个new-row，都会要先执行 queen-cols 在 k-1 处的结果，再执行 adjoin-position。

如果原来的时间花费是 T，对于这个实现，其时间大概在 T * board-size。