Boost logo

Boost :

Subject: Re: [boost] Interest check: memoization
From: James Porter (porterj_at_[hidden])
Date: 2009-01-26 03:56:17


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. 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);

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. :)

Recursive memoization seems like one of the more common use cases for
memoization in general, so I definitely want it to be as straightforward
as possible to use for this purpose.

- Jim


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