It's hard to say "C++ is fun" with an open heart, unless you have read the original blog post on automatic memoization in C++0x: http://slackito.com/2011/03/17/automatic-memoization-in-cplusplus0x/

Indeed, the "little" template <typename ReturnType, typename... Args> std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)  makes C++ so much fun! It "memoizes" functions and function objects unintrusively. Recursive functions cannot be effectively memoized that way in C++, unfortunately.

After looking at the problem from different angles, I finally came up with a solution around midnight. It can definitely be polished still, and might contain bits of very bad style (not the original code), but here it is (The memoize function by slackito.com + my C++Koan noodlings):

//original post: http://slackito.com/2011/03/17/automatic-memoization-in-cplusplus0x/
#include <iostream>
#include <functional>
#include <map>


//the original memoize
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{

	std::map<std::tuple<Args...>, ReturnType> cache;
	return ([=](Args... args) mutable  {

		std::tuple<Args...> t(args...);
		if (cache.find(t) == cache.end()) {
			cache[t] = func(args...);
		}

		return cache[t];
	});
}

/// wrapped factorial
struct factorial_class {

	/// the original factorial with a sligh modification :
	/// recursive call factorial -> _factorial
	int factorial(int n) {
		if (n==0) return 1;

		else {
		std::cout<<"factorial("<<n<<"-1)*"<<n<<std::endl;

		return _factorial(n-1)*n;
		}
	}

	/// the trick function :)
	int _factorial(int n) {

		if (memo) return (*memo)(n);
		return factorial(n);
	}

	/// we're not a function, but a function object
	int operator()(int n) {
		return factorial(n);
	}

	/// the trick holder
	std::function<int(int)>* memo;

	factorial_class() { memo=0; }
};

int main()
{
	auto fact=factorial_class(); //virgin wrapper

	auto tmp = memoize( (std::function<int(int)>(fact) ) ); //memoize with the virgin wrapper copy

	fact.memo=&tmp; //spoilt wrapper
	tmp = memoize( (std::function<int(int)>(fact) ) ); //a new memoize with the spoilt wrapper copy

	std::cout<<tmp(3)<<std::endl; // 3 useful multiplications
	std::cout<<tmp(4)<<std::endl; // 1 useful multiplication

	std::cout<<tmp(6)<<std::endl; // 2 useful multiplications
}

http://pastebin.com/x3U2xz7C
compiles with g++ main.cpp -std=c++0x

It makes C++ even more fun! (Even if you hate it at the same time)

D.2011

Вам это будет интересно!

Последние новости