Re: [boost] Interest check: memoization

Subject: Re: [boost] Interest check: memoization
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-01-26 07:18:12

----- Original Message ----- 
From: "James Porter" <porterj_at_[hidden]>
To: <boost_at_[hidden]>
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