Boost logo

Boost :

Subject: Re: [boost] Interest check: memoization
From: James Porter (porterj_at_[hidden])
Date: 2009-01-31 02:28:42


For those who are still interested, I've uploaded a new version of the
memoizer code: http://www.teamboxel.com/misc/memoizer-0.3.tar.gz

The main changes are, 1) adding recursive and static memoizers, 2)
switching over to Boost.Build. There are also a handful of unit tests,
as well as some examples. The basic memoizer template works the same as
before (though I fixed a bug that made it impossible to use
std::/boost::function objects), so I'll focus on the new memoizer types:

The recursize memoizer is useful for memoizable functions that call
themselves. The basic memoizer doesn't easily allow for this without the
use of global objects, prompting me to create a specialized version. The
example below shows typical usage:

        class factorial : public recursive_memoizer<factorial,int(int)>
        {
                friend class memoizer_core_access;
        public:
                factorial(int k) : k(k)
                {}
        private:
                int call(int n)
                {
                        if(n<=1)
                                return 1;
                        else
                                return n*memo(n-k);
                }

                int k;
        };

        // ...

        // usage
        factorial f(1);
        f(5); // == 120

The recursive memoizer is useful, but it still requires you to hold onto
an object to handle the memoization. That's where the static memoizer
comes in: it has the ability for recursion just like the recursive
memoizer, but has static duration and therefore can be called at any
time from anywhere in your program (standard caveat for calls from other
static functions applies). Example:

        class fibonacci_;
        typedef static_memoizer<fibonacci_> fibonacci;

        class fibonacci_
        {
        public:
                int operator ()(int n)
                {
                        if(n==1)
                                return 1;
                        else if(n<1)
                                return 0;
                        else
                                return fibonacci(n-1)+fibonacci(n-2);
                }
        };

        // ...

        // usage
        fibonacci(10); // == 55

There are still, I'm sure, plenty of bugs and strange edge cases for me
to look at, but I'm pretty happy with how the interface is shaping up so
far. As usual, comments and criticisms are welcome.

- Jim


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk