Re: [boost] Interest check: memoization

26 Jan 2009


      ----- Original Message ----- 
From: "James Porter" <porterj@alum.rit.edu>
To: <boost@lists.boost.org>
Sent: Monday, January 26, 2009 9:56 AM
Subject: Re: [boost] Interest check: memoization
...
vicente.botet wrote:
...
int fibonacci_impl(int n);
    memoizer<int (int)> fibonacci(fibonacci_impl);
int fibonacci_impl(int n) {
        return (n==0?0:n==1?1:fibonacci(n-2)+fibonacci(n-1))
    }
for(int n=0;n<40;++n){
        std::cout<<"F("<<n<<")="<<fibonacci(n)<<std::endl;
    }
I've been thinking about this implementation and how it's fairly 
inflexible, especially for function objects.
The global object wasn't look very pretty.
...
I've added support for 
function objects, and I've been working on a general solution to the 
recursive memoization problem. How does this look?
class factorial : public recursive_memoizer<factorial, int(int)>
{
    friend memoizer_core_access;
private:
    int call(int n)
    {
        if(n==0)
            return 1;
        else
            return n*memo(n-1);
    } 
};
// Usage
factorial f;
f(5);
Yes, this is very interesting. I'm wondering if Boost.Flyweight should'n provide a similar recursive class, Joaquin?
...
The (in-progress) implementation I have allows for stateful function 
objects to be memoized, though clearly you wouldn't want to change the 
state once you start memoizing values. I'll post updated code when I'm 
satisfied that it actually works in more than the single case I've 
tested it with. :)
Thanks,
Vicente