Trading Space for Time

Working through SICP for the first time. Found a used first edition (hardcover, no less) on eBay. Some misguided person had marked each of the covers up with a giant X in black marker.

The first edition differs from the second in a few ways. For example, at the end of the tree-recursive change-counting problem on pages 39-40 of the second edition, the authors say “it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge”. They also note that memoization can be used to reduce the number of redundant computations that occur.

In other words, we can trade space for time.

In the first edition, Exercise 1.9 asks you to design a procedure that evolves an iterative process for solving the change-counting problem. I’m working on a solution to that problem; in the meantime, I implemented a procedure that I call memoizing-apply which does the following:

  1. See if an answer has already been computed and stored in a table *mr* (short for `memoized-results’).
  2. If the answer hasn’t already been computed, compute it. Then stick the answer in the table *mr*.

This process is known as memoization or tabulation, and *mr* serves as a lookup table.

We define a table *mr*, and a procedure memoized? that checks if the procedure has already been called with the current arguments. This assumes that the procedure always returns the same answer when you give it the same arguments.

(define *mr* '())

(define (memoized? args)
  (let ((result (assoc args *mr*)))
    (if result
        (cdr result)
        #f)))

Memoizing-apply does what we described above: it checks if the answer has already been computed (is already in the lookup table), and if so it just returns the answer. If not, it computes the answer and sticks it in the table.

(define (memoizing-apply f xs)
  (or (memoized? xs)
      (let ((result (apply f xs)))
      (begin (push! (cons xs result) *mr*)
             result))))

Note that push! is not a standard Scheme procedure; here’s the definition:

(define-syntax push!
  (syntax-rules ()
    ((push! item seq)
     (set! seq (cons item seq)))))

Let’s try it out. (Note that you can get the definitions for the procedures cc and first-denomination from a freely available copy of the book available at the SICP website.)

Here’s my modified version of cc, the change-counting procedure. I call it m-cc, and it uses the memoizing-apply procedure above to avoid doing redundant work:

(define (m-cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+
               (memoizing-apply m-cc (list amount (- kinds-of-coins 1)))
               (memoizing-apply m-cc (list (- amount (first-denomination kinds-of-coins))
                               kinds-of-coins))))))

The above code is different from the original in that it uses memoizing-apply to make the recursive call to itself. In my testing this is much faster than the equivalent cc version.

The memoization technique works very nicely, but it’s only appropriate in situations where memory is freely available. On most computers, most of the time, it’s probably the best way to go, since the tree-recursive implementation is readable and easy to understand. The exercise that asks you to solve the problem using an iterative process will likely be more complicated, but I’m not sure yet.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s