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.
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? Also, how can recursion be handled without messing up the
code or including additional dependencies in the original code?
One solution would be to use std::tr1::function class template to
instantiate a memoize template function that would be
signature-compatible with the routine being targeted. The
implementation of this memoize routine would instantiate a
std::tr1::tuple with the function's parameter types and initialize it
with the parameter values passed in a given function call. This tuple
would in turn serve as an index into a statically allocated
std::tr1::unordered_map within the memoize routine. This unordered_map
therefore stores previously-returned values with the value of the
corresponding parameter list - as stored in a tuple - serving as its
key. (And no, I am not a paid spokesperson for the std::tr1 library
:-))
I think that it is virtually certain that the memoize routine would
have to be differentiated by the number of parameters the targeted
function accepts. I would note though that each of these routines would
have to be implemented solely on an "as-needed" basis (that is, to
match the parameter count of a function actually being targeted for
memoization). So the full task of implementing this set of routines
would be completed gradually - over time. So the total effort to
implement a working solution would no doubt be less than it may
otherwise appear.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]