Code Immersion

In class I talked about “memoization” as a strategy for improving the efficiency of recursive functions like the Fibonacci function we were experimenting with. The idea is to store each value as you calculate it, so that later calls with the same arguments can immediately return the previously calculated value instead of re-calculating it. In the half-implemented version we produced in class the previously calculated values were stored in a list with the value for argument 1 being in position 1 of the list, the value for argument 2 being in position 2, etc. But a more general strategy is to store pairs of (argument value) so that calculated answers can be added to the “memo” in arbitrary order,  so that you can memoize functions that take arguments other than positive integers, etc.

Scheme allows us to abstract this idea in a particularly powerful way. Using the definition of memoize provided below — which uses some fancy stuff that we haven’t covered in class — one can first define fibonacci in the totally normal, non-memoized way, and then do this:

(set! fibonacci (memoize fibonacci))

Henceforth fibonacci will be memoized, meaning that it will first check to see if it has previously calculated the answer and return the previously-calculated answer if it has. If it hasn’t then it will calculate it from scratch (but using any previously-calculated answers that it needs in its recursive calls) and store the new value (and return it).

To try this out first use my definition of memoize:

(define memoize
  (lambda (f) ;; returns a memoized version of function f
    (let ((memo '()))
      (lambda args
        (let ((match (assoc args memo)))    ;; look up args
          (if match
              (cadr match)                  ;; return stored value
              (let ((value (apply f args))) ;; or calculate if necessary
                (set! memo                  ;; and store new value
                      (cons (list args value) memo))
                value)))))))

Then define fibonacci in the ordinary, unmemoized way that most directly reflects the way we describe the function in English:

(define fibonacci
  (lambda (n)
    (cond ((< n 2) 0)
          ((= n 2) 1)
          (else (+ (fibonacci (- n 2))
                   (fibonacci (- n 1)))))))

Now if you test this version without memoizing, using “time” to see how long it takes, you get something like:

> (time (fibonacci 30))
cpu time: 500 real time: 518 gc time: 0
514229

But if you add the following after your ordinary definition of fibonacci:

(set! fibonacci (memoize fibonacci))

Then you get:

> (time (fibonacci 30))
cpu time: 0 real time: 1 gc time: 0
514229

And you can easily go up to inputs of many thousand now.

Some improvements that someone might want to make to my memoize function: 1) It already works for functions that take any number of arguments, but make it work for functions that return any number of values (something we haven’t yet covered), 2) Make it use a more efficient memo data structure, like a hashtable.

BTW my idea for this was based on Paul Graham’s similar function in Common Lisp, but the Scheme version is pretty different.

-Lee

Update: I had a bug in the fibonacci definition in my first post of this, (= n 3) instead of (= n 2); I’ve fixed it and rerun the timings.

This entry was posted on October 9, 2009 at 9:29 am and is filed under Uncategorized.