Perl's memoize function in C++
DK
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?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
mfur...@gmail.com
#include <map>
using std;
int fib(int n)
{
static map<int, int> mapCache;
if (mapCache.find(n) != mapCache.end())
return mapCache[n];
int iResult = fib(n-1) + fib(n-2);
mapCache[n] = iResult
return iResult;
}
Good Luck!
Matt Furnari
DK
and would require maintainance of a map by hand. In case of multiple
arguments, a map<string, int> would be required which stores a mapping
from the concatenated version of the arguments as the key to the return
values. I want to make this process transparent. i.e. The cache should
be handled by a separate function which can act as an intermediary to
make this process transparent. However, in this case, how can recursion
be handled so that the function calls go through the cache. Will a
macro like MEMOIZE_BEGIN(int, int) and MEMOIZE_END(int,int) placed at
the beginning and end of the function be better or more apt?
Nicola Musatti
> 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
Greg Herlihy
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
Brian McKeever
lookup table for an argument(s) after the function has been called once
with a particular set of arguments.
[...]
> Also, how can recursion be handled without messing up the
code or including additional dependencies in the original code?
In order for a recursive function to properly memoize, you either have
to modify the function to call itself through a memoizing decorator
(like Nicola suggests), or "intrusively" memoize by inserting the cache
code into the body of the function. Following the idea of
"MEMOIZE_BEGIN(int, int)" from your other post, you could implement it
like this:
// define additional structs for different function arities
// use boost::tuple as the key
template<typename Ret, typename Arg1>
struct Memoizer1
{
typedef std::map<Arg1, Ret> CacheMap;
Ret* m_pRet;
Arg1* m_pArg1;
CacheMap* m_pMap;
Memoizer1(CacheMap* pMap, Ret* pRet, Arg1* pArg1) :
m_pRet(pRet),
m_pArg1(pArg1), m_pMap(pMap)
{}
~Memoizer1()
{
(*m_pMap)[*m_pArg1] = *m_pRet;
}
};
#define MEMOIZE1(RetType, RetVar, ArgType, ArgVar) \
static std::map<ArgType, RetType> cacheMap;
\
{
\
std::map<ArgType, RetType>::iterator iter =
cacheMap.find(ArgVar);\
if (iter != cacheMap.end())
\
return iter->second;
\
}
\
Memoizer1<ArgType, RetType> memoizer(&cacheMap, &RetVar, &ArgVar);
use like this:
int fib(int n)
{
int ret;
MEMOIZE1(int, ret, int, n) // return type, return variable, argument 1
type, name of argument 1
if (n < 2)
ret = n;
else
ret = fib(n-1) + fib(n-2); // or return (ret = fib(n-1)
+ fib(n-2));
return ret;
}
The code can handle early function returns, as long as the correct
return value is assigned to the return variable (as in the comment).
It would probably be a good idea to have the function arguments be
const-qualified.
If I were going to use this in production code, I would include some
sort of mechanism to prevent the cache from getting too big, or a way
to clear it out.
It may be possible get rid of the type arguments to the macro or to
avoid creating a different class for each argument count.
Hope it helps.
Brian