メタプログラミングでFib関数をメモ化するとどうなるのか
メモ化されたC++テンプレートメタプログラミングなFib関数を考えてみた。
boost.mpl.mapをメモ帳代わりにして、計算していく。
#include <boost/mpl/if.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/map.hpp> #include <boost/mpl/insert.hpp> #include <boost/mpl/at.hpp> #include <boost/mpl/int.hpp> #include <iostream> using namespace boost::mpl; template <typename m, int n> struct fib_; template <typename m, int n, bool cond> struct fib__ { typedef struct fib_<m, n - 2>::type r1; typedef struct fib_<typename r1::first, n - 1>::type r2; typedef int_<r1::second::type::value + r2::second::type::value> r; typedef boost::mpl::pair< typename insert<m, boost::mpl::pair< int_<n>, r > >::type, r > type; }; template <typename m, int n> struct fib__<m, n, true> { typedef boost::mpl::pair< m, typename at< m, int_<n> >::type > type; }; template <typename m, int n> struct fib_ { typedef typename fib__< m, n, has_key< m, int_<n> >::type::value >::type type; }; template <typename m> struct fib_<m, 1> { typedef boost::mpl::pair< typename insert<m, boost::mpl::pair< int_<1>, int_<1> > >::type, int_<1> > type; }; template <typename m> struct fib_<m, 2> { typedef boost::mpl::pair< typename insert<m, boost::mpl::pair< int_<2>, int_<1> > >::type, int_<1> > type; }; template <int n> struct fib { enum { value = fib_< map0<>, n >::type::second::value }; }; int main() { std::cout << fib<50>::value << std::endl; return 0; }
これでいけるかと思ったら、とんでもなく時間が掛かった挙げ句、コンパイラご臨終と相成った。流石に実装が愚直すぎたか……
$ g++ fib.cpp cc1plus: out of memory allocating 1048576 bytes after a total of 15007744 bytes