A memorable, recursive factorial function?

Question

I know how to make memoization in Python easy, but I need a faster way to compute them, so I use C ++. However, I have no idea how to memoir. I understand that it stores the values ​​in an array or vector, and then scans its value when it is extracted, but it would be very useful to see how this is done so that I can try its speed.

Answer 1

Well, the easiest way I can do this in C ++ probably uses a function object to store the stored values. I think this is probably a bit like your python decorator, although I have never done any python. The code will 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 a type name and a function pointer, then the function operator is defined by the class that allows it to be called. The function operator accepts an input value if it is indicated on the map, or simply returns it from the map, or calculates it (using the function pointer), adds it to the map, and then returns it.

So, suppose you define some processing function, for example say:

 int unity(int in) { return in; } 

You would use the following code:

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

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

Answer 2

Just for fun, here is a small general memoizer that I wrote some time ago. Naturally, this requires variation patterns:

 template <template <typename...> class Container, typename...> struct Memo; template <typename R, typename... Args, template <typename...> class Container> struct Memo<Container, R, std::tuple<Args...>> { Memo(std::function<R(Args...)> f) : func(f) { } R operator()(Args && ...args) { const auto arg = std::make_tuple(args...); typename CacheContainer::const_iterator it = cache.find(arg); if (it == cache.cend()) { it = cache.insert(typename CacheContainer::value_type(arg, func(std::forward<Args>(args)...))).first; std::cout << "New call, memoizing..." << std::endl; } else { std::cout << "Found it in the cache!" << std::endl; } return it->second; } private: typedef Container<typename std::tuple<Args...>, R> CacheContainer; std::function<R(Args...)> func; CacheContainer cache; }; template <typename R, typename... Args> Memo<std::map, R, std::tuple<Args...>> OMapMemoize(R(&f)(Args...)) { return Memo<std::map, R, std::tuple<Args...>>(f); } template <typename R, typename... Args> Memo<std::unordered_map, R, std::tuple<Args...>> UMapMemoize(R(&f)(Args...)) { return Memo<std::unordered_map, R, std::tuple<Args...>>(f); } 

I’m not quite sure whether I got the legal veracity correctly, as I wrote this a long time ago. Anyway, here is a test case:

 int foo(double, char) { return 5; } int main() { auto f = OMapMemoize(foo); auto g = UMapMemoize(foo); int a, b; a = f(1.0, 'a'); a = f(1.0, 'a'); a = f(1.0, 'a'); a = f(1.0, 'a'); b = g(1.0, 'a'); b = g(1.0, 'a'); b = g(1.0, 'a'); b = g(1.0, 'a'); return a; } 

Answer 3

No one, except recursion, studying in school, did not calculate factorials in this way.

Remembering is a very good idea, especially if you are going to re-call this method. Why throw away a good job?

Another consideration is the best way to calculate factorials: use the natural gamma function log. It will withstand overflow longer because you are returning a double value. A natural journal will grow slower than value. If you calculate combinations, the natural log changes the multiplication and division by addition and subtraction.

But, of course, memoize for any implementation you use. If you are writing it in C ++, I would recommend using std:map with argument x as the key and ln(gamma(x)) as the value.

Sorry, this has been too long since I wrote C ++ and STL. I would rather use a hash map with O(1) read access time to the need to iterate over the keys in O(n) .

Answer 4

I like to rely on lambda capture as in (uses std=c++14 )

 template<typename R, typename... Args> auto memoize(std::function<R(Args...)>&& f) { using F = std::function<R(Args...)>; std::map<std::tuple<Args...>,R> cache; return ([cache = std::map<std::tuple<Args...>,R>{}, f = std::forward<F>(f)](Args&&... args) mutable { std::tuple<Args...> t(args...); if (cache.find(t) == cache.end()) { R r = f(std::forward<Args...>(args)...); cache[t] = r; } return cache[t]; }); }