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

From Drewiki
Jump to: navigation, search

Problem

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 \times 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.

Solution

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 n^0 + n^1 + n^2 + \cdots + n^{m-1}. (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 x \ne y 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 O\left( \phi \right). The cost of evaluating Louis's version is O\left( \phi^{n-1} \right). 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.

Personal tools