caching results of iterative procedure.
Author Message
caching results of iterative procedure.

I am working to a problem similar to the following: to compute
binomials recursively with the formula

binomial(0,0)    = 1,
binomial(p+1, q) = binomial(p,q) + binomial(p,q+1).

the naive definition is

;;; plain binomial
(define (binomial p q)
(if (= p 0)
(if (= q 0) 1 0)
(+ (binomial (1- p) (1- q))
(binomial (1- p) q))))

but, the same values are computed many times.  So I need to store
previously computed values.  I do like this:

;;; I use slib weight-balanced trees
(require 'wt-tree)

;;; lex order
(define (pair< x y)
(cond ((< (car x) (car y)) #t)
((> (car x) (car y)) #f)
((< (cdr x) (cdr y)) #t)
(else #f)))

(define pair-wt-type (make-wt-tree-type pair<))

;; memoize a procedure of two integers
(define (memo f)
(let ((memo-tree (make-wt-tree pair-wt-type)))
(lambda (x y)
(let ((precomputed-result (wt-tree/lookup memo-tree (cons x y) #f)))
(if precomputed-result
precomputed-result
(let ((result (f x y)))
(wt-tree/add! memo-tree (cons x y) result)
result))))))

;;; memo binomial
(define memo-binomial
(memo (lambda (p q)
(if (= p 0)
(if (= q 0) 1 0)
(+ (memo-binomial (1- p) (1- q))
(memo-binomial (1- p) q))))))

This works nice but I need something more flexible.  My dream is to be
able to define `memo-binomial' from `binomial' with something like

(define memo-binomial (dream-memo binomial))

It should work for any procedure taking two integers as arguments as
`binomial' does.  A am a bit confused and with my poor scheme
knowledge I find difficult to understand if something like this is
possible or not.  Any suggestion appreciated.

marco

Sent via Deja.com http://www.*-*-*.com/

Tue, 12 Mar 2002 03:00:00 GMT
caching results of iterative procedure.
...
Quote:
> This works nice but I need something more flexible.  My dream is to be
> able to define `memo-binomial' from `binomial' with something like

>   (define memo-binomial (dream-memo binomial))

...

You aren't the only one with this dream -- it is a nice one.  So far
as I can tell, it can't truly be realized.  However, there are two
approaches that come close.  One is to instead do

(define binomial (memo binomial))

or equivalently

(set! binomial (memo binomial))

This is kind of a bad hack, in that it interacts quite closely with
binomial's internals.  It also doesn't allow you to have both the
non-memoized and memoized versions simultaneously, since you
effectively modify one to produce the other.

The other approach, which I like better, is to change the picture a
bit.  Instead of turning a non-memoized binomial into a memoized one,
you can turn a neutral binomial-core into either a memoized binomial
or a non-memoized binomial:

(define binomial (non-memoized binomial-core))

(define memo-binomial (memoized binomial-core))

The definitions needed to make this work (beyond your memo, or an
equivalent) are below.  Note that I've made my non-memoized and
memoized work for procedures of any arity, not just two-argument
procedures like binomial.

(define binomial-core
(lambda (binomial)
(lambda (p q)
(if (= p 0)
(if (= q 0) 1 0)
(+ (binomial (- p 1) (- q 1))
(binomial (- p 1 ) q))))))

(define non-memoized
(lambda (core)
(define result
(lambda args
(apply (core result) args)))
result))

(define memoized
(lambda (core)
(define result
(memo
(lambda args
(apply (core result) args))))
result))

-Max Hailperin
Associate Professor of Computer Science
800 W. College Ave.
St. Peter, MN 56082
USA
http://www.gustavus.edu/~max/

Tue, 12 Mar 2002 03:00:00 GMT
caching results of iterative procedure.

Quote:

>I am working to a problem similar to the following: to compute
>binomials recursively with the formula

>  binomial(0,0)    = 1,
>  binomial(p+1, q) = binomial(p,q) + binomial(p,q+1).

>the naive definition is

>  ;;; plain binomial
>  (define (binomial p q)
>    (if (= p 0)
>    (if (= q 0) 1 0)
>    (+ (binomial (1- p) (1- q))
>       (binomial (1- p) q))))

>but, the same values are computed many times.  So I need to store
>previously computed values.  I do like this:

Maybe I'm missing something, but why don't you just do it like this?

(define (choose n k)

(define (chooseb n k kcount result)
(if (> kcount k)
result
(chooseb (- n 1) k (+ kcount 1) (/ (* n result) kcount))
)
)

(chooseb n k 1 1)

)

This will calculate the binomial coefficient of n and k by means of a
tail-recursive auxiliary function. By using auxiliary functions you can
introduce new variables which you can use for storing results along the way.

I'm guessing this is what you want, or am I wrong?

--

Man has always sacrificed truth to his vanity, comfort and

-- W. Somerset Maugham

Tue, 12 Mar 2002 03:00:00 GMT
caching results of iterative procedure.
Nice!  It was what I was looking for: now GC works as I
need, among other things.  Thank you.

One more question, please.  Could someone suggest me a good
way to define `memo' that make it works with procedure of
any arity? (as `memoized' and `non-memoized' do).  To use
wt-trees I need a way to put an order to object of unknown
structure.

Thank you.
marco

[...]

Quote:
> The other approach, which I like better, is to change the picture a
> bit.  Instead of turning a non-memoized binomial into a memoized one,
> you can turn a neutral binomial-core into either a memoized binomial
> or a non-memoized binomial:

> (define binomial (non-memoized binomial-core))

> (define memo-binomial (memoized binomial-core))

[...]

Sent via Deja.com http://www.deja.com/

Wed, 13 Mar 2002 03:00:00 GMT
caching results of iterative procedure.

Quote:

> One more question, please.  Could someone suggest me a good
> way to define `memo' that make it works with procedure of
> any arity? (as `memoized' and `non-memoized' do).  To use
> wt-trees I need a way to put an order to object of unknown
> structure.

There is no standard-compliant way to order arbitrary objects in
Scheme, nor to compute hash codes for them.  Thus a truly general memo
in standard Scheme would be doomed to use simple linear search for the
table of prior cases, rendering it of dubious value.  If you limit
yourself to procedures that take some number of numerical arguments
(or perhaps integer, or integer with range limitations), then
prospects are much brighter.  You can get a list of all the arguments
using the unparenthesized-lambda-parameter notation, and then use
standard list-processing techniques.  For example, if what you want is
ordering comparison, you just cdr down the two lists in parallel,
comparing corresponding elements.

By the way, in response to the earlier poster who suggested simply
replacing binomial with an iterative algorithm -- I assume that
Marco's point was not that he really wanted to do binomial
coefficients this way so much as that he was using that as a test case
for the general technology of memoization as a higher-order procedure.
If the point is really to do an efficient binomial coefficient
calculation, though, your solution may not be the best either, since
it relies so intesively on multiplication and division.  Depending on
the machine, language implementation, range of numbers used, etc., you
may find that you are better off with an approach that only uses
addition.  Marco's memoized version does, but it can be improved on
(if efficiency is the name of the game) by being more careful with the
data structure and order in which values are computed.

-Max Hailperin
Associate Professor of Computer Science
800 W. College Ave.
St. Peter, MN 56082
USA
http://www.gustavus.edu/~max/

Wed, 13 Mar 2002 03:00:00 GMT
caching results of iterative procedure.

Quote:
>> One more question, please.  Could someone suggest me a good
>> way to define `memo' that make it works with procedure of
>> any arity? (as `memoized' and `non-memoized' do).  To use
>> wt-trees I need a way to put an order to object of unknown
>> structure.
>There is no standard-compliant way to order arbitrary objects in
>Scheme, nor to compute hash codes for them.  Thus a truly general memo
>in standard Scheme would be doomed to use simple linear search for the
>table of prior cases, rendering it of dubious value.  If you limit
>yourself to procedures that take some number of numerical arguments
>(or perhaps integer, or integer with range limitations), then
>prospects are much brighter.  You can get a list of all the arguments
>using the unparenthesized-lambda-parameter notation, and then use
>standard list-processing techniques.  For example, if what you want is
>ordering comparison, you just cdr down the two lists in parallel,
>comparing corresponding elements.

>By the way, in response to the earlier poster who suggested simply
>replacing binomial with an iterative algorithm -- I assume that
>Marco's point was not that he really wanted to do binomial
>coefficients this way so much as that he was using that as a test case
>for the general technology of memoization as a higher-order procedure.
>If the point is really to do an efficient binomial coefficient
>calculation, though, your solution may not be the best either, since
>it relies so intesively on multiplication and division.  Depending on
>the machine, language implementation, range of numbers used, etc., you
>may find that you are better off with an approach that only uses
>addition.  Marco's memoized version does, but it can be improved on
>(if efficiency is the name of the game) by being more careful with the
>data structure and order in which values are computed.

I guess you're talking about me? Yes, I think I did indeed misunderstand
him.

As for performance, this function was just made to be simple and readable,
since performance wasn't important. This was just an example function I am
never going to use, but I included it as a tip in case it could help him
out.

And ofcourse, if I _were_ interested in performance, I wouldn't be using
DrScheme like I do now. :)

--

Man has always sacrificed truth to his vanity, comfort and