Writing Universal Memoization Function in C++11

Memoization functor wrapper in c++

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.

C++ Memoization understanding

The code indeed save each fib_val into the fibHash map. The find method called on fibHash searches the map to see if the value was previously computed. If so, find returns an iterator on this value and the function returns it (return *fibIter).

fibHash[ n ] = fib_val; adds a new value in the map.

Memoized, recursive factorial function?

Well the neatest way I can think of to do this in C++ is probably using a function object to store the memoized values. I guess this is probably slightly similar to your python decorator, although I have never really done any python. The code would look something like this:

template <typename T, T (*calc)(T)>
class mem {
  std::map<T,T> mem_map;

public:
  T operator()(T input) {
    typename std::map<T,T>::iterator it;

    it = mem_map.find(input);
    if (it != mem_map.end()) {
      return it->second;
    } else {
      T output = calc(input);
      mem_map[input] = output;
      return output;
    }
  }
};

The code defines a template class that takes in a typename and a function pointer, the function operator is then defined on the class allowing it to be called. The function operator takes in an input value checks if said value is in a map, then either simply returns it from the map or calculates it (using the function pointer), adds it to the map and then returns it.

So assuming you define some processing function like say:

int unity(int in) { return in; }

You would use the code like this:

mem<int, unity> mem_unity;
int y;
y = mem_unity(10);

So we define an instance of the mem class which takes our value type and processing function as template parameters, then simply call this class as a function.

Memoization Practice

Some issues:

• The first function is overwritten by the second, so you actually only use the second. Hence, there is no memoization happening
• The assignment says that your function should take an array, but you provide it a set. {2, 3} is a set in Python, while [2, 3] is a list.

If the first function were used:

• It has a commented line that is actually needed.
• It takes an argument that is initialised once (only once!) with ={}. This means that if your main code makes multiple calls (like in your example), memo will not be reset between calls, and therefore the results will be wrong.

So, use a different name for the first function and remove the initial value for memo. Avoid the repetition of code in the second function, and just let it call the first one, making sure it passes an empty memo dictionary:

def howSumRec(target_num, listt, memo):
    if target_num in memo: 
        return memo[target_num]
    if target_num == 0:
        return []
    if target_num < 0: 
        return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSumRec(remainder, listt, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    return howSumRec(target_num, listt, {})

You could still improve on this, if needed, as this does not take advantage of the fact that the order in which you add terms is not important. So you could make sure that a recursive call never looks at terms that are positioned earlier in the list than the last term that was added:

def howSumRec(target_num, listt, i, memo):
    if target_num in memo: 
        return memo[target_num]
    if target_num == 0:
        return []
    if target_num < 0: 
        return None
    for j in range(i, len(listt)):
        num = listt[j]
        remainder = target_num - num
        remainder_result = howSumRec(remainder, listt, j, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    return howSumRec(target_num, listt, 0, {})

It is important that with this version, listt is really a list, and not a set, so call it as:

print(howSum(7, [2, 3]))
print(howSum(7, [5, 3, 4, 7]))
print(howSum(7, [2, 4]))
print(howSum(8, [2, 3, 5]))
print(howSum(300, [7, 14]))

Writing performant C++ setters

My understanding is that what C# compiler does in the background roughly transforms to following C++ code:

class Person {
    std::wstring _name;
public:
    template<typename T>
    inline void setName(T&& name) { _name = std::forward<T>(name); }
};

And for the insertion part:

std::vector<Person> vec;
vec.reserve(999999);
for (auto i = 0; i < vec.size(); i++)
{
    vec.emplace_back();
    vec.back().setName(L"John Chester Doe");
}

Thanks again for your time, if there are any other suggestions how to improve this I'll be happy to hear it.

---

Related Topics