Re: [boost] Interest check: memoization

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