Consider the following code (compiles with gcc 4.7.2):
#include<iostream>
#include<memory>
struct Base
{
~Base() {}
virtual double operator()(double x) const = 0;
};
template<typename F, typename G> struct Compose;
struct A : public Base
{
virtual double operator()(double x) const {return x;} //suppose this is a hard-to.calculate function, lots of temporaries, maybe also time-dependent, etc
template <typename F>
Compose<A,F> operator()(const F& f) const {return Compose<A,F>(*this,f);}
};
struct B : public Base
{
virtual double operator()(double x) const {return x*x;} //suppose this is a hard-to.calculate function, lots of temporaries, maybe also time-dependent, etc
template <typename F>
Compose<B,F> operator()(const F& f) const {return Compose<B,F>(*this,f);}
};
struct C : public Base
{
virtual double operator()(double x) const {return x*x*x;} //suppose this is a hard-to.calculate function, lots of temporaries, maybe also time-dependent, etc.
template <typename F>
Compose<C,F> operator()(const F& f) const {return Compose<C,F>(*this,f);}
};
template<typename F, typename G>
struct Compose : public Base
{
Compose(const F &_f, const G &_g) : f(_f), g(_g) {}
F f;
G g;
virtual double operator()(double x) const {return f(g(x));}
};
int main()
{
double x=2.0;
A a;
B b;
C c;
std::shared_ptr<Base> ptrBase = std::make_shared<A>(A());
std::shared_ptr<A> ptrA = std::make_shared<A>(a);
std::cout<< a(x) <<std::endl;
std::cout<< ptrBase->operator()(x) <<std::endl;
std::cout<< ptrA->operator()(x) <<std::endl;
std::cout<< b(a(x)) <<std::endl;
std::cout<< c(b(a(x))) <<std::endl;
std::cout<< a(c(b(a(x)))) <<std::endl;
std::cout<< ptrA->operator()(c(b(ptrBase->operator()(x)))) <<std::endl;
}
Output:
2
2
2
4
64
64
64
Ok, long prelude for a short question. Several redundant calculations occur here, for instance, the result of A()(x) is calculated six times (some via objects, some via pointers). How can I implement a global output array which stores the evaluated function values?
One approach which came to my mind and should work is to implement a function std::string id() unique to each (composed) class, plus a global std::map<std::string,double> to store the results, and then check whether a (current) result exists.
Do you see other and maybe better approaches here? Thanks in advance.
Sorry guys, although there are some similarities (the word "memoization" which seems to somehow trigger a reflex), I really don't see why this should be duplicate ... but I'm open to discussion.
The case above is in my opinion much more complex than those in the linked threads (e.g., its not simply a fibonacci-function). Moreover, as far I can see the highlighted memoization class will treat objects and pointers differently (at least without further editing). My intention was to arrive at a pattern in which each result is calculated only once, regardles how it is invoked.
Up to now, I was playing around with CRTP'ed static results classes, which leads to the following code (compiles with gcc 4.7.2.):
#include<iostream>
#include<memory>
#include<string>
#include<map>
struct Base
{
virtual ~Base() {}
virtual double operator()(double x) const = 0;
virtual std::string id() const = 0;
};
template<typename F, typename G> struct Compose;
template<typename T>
struct Result
{
virtual ~Result() {}
double get(double x) const
{
return mem.find(x)->second;
}
bool isSet(double x) const {it=mem.find(x); return it!=mem.end();}
//get the previously found result by isSet(x)
double get() const
{
return it->second;
}
protected:
//the set function is const, as it works only on static variables
//don't know whether it is the best idea, but it allows for a const operator() later...
void set(double x, double y) const
{
mem.insert(std::make_pair(x,y));
}
private:
static std::map<double, double> mem;
static std::map<double, double>::const_iterator it;
};
template<typename T> std::map<double, double> Result<T>::mem;
template<typename T> std::map<double, double>::const_iterator Result<T>::it=Result<T>::mem.begin();
struct A : public Base, public Result<A>
{
virtual double operator()(double x) const
{
if(isSet(x))
{
return get();
}
else
{
double y=x;
set(x,y);
std::cout<<"setA ";
return y;
}
}
template <typename F>
Compose<A,F> operator()(const F& f) const {return Compose<A,F>(*this,f);}
virtual std::string id() const {return "A";}
};
struct B : public Base, public Result<B>
{
virtual double operator()(double x) const
{
if(isSet(x))
{
return get();
}
else
{
double y=x*x;
set(x,y);
std::cout<<"setB ";
return y;
}
}
template <typename F>
Compose<B,F> operator()(const F& f) const {return Compose<B,F>(*this,f);}
virtual std::string id() const {return "B";}
};
struct C : public Base, public Result<C>
{
virtual double operator()(double x) const
{
if(isSet(x))
{
return get();
}
else
{
double y=x*x*x;
set(x,y);
std::cout<<"setC ";
return y;
}
}
template <typename F>
Compose<C,F> operator()(const F& f) const {return Compose<C,F>(*this,f);}
virtual std::string id() const {return "C";}
};
template<typename F, typename G>
struct Compose : public Base, public Result<Compose<F,G> >
{
Compose(const F &_f, const G &_g) : f(_f), g(_g) {}
F f;
G g;
virtual double operator()(double x) const
{
if(this->isSet(x))
{
return this->get();
}
else
{
double y=f(g(x));
this->set(x,y);
std::cout<<"set"<<this->id()<<" ";
return y;
}
}
virtual std::string id() const {return f.id() + "(" + g.id() + ")";}
};
int main()
{
double x=2.0;
A a;
B b;
C c;
std::shared_ptr<Base> ptrBase = std::make_shared<A>(A());
std::shared_ptr<A> ptrA = std::make_shared<A>(A());
std::cout<<"-------------------------------"<<std::endl;
std::cout<< a(x) <<std::endl;
std::cout<<ptrBase->operator()(x) <<std::endl;
std::cout<<ptrA->operator()(x) <<std::endl;
std::cout<<"-------------------------------"<<std::endl;
std::cout<<c(x)<<std::endl;
std::cout<<C()(x)<<std::endl;
std::cout<<C()(x)<<std::endl;
std::cout<<"-------------------------------"<<std::endl;
auto ba= b(a);
std::cout<<ba(x) << std::endl;
auto cba= c(ba);
std::cout<<cba(x)<< std::endl;
auto acba= a(cba);
std::cout<<acba(x)<<std::endl;
}
Output:
-------------------------------
setA 2
2
2
-------------------------------
setC 8
8
8
-------------------------------
setB setB(A) 4
setC(B(A)) 64
setA(C(B(A))) 64
-------------------------------
Ok, some things to note here:
By inheritance from the static results class, it is interesting how all the differently called A's (by object, by pointer-to-object, by pointer-to-base) retrieve the stored result (there is only one set). Same for C() which is called three times but set only once.
In order to anticipate the next reflex, I know that multiple inheritance can be bad, but the classes seem to be well separated. The same behavior is probably obtained by composition, so please forget about that point.
In fact, this isn't really a memoization class yet, as it simply stores the result which was calculated first. Thus it also gives wrong results [eg. for C(B(A))]. However, this can be easily cured by a map or whatever. I will do this later eventually, at the moment its only about the pattern (EDIT: is done).
And as a last point, I'm aware that a different solution than in the seemingly-duplicated threads doesn't imply a different questions. Yet, it will maybe (--hopefully) yield some extension of the memoization-topic on this page from which all can benefit.
I'm looking forward to your thoughts. Thanks in advance!
EDIT 2: Helping yourself is a good thing, now the code works as I was looking for. I have updated it in the post above.
Changes:
Added a map to actually make a real memoization class out of it. Caution: double comparison is dangerous, so one should better pass a more approriate comparison function instead of the standard equality.
Made the static members of the results array private, and the setters protected, as only the function-classes may change the results.
Still the map types are not given by template parameters (as in the linked threads). That is overhead which I don't need (and probably YAGNI too).
Now I'll stop talking to myself. Comments are still welcome. Thanks, David
