Boost logo

Boost :

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


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