## Memoization

October 9, 2009by Lee Spector (lspector)

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.

October 9th, 2009 at 9:00 pm

(define (memoize f)

(let ((memo (make-hash)))

(lambda args

(let ((match (hash-ref memo args #f)))

(if match

(apply values match)

(let ([vlist (call-with-values (lambda () (apply f args)) list)])

(hash-set! memo args vlist)

(apply values vlist)))))))

I couldn’t figure out how to do it except by converting between multiple values and a list of values, which seems kind of unnatural. I also don’t know when, using a hash, two lists of arguments will be ‘equal?’ and when they won’t. Is there a better way?

October 9th, 2009 at 9:49 pm

Adria (asm09): That looks exactly right. Conversion to/from lists is the only way I see to do it too, but I don’t think it’s a big weakness — the user of memoize doesn’t have to think about this and the performance hit is small, since you only have to build a list when storing a new set of values. On equality of keys in the hashtable, since you used make-hash it will do comparisons with equal?, which is probably the most reasonable thing. There are other functions to create hashtables that use eq? or eqv?, but I think that those will always return #f in this context since the keys are lists created by the function calls.

October 10th, 2009 at 12:16 pm

[…] Memoization […]

October 14th, 2009 at 4:22 pm

The two calls to lambda are kind of mystifying to me. What exactly does nesting these lambda function do?

October 14th, 2009 at 4:47 pm

Arielle (as07): The outer lambda makes the memoize function, just like it would as the 2nd line of any other function definition we’ve used. The inner lambda expression is the value that gets returned from calls to memoize. Memoize takes a function as its argument and returns a new function (that does the same thing as the function it was given, but keeps track of answers and reuses them when it already has them). So (memoize fibonacci) returns a function defined by (lambda (args) (let ((match… [all the rest of that stuff in the inner lambda expression above, but with f having the value fibonacci]. (set! fibonacci (memoize fibonacci)) puts this back into fibonacci, so that calls to fibonacci call this new memoized function. Note that it’s not obvious that the “let” that established the memo variable would cause it to persist between calls to the new fibonacci. But it does, and that’s a swell thing about Scheme/Lisp — look up “closures” if you’re interested in this. I hear that some “modern” programming language developers (for Objective C) have just rediscovered this old idea from the Lisp world…

-Lee