出力を保存する関数

ちょっと漸化式をいっぱい使う式を解く要件があったのですが、
そこで入力と出力をキャッシュするクラスを作りました。

漸化式というとフィボナッチ数が有名ですが、
普通に再帰を使って計算してしまうと結構時間かかります。
しかし、入力に対して出力が同じ値になるので、それをキャッシュするわけです。

ソースはこちら
f(n,2)が普通のフィボナッチ数、f(n,m)はm個足した版です。

```cpp:fib.cpp
#include <boost/function.hpp>
#include <boost/unordered_map.hpp>

template<typename R, typename T1, typename T2>
class CacheFunction{
	typedef boost::function<R (T1, T2)> CalculateFunction;
	CalculateFunction cfunc;
	typedef boost::unordered_map<std::pair<T1, T2>, R> CacheMap;
	CacheMap cmap;

public:
	CacheFunction() :cfunc(){}
	CacheFunction(CalculateFunction cfunc) :cfunc(cfunc){}

	int operator()(T1 a, T2 b){
		auto key = std::pair<T1, T2>(a, b);
		auto it = cmap.find(key);
		if (it != cmap.end()) return it->second;
		auto result = cfunc(a, b);
		cmap[key] = result;
		return result;
	}

	void set(CalculateFunction func){
		cfunc = func;
	}
};

int main(){
	CacheFunction<int, int, int> f_ch;

	auto f = [&](int n, int m)->int{
		if (n <= m) return 1;
		Number x = 0;
		for (int i = 0; i < m; i++){
			x += f_ch(n - 1 - i, m);
		}
		return x;
	};
	f_ch.set(f);

	std::cout << f_ch(30, 5) << std::endl;
	return 0;
}
```

キャッシュするために関数をラップするんですが、
再帰で呼び出す関数もラップした関数にしないといけません。

なので、一度ラップするクラスを作り、ラムダ式でキャプチャして
最後にラップクラスにセットというややこしい方法に…。
なんとかならないですかね～。
こういうことをするにあたって何も考えずに出来る言語ないかなぁ…。

おまけ
引数3つ版も作ってみました。
[たらいまわし関数](http://ja.wikipedia.org/wiki/%E7%AB%B9%E5%86%85%E9%96%A2%E6%95%B0)も一瞬です。

```cpp:tarai.cpp
#include <boost/function.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <boost/unordered_map.hpp>

template<typename R, typename T1, typename T2, typename T3>
class CacheFunction3{
	typedef boost::function<R (T1, T2, T3)> CalculateFunction;
	CalculateFunction cfunc;
	typedef boost::tuple<T1, T2, T3> Key;


	struct ihash
		: std::unary_function < Key, std::size_t >
	{
		std::size_t operator()(Key const& e) const
		{
			std::size_t seed = 0;
			boost::hash_combine(seed, e.get<0>());
			boost::hash_combine(seed, e.get<1>());
			boost::hash_combine(seed, e.get<2>());
			return seed;
		}
	};

	struct iequal_to
		: std::binary_function < Key, Key, bool >
	{
		bool operator()(Key const& x, Key const& y) const
		{
			return (x.get<0>() == y.get<0>() &&
				x.get<1>() == y.get<1>() &&
				x.get<2>() == y.get<2>());
		}
	};

	typedef boost::unordered_map<Key, R, ihash, iequal_to> CacheMap;
	CacheMap cmap;

public:
	CacheFunction3() :cfunc(){}
	CacheFunction3(CalculateFunction cfunc) :cfunc(cfunc){}

	int operator()(T1 a, T2 b, T3 c){
		auto key = Key(a, b, c);
		auto it = cmap.find(key);
		if (it != cmap.end()) return it->second;
		auto result = cfunc(a, b, c);
		cmap[key] = result;
		return result;
	}

	void reset(CalculateFunction func){
		cfunc = func;
	}
};

int main()
{
	CacheFunction3<int, int, int, int> ctarai;
	auto tarai = [&](int x, int y, int z)->int{
		return x <= y ? y : ctarai(ctarai(x - 1, y, z), ctarai(y - 1, z, x), ctarai(z - 1, x, y));

	};
	ctarai.reset(tarai);

	std::cout << ctarai(13, 6, 0) << std::endl;

	boost::function<int(int, int, int)> org_tarai = [&](int x, int y, int z)->int{
		return x <= y ? y : org_tarai(org_tarai(x - 1, y, z), org_tarai(y - 1, z, x), org_tarai(z - 1, x, y));
	};

	std::cout << org_tarai(13, 6, 0) << std::endl;

	return 0;
}
```