Re: [boost] Interest check: memoization

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