Note: this wiki is now retired and will no longer be updated!
The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.
SICP 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 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.
The original version of the flatmap expression evaluates the combination (queen-cols (- k 1)) once, and evaluates the enumerate-interval expression once for each element in the sequence generated by evaluating (queen-cols (- k 1)). By flipping the order of the nested mappings, Louis's version of the expression evaluates the enumerate-interval expression once and evaluates (queen-cols (- k 1)) board-size times, once for each number in the sequence generated by the enumerate-interval expression.
enumerate-interval is a simple linear-recursive procedure, so it's relatively cheap to evaluate the expression (enumerate-interval 1 board-size) multiple times. Computing queen-cols is more expensive, if for no other reason than the fact that evaluating queen-cols also evaluates (enumerate-interval 1 board-size).
The original version of the queen-cols procedure generates a linear-recursive process, but Louis's version generates a tree-recursive process, so the original version is going to be appreciably faster than Louis's for large enough values of board-size.
Now let's address the second part of the exercise: if the original version of the procedure takes time T to solve the eight-queens puzzle, how long does it take Louis's version?
The tree-shaped process generated by evaluating Louis's version of queens has degree board-size, i.e., each non-leaf node in the tree has board-size children. Each node also decrements k, the number of columns being considered, until it reaches zero; k's initial value is board-size, so that means this version of queens generates a tree-shaped process of degree board-size and depth board-size.
The number of nodes in a tree of degree n and depth m is the sum . (Prove this to yourself by drawing binary and ternary trees of various depths.) Therefore, evaluating (queens 8 ) with Louis's version of queens evaluates queen-cols 2396745 times. The original version of queens evaluates queen-cols only 8 times.
This doesn't tell the whole story about how much faster the original version is than Louis's version. Because the sequences generated by (queen-cols x) and (queen-cols y) for are generally different lengths, the cost of filtering them is different: in other words, if the original version of of queens takes time T to solve for 8 queens, it doesn't necessarily take time T/2 to solve for four.
We can say that because the original version is linear-recursive, the cost of evaluating it is . The cost of evaluating Louis's version is . So if the time needed by the original version to solve the 8 queens puzzle is T, we can expect the time required for Louis's version to be roughly T7.