7

Here is a generic memoization wrapper I wrote for functions. It makes use of tuplehash. 

template<typename R, typename... Args>
class memofunc{
    typedef R (*func)(Args...);
    func fun_;
    unordered_map<tuple<Args...>, R, tuplehash::hash<tuple<Args...> > > map_;
public:
    memofunc(func fu):fun_(fu){}
    R operator()(Args&&... args){
    auto key = make_tuple(std::forward<Args>(args)...);
    auto q = map_.find(key);
    if(q == map_.end()){
        R res = fun_(std::forward<Args>(args)...);
        map_.insert({key,res});
        return res;
    }else{
        return q->second;
    }
    }
};

example of usage for Fibonacci numbers.

long long fibo(long long x){
    static memofunc<long long, long long> memf(fibo);
    // try to replace fibo with this new fibo but doesn't work, why?
    // function<long long(long long)> fibo = memf; 

    if(x <= 2) return 1;
    // this works but involves changing the original code.
    // how to write code such that I dont need to manually add this code in?
    return memf(x-1) + memf(x-2); 
    // old code
    // return fibo(x-1) + fibo(x-2);
}

Question is, ideally I could just add a few line to the beginning of the recursive function and done with memoization. But simple replacement doesn't work, and this is where I stuck.

Community
  • 1
  • 1
user40129
  • 763
  • 1
  • 5
  • 15

1 Answers1

4

Your problem seems to be that you make a local copy of your memoizer at each function call, then destroy it.

Here is a simple one-argument version of your memoizer that seems to work:

#include <iostream>
#include <functional>
#include <unordered_map>

template<typename Sig, typename F=Sig* >
struct memoize_t;
template<typename R, typename Arg, typename F>
struct memoize_t<R(Arg), F> {
  F f;
  mutable std::unordered_map< Arg, R > results;
  template<typename... Args>
  R operator()( Args&&... args ) const {
    Arg a{ std::forward<Args>(args)... }; // in tuple version, std::tuple<...> a
    auto it = results.find(a);
    if (it != results.end())
      return it->second;
    R retval = f(a); // in tuple version, use a tuple-to-arg invoker
    results.emplace( std::forward<Arg>(a), retval ); // not sure what to do here in tuple version
    return retval;
  }
};

template<typename F>
memoize_t<F> memoize( F* func ) {
  return {func};
}

int foo(int x) {
  static auto mem = memoize(foo);
  auto&& foo = mem;
  std::cout << "processing...\n";
  if (x <= 0) return foo(x+2)-foo(x+1); // bwahaha
  if (x <= 2) return 1;
  return foo(x-1) + foo(x-2);;
}
int main() {
  std::cout << foo(10) << "\n";
}

live example

Note that foo(10) only does 10 invocations of foo.

This also admits:

#define CAT2(A,B,C) A##B##C
#define CAT(A,B,C) CAT2(A,B,C)
#define MEMOIZE(F) \
  static auto CAT( memoize_static_, __LINE__, F ) = memoize(F); \
  auto&& F = CAT( memoize_static_, __LINE__, F )

int foo(int x) {
  MEMOIZE(foo);
  std::cout << "processing...\n";
  if (x <= 0) return 0;
  if (x <= 2) return 1;
  return foo(x-1) + foo(x-2);;
}

for people who like macros for this kind of thing.

A 3 step version might be better.

First, a prelude with a forward declaration of the function and memoizer wrapper.

Second, within the function, an alias for the function name, so recursive calls use the memorization function.

Third, after the declaration of the function, an alias for the function name, so external calls also use the memoized version.

The code above only memoizes recursive calls, never the initial call.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • Couldn't your `operator()` template cause conversions multiple times? E.g. if the one of the parameters is a `std::string` but the argument is a string literal. – dyp Jul 08 '14 at 21:40
  • @dyp yes. For a real version, I'd perfect forward into a local `std::tuple`, then `emplace`. Interestingly this leaves a strange hole -- the `emplace` lookup ends up occurring after `f` is called, which means `f` can modify the arguments and change where the result is cached. The code above could avoid this, but it uses `operator=` instead of direct construction of `R`. Is there a way around that problem? – Yakk - Adam Nevraumont Jul 08 '14 at 23:27
  • Why `auto&& foo = mem;`? – BЈовић Jul 09 '14 at 07:59
  • 1
    @BЈовић Because without that line, `foo` calls inside `foo` would call `foo`, and not `mem`. And we want recursive calls to be memoized. That creates an alias called `foo` that, when code inside `foo` invokes `foo(x-1)`, it goes through the alias. – Yakk - Adam Nevraumont Jul 09 '14 at 13:19
  • You could also do `return mem(x-1) + mem(x-2);`, and remove foo (local variable, not the function). – BЈовић Jul 09 '14 at 13:47
  • @BЈовић but the point of the OP's question is to insert a prologue at the start of the function that lets you memoize the recursive calls in the function **without** changing the body of the function after the prologue. – Yakk - Adam Nevraumont Jul 09 '14 at 13:53
  • Hmm. You could try inserting an element into the map before calling `f`, e.g. via a union/placement new (using the map element as a buffer). Then you have an iterator to that element and `f` can change the arguments. (Requires a try/catch if `f` throws to remove that element again.) – dyp Jul 09 '14 at 14:59
  • @dyp except recursive calls (in the invocation) can invalidate our iterator. – Yakk - Adam Nevraumont Jul 09 '14 at 15:11
  • Why not `results[a] = std::move(retval);`? Btw, nice solution to the default construction vs memoization problem. But why don't you use `emplace`/`insert` now? – dyp Jul 09 '14 at 17:07
  • 1
    `retval` will be returned, for one thing, so `move`ing it seems impolite. ;) We could return `results[a]`, but we already have it in `retval`. – Yakk - Adam Nevraumont Jul 09 '14 at 17:30