Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Memoisation
44 views
Skip to first unread message
Michael Le Barbier Grünewald
May 31, 2012, 2:23:11 AM5/31/12
to
Dear Group,
I am trying to implement memoisation in C++ for abstract classes such that:
I have an abstract class A with a public `int eval()' method delegating its work to the private purely virtual, customisable, `int reallyEval()' method.
Now, let's say that I have a few concrete classes B1, .., Bn derived from A.
Is this possible to add memoisation to B1...Bn by introducing a class C and letting B inherit from C instead of A?
If not, what is the best way to add memoisation?
A possibility would be to edit A and add a level of indirection in the `eval' chain by adding a private customisable `memoisedEval' method whose default version would just call `reallyEval' and the version in a class `MemoisedA' would implement actual memoisation.
This is as close as I could get of my goal, but this involves edition of A. Is this avoidable?
Thank you for your insights!
Michael
I am trying to implement memoisation in C++ for abstract classes such that:
I have an abstract class A with a public `int eval()' method delegating its work to the private purely virtual, customisable, `int reallyEval()' method.
Now, let's say that I have a few concrete classes B1, .., Bn derived from A.
Is this possible to add memoisation to B1...Bn by introducing a class C and letting B inherit from C instead of A?
If not, what is the best way to add memoisation?
A possibility would be to edit A and add a level of indirection in the `eval' chain by adding a private customisable `memoisedEval' method whose default version would just call `reallyEval' and the version in a class `MemoisedA' would implement actual memoisation.
This is as close as I could get of my goal, but this involves edition of A. Is this avoidable?
Thank you for your insights!
Michael
gwowen
May 31, 2012, 3:50:53 AM5/31/12
to
On May 31, 7:23 am, Michael Le Barbier Grünewald
I've implemented a very simple memoisation like this: [code not
checked...]
template memoised<class Btype> : public Btype
{
private:
int storedval;
bool stored;
virtual int reallyEval(){
if(!stored) {
storedval = Btype::reallyEval();
stored = true;
}
return storedval;
}
}
I've implemented a very simple memoisation like this: [code not
checked...]
template memoised<class Btype> : public Btype
{
private:
int storedval;
bool stored;
virtual int reallyEval(){
if(!stored) {
storedval = Btype::reallyEval();
stored = true;
}
return storedval;
}
}
Michael Le Barbier Grünewald
Jun 1, 2012, 2:36:05 AM6/1/12
to
Hye!
On Thursday, May 31, 2012 9:50:53 AM UTC+2, gwowen wrote:
> On May 31, 7:23 am, Michael Le Barbier Grünewald
> <michip...@googlemail.com> wrote:
> > If not, what is the best way to add memoisation?
>
> I've implemented a very simple memoisation like this: [code not
> checked...]
Thank you for your answer, yet it leadsd me to a few other questions.
1. If we write Btype::reallyEval(), does it mean `the *very* method defined by Btype' or the overriden one? In the first case it means this memoisation scheme can only be used for leaf (final) classes, in the second that it does not work!
2. reallyEval() is typically a private member, so we need to let memoise be a friend of Btype: if memoise can only be used on leaves, this is quite a lot of work.
On Thursday, May 31, 2012 9:50:53 AM UTC+2, gwowen wrote:
> On May 31, 7:23 am, Michael Le Barbier Grünewald
> <michip...@googlemail.com> wrote:
> > If not, what is the best way to add memoisation?
>
> I've implemented a very simple memoisation like this: [code not
> checked...]
1. If we write Btype::reallyEval(), does it mean `the *very* method defined by Btype' or the overriden one? In the first case it means this memoisation scheme can only be used for leaf (final) classes, in the second that it does not work!
2. reallyEval() is typically a private member, so we need to let memoise be a friend of Btype: if memoise can only be used on leaves, this is quite a lot of work.
Qi
Jun 1, 2012, 3:52:43 AM6/1/12
to
On 2012-6-1 14:36, Michael Le Barbier Grünewald wrote:
> Thank you for your answer, yet it leadsd me to a few other
> questions.
>
> 1. If we write Btype::reallyEval(), does it mean `the
> *very* method defined by Btype' or the overriden one?
> In the first case it means this memoisation scheme can
> only be used for leaf (final) classes, in the second
> that it does not work!
Maybe you can dedicate your virtual function to sister
> Thank you for your answer, yet it leadsd me to a few other
> questions.
>
> 1. If we write Btype::reallyEval(), does it mean `the
> *very* method defined by Btype' or the overriden one?
> In the first case it means this memoisation scheme can
> only be used for leaf (final) classes, in the second
> that it does not work!
in a multiple inheritance?
http://www.parashift.com/c++-faq-lite/multiple-inheritance.html#faq-25.10
> 2. reallyEval() is typically a private member, so
> we need to let memoise be a friend of Btype: if memoise
> can only be used on leaves, this is quite a lot of work.
access reallyEval(), and let that function
be Btypes' friend. Then all other classes
use that accessor function.
BTW, please keep your post text line within 79 letters.
Don't use so long line in newsgroups.
--
WQ
Pavel
Jun 1, 2012, 10:13:27 PM6/1/12
to
Michael Le Barbier Grünewald wrote:
> Dear Group,
>
> I am trying to implement memoisation in C++ for abstract classes such that:
>
> I have an abstract class A with a public `int eval()' method delegating its work to the private purely virtual, customisable, `int reallyEval()' method.
>
> Now, let's say that I have a few concrete classes B1, .., Bn derived from A.
>
> Is this possible to add memoisation to B1...Bn by introducing a class C and letting B inherit from C instead of A?
Why not?
>
> I am trying to implement memoisation in C++ for abstract classes such that:
>
> I have an abstract class A with a public `int eval()' method delegating its work to the private purely virtual, customisable, `int reallyEval()' method.
>
> Now, let's say that I have a few concrete classes B1, .., Bn derived from A.
>
> Is this possible to add memoisation to B1...Bn by introducing a class C and letting B inherit from C instead of A?
My understanding is (please correct me if I am wrong) that your B1..Bn classes
have some additional opportunity of memoization in reallyEval() to what's
already done in A::eval() *and* this opportunity is common in at least some of B
(otherwise, you would have done it differently in every Bi::reallyEval() by
delegating to something like Bi::reallyDoEval (non-virtual unless necessary for
other reasons).
So, if you have freedom to change Bi (which I assume you can because you are
considering inheriting them from a different base):
Add class C: public A and implement only one reallyEval() method there that does
that additional memoization and may call some protected pure virtual
doReallyEval() and only implement that doReallyEval, not reallyEval() in B1..Bn.
>
> If not, what is the best way to add memoisation?
>
> A possibility would be to edit A and add a level of indirection in the `eval' chain by adding a private customisable `memoisedEval' method whose default version would just call `reallyEval' and the version in a class `MemoisedA' would implement actual memoisation.
>
> This is as close as I could get of my goal, but this involves edition of A. Is this avoidable?
>
>
> Thank you for your insights!
> Michael
-Pavel
Gareth Owen
Jun 3, 2012, 1:54:18 AM6/3/12
to
Michael Le Barbier Grünewald <mich...@googlemail.com> writes:
> Hye!
>
> On Thursday, May 31, 2012 9:50:53 AM UTC+2, gwowen wrote:
>> On May 31, 7:23 am, Michael Le Barbier Grünewald
>> <michip...@googlemail.com> wrote:
>> > If not, what is the best way to add memoisation?
>>
>> I've implemented a very simple memoisation like this: [code not
>> checked...]
>
> Thank you for your answer, yet it leadsd me to a few other questions.
>
> 1. If we write Btype::reallyEval(), does it mean `the *very* method
> defined by Btype'
Yes, the very method.
> Hye!
>
> On Thursday, May 31, 2012 9:50:53 AM UTC+2, gwowen wrote:
>> On May 31, 7:23 am, Michael Le Barbier Grünewald
>> <michip...@googlemail.com> wrote:
>> > If not, what is the best way to add memoisation?
>>
>> I've implemented a very simple memoisation like this: [code not
>> checked...]
>
> Thank you for your answer, yet it leadsd me to a few other questions.
>
> 1. If we write Btype::reallyEval(), does it mean `the *very* method
> defined by Btype'
> or the overriden one? In the first case it means this memoisation
> scheme can only be used for leaf (final) classes, in the second that
> it does not work!
replacement for a Btype. If your inheritance looks like this
A
|
B1-----memo<B1>
|
B1a----memo<B1a>
you can certainly have a memoised<B1> and a memoised<B1A>. But note that
a memoised<B1a> is not derived from a memoised<B1a>. In practice,
though, the fact a class is memoised<> should be completely transparent
for the code.
So you never derive from memoised<> -- each is a leaf class derived from
every non-abstract Bclass. Just replace a Btype_foo with a
memoised<Btype_foo> when each object is first instantiated.
> 2. reallyEval() is typically a private member, so we need to let
> memoise be a friend of Btype
private. It depends on whether you can change the definition of A.
Michael Le Barbier Grünewald
Jun 4, 2012, 2:17:43 AM6/4/12
to
Hi Pavel, thank you for your comments.
On Saturday, June 2, 2012 4:13:27 AM UTC+2, Pavel wrote:
> So, if you have freedom to change Bi (which I assume you can because you are
> considering inheriting them from a different base):
>
> Add class C: public A and implement only one reallyEval() method there that does
> that additional memoization and may call some protected pure virtual
> doReallyEval() and only implement that doReallyEval, not reallyEval() in B1..Bn.
after reading this and the other contributions, I feel it is not
really possible to add memoisation to a class just by changing the
basis class...
What I like in your proposition, is that B1..Bn really gets
tranparently memoised without code editing, but the classes have
to be a bit reworked.
On Saturday, June 2, 2012 4:13:27 AM UTC+2, Pavel wrote:
> So, if you have freedom to change Bi (which I assume you can because you are
> considering inheriting them from a different base):
>
> Add class C: public A and implement only one reallyEval() method there that does
> that additional memoization and may call some protected pure virtual
> doReallyEval() and only implement that doReallyEval, not reallyEval() in B1..Bn.
really possible to add memoisation to a class just by changing the
basis class...
What I like in your proposition, is that B1..Bn really gets
tranparently memoised without code editing, but the classes have
to be a bit reworked.
Michael Le Barbier Grünewald
Jun 4, 2012, 2:30:32 AM6/4/12
to
Hello Qi,
On Friday, June 1, 2012 9:52:43 AM UTC+2, Qi wrote:
> Maybe you can dedicate your virtual function to sister
> in a multiple inheritance?
> http://www.parashift.com/c++-faq-lite/multiple-inheritance.html#faq-25.10
I do not really understand what you mean here...
I ``discovered'' the `delegate to sister' idiom for a few weeks
and used this in the following manner:
A is an ABS, A': virtual public A implements a concrete A.
P : virtual public A implements algorithms involving A,
and to get a concrete P we just need to let
P': public P, public A'
In this example using `delegate to sister' can be avoided by
letting P access A through a reference and this is probably
the most idiomatic way to go. Just out of curiosity,
in which sort of situations can be `the delegate to sister'
successfully used?
> > 2. reallyEval() is typically a private member, so
> > we need to let memoise be a friend of Btype: if memoise
> > can only be used on leaves, this is quite a lot of work.
>
> You can use a global accessor function to
> access reallyEval(), and let that function
> be Btypes' friend. Then all other classes
> use that accessor function.
Thank you for the tip, I did not know about it!
On Friday, June 1, 2012 9:52:43 AM UTC+2, Qi wrote:
> Maybe you can dedicate your virtual function to sister
> in a multiple inheritance?
> http://www.parashift.com/c++-faq-lite/multiple-inheritance.html#faq-25.10
I ``discovered'' the `delegate to sister' idiom for a few weeks
and used this in the following manner:
A is an ABS, A': virtual public A implements a concrete A.
P : virtual public A implements algorithms involving A,
and to get a concrete P we just need to let
P': public P, public A'
In this example using `delegate to sister' can be avoided by
letting P access A through a reference and this is probably
the most idiomatic way to go. Just out of curiosity,
in which sort of situations can be `the delegate to sister'
successfully used?
> > 2. reallyEval() is typically a private member, so
> > we need to let memoise be a friend of Btype: if memoise
> > can only be used on leaves, this is quite a lot of work.
>
> You can use a global accessor function to
> access reallyEval(), and let that function
> be Btypes' friend. Then all other classes
> use that accessor function.
Michael Le Barbier Grünewald
Jun 4, 2012, 2:33:36 AM6/4/12
to
Hello gwowen, thank you for your careful clarifications!
(I am sorry for the long lines, I am used to access Newsgroups
with a sensible client, but here and there must I use Gg groups.
I will try to keep this in mind, though.)
(I am sorry for the long lines, I am used to access Newsgroups
with a sensible client, but here and there must I use Gg groups.
I will try to keep this in mind, though.)
0 new messages