Re: Perl's memoize function in C++
DK wrote:
Perl's memoize function can be used as a cache creator to create a
lookup table for an argument(s) after the function has been called once
with a particular set of arguments.
Basically, I want to implement something like this:
int fib(int n) {
if( n <= 2 )
return 1;
else
return fib(n-1) + fib(n-2);
}
int main() {
int (*newfib)(int);
newfib = memoize(fib);
int n = 7;
std::cout << newfib(n) << std::endl;
return 0;
}
This helps to create a dynamically cached functional substitute for a
horribly inefficient original function in a single line.
No it doesn't, because your original fib() still calls itself
recursively, defying your attempt at memoization. You need to make fib()
call its memoized version instead. Here's an example:
#include <map>
#include <iostream>
template <typename ReturnT, typename ArgT>
class SimpleMemo {
public:
typedef ReturnT (* FuncType)(ArgT);
SimpleMemo(FuncType f) : func(f) {}
ReturnT operator() (ArgT a) {
MapType::iterator i = m.find(a);
if ( i == m.end() ) {
i = m.insert(i, MapType::value_type(a, func(a)));
}
return i->second;
}
private:
typedef std::map<ArgT, ReturnT> MapType;
MapType m;
FuncType func;
};
template <typename ReturnT, typename ArgT>
SimpleMemo<ReturnT, ArgT> simpleMemoize(ReturnT (* f)(ArgT)) {
return SimpleMemo<ReturnT, ArgT>(f);
}
int fib(int n) {
static SimpleMemo<int, int> memoFib(simpleMemoize(fib));
std::cout << "\tCalling fib(" << n << ")\n";
if( n <= 2 )
return 1;
else
return memoFib(n-1) + memoFib(n-2);
}
int main() {
std::cout << "The value of fib(3) is..." << std::endl << fib(3) << '\n';
std::cout << "The value of fib(4) is..." << std::endl << fib(4) << '\n';
std::cout << "The value of fib(5) is..." << std::endl << fib(5) << '\n';
}
The memoize function will look up a cache to see if a value is already
known for the function. If yes, then that value is returned, else it is
calculated using the function. However, my problem is : How do I
implement a memoize function which is type safe (without using varargs)
and can handle multiple arguments without writing separate functions
for 1 arg, 2 arg, multi arg functions. Can templates or functors be of
any help?
I can't help you much there. I suggest you take a look at how some of
the Boost libraries work/are implemented. I'm specifically thinking of
Function, Bind and Tuple. See www.boost.org .
Also, how can recursion be handled without messing up the
code or including additional dependencies in the original code?
As I've shown you above, the memoizer can be generic, but the memoized
recursive function must be aware of it.
Cheers,
Nicola Musatti
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]