sicp-ex-4.39



<< Previous exercise (4.38) | Index | Next exercise (4.40) >>


meteorgan

  
  
 The order of restrictions doesn't affect the result. but actually affect the running time. 
 for example this code is more efficient: 
 (define (mutiple-dwelling) 
   (let ((baker (amb 1 2 3 4 5)) 
         (cooper (amb 1 2 3 4 5)) 
         (fletcher (amb 1 2 3 4 5)) 
         (miller (amb 1 2 3 4 5)) 
         (smith (amb 1 2 3 4 5))) 
     (require (not (= baker 5))) 
     (require (not (= cooper 1))) 
     (require (not (= fletcher 5))) 
     (require (not (= fletcher 1))) 
     (require (> miller cooper)) 
     (require (not (= (abs (- smith fletcher)) 1))) 
     (require (not (= (abs (- fletcher cooper)) 1))) 
     (require (distinct? (list baker cooper fletcher miller smith))) 
     (list (list 'baker baker) 
           (list 'cooper cooper) 
           (list 'fletcher fletcher) 
           (list 'miller miller) 
           (list 'smith smith)))) 
 Because distinct? runs in quadratic time, while other conditions can be assured in constant time. when moved it to the end of restrictions, it runs less times than before. 
 so reduce the total time.  

xdavidliu

Note that this exercise can be solved purely using some elementary combinatorial calculations on pencil and paper, without running the code or even knowing how long it takes to run the distinct? procedure.

The first part, whether the ordering of requirements affects the final result, is clearly "no".

To answer the second part, let's define four "events", corresponding to the four require statements after the initial distinct? requirement:

1. baker = 5
2. cooper = 1
3. fletcher = 5
4. fletcher = 1

Note that the number of distinct outcomes is 5! = 120. Of those 120, the number that fail the first requirement, e.g. match event 1, we denote as N(1) = 4! = 24. The number that fail *either* the first or second requirement, e.g. match *either* event 1 or event 2, we denote as N(1 or 2). Using "the principle of inclusion and exclusion" (c.f. wikipedia), we have

N(1 or 2) = N(1) + N(2) - N(1 and 2) = 2 * 4! - 3! = 42

An easy way to think about this is we are adding up overlapping Venn diagram regions and correcting for double-counting overlaps.

Continuing, we have after some further calculation:

N(1 or 2 or 3) = 3 * 4! - 2 * 3! = 60
N(1 or 2 or 3 or 4) = 4 * 4! - 4 * 3! = 72

From these numbers we see that 24 outcomes fail the first requirement, 18 fail the second, 18 fail the third, and 12 fail the fourth. Hence, the total number of tests done on these failed requirements, during the four requirements examined here, is

1 * 24 + 2 * 18 + 3 * 18 + 4 * 12 = 162.

Now let's see what happens if we reorder the four events, which correspond to the four require statements in the code after the initial distinct? require statement:

1. fletcher = 5
2. fletcher = 1
3. baker = 5
4. cooper = 1

Performing a similar calculation as above (which I will leave as an exercise for the reader), we obtain the total number of tests done during the four requirements is 156.

Hence, assuming that our Scheme interpreter takes the same time to lookup each of the variables in the environment, having the two fletcher requirements *before* the baker and cooper requirements is *guaranteed* to be faster.

Note that we are able to compare these two orderings because everything that happens after the four requirements is the same for both.