memoization.hpp

#pragma once
#ifndef PLASMA_MEMOIZATION
#define PLASMA_MEMOIZATION

// Copyright plasma-effect 2015
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#include<vector>
#include<tuple>
#include<functional>
#include<memory>

namespace plasma
{
	template<class Fty>class memoization;
	template<class ReturnType, class... ArgumentTypes>class memoization<ReturnType(ArgumentTypes...)>
	{
		struct memoization_data
		{
			std::vector<std::pair<std::tuple<ArgumentTypes...>, ReturnType>> data_;
		};
		std::function<ReturnType(ArgumentTypes...)> func_;
		std::shared_ptr<memoization_data> data_;
	public:
		ReturnType operator()(ArgumentTypes... args)const
		{
			auto t = std::make_tuple(args...);
			for (auto const& x : data_->data_)
			{
				if (x.first == t)
				{
					return x.second;
				}
			}
			auto ret = func_(args...);
			data_->data_.push_back(std::make_pair(t, ret));
			return ret;
		}
		memoization(std::function<ReturnType(ArgumentTypes...)>func):func_(func),data_(std::make_shared<memoization_data>()){}
		memoization(memoization const&) = default;
		memoization(memoization&&) = default;
		memoization& operator=(memoization const&) = default;
		memoization& operator=(memoization&&) = default;
		~memoization() = default;
	};
}
#endif

memoization_recursion.hpp

#pragma 
#ifndef PLASMA_MEMOIZATION_RECURSION
#define PLASMA_MEMOIZATION_RECURSION

// Copyright plasma-effect 2015
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#include<functional>
#include<vector>
#include<tuple>
#include<utility>
#include<memory>

namespace plasma
{
	namespace recursion
	{
		template<class Fty>class memoization;
		template<class ReturnType, class... ArgumentTypes>class memoization<ReturnType(ArgumentTypes...)>
		{
			std::function<ReturnType(std::function<ReturnType(ArgumentTypes...)>, ArgumentTypes...)> func;
			std::shared_ptr<std::vector<std::pair<std::tuple<ArgumentTypes...>, ReturnType>>> data;
		public:
			memoization(std::function<ReturnType(std::function<ReturnType(ArgumentTypes...)>, ArgumentTypes...)> f) :
				func(f), data(std::make_shared<std::vector<std::pair<std::tuple<ArgumentTypes...>, ReturnType>>>()) {}
			memoization(memoization const&) = default;
			memoization(memoization&&) = default;
			memoization& operator=(memoization const&) = default;
			memoization& operator=(memoization&&) = default;
			~memoization() = default;

			ReturnType operator()(ArgumentTypes... args)const
			{
				auto t = std::make_tuple(args...);
				for (auto x : *data)
				{
					if (x.first == t)
					{
						return x.second;
					}
				}
				auto ret = func([&](ArgumentTypes... as) {return this->operator()(as...);}, args...);
				data->emplace_back(t, ret);
				return ret;
			}
		};
	}
}
#endif

reference.md

##基本的な使い方

#include"memoization.hpp"
#include<iostream>
int test(int x)
{
  /* とても重い処理(ただし参照透過) */
}

int main()
{
  plasma::memoization<int(int)> func(test);
  std::cout<<func(0)<<std::endl;
  std::cout<<func(1)<<std::endl;
}

##再帰したい

#include"memoization.hpp"
#include<iostream>

int fact_i(int);
const plasma::memoization<int(int)> fact(fact_i);
int fact_i(int x)
{
  return (x == 0 ? 1 : fact(x-1) * x);
}

int main()
{
  std::cout<<fact(0)<<std::endl;
  std::cout<<fact(1)<<std::endl;
  std::cout<<fact(5)<<std::endl;
}

##競プロでも使いたい

/* ここらへんにmemoization.hppの中身をコピペする */
/* あとは普通に実装する */

安心と信頼のBoost Software License #注意点 ArgumentTypesの各typeでoperator==が実装されてる必要があります

#とても大切なお知らせ Yコンビネータを利用して再帰関数を定義できるバージョンを作りました。(memoization_recursion.hpp)

#include"memoization_recursion.hpp"
#include<iostream>

int main()
{
	auto fib = plasma::recursion::memoization<double(int)>([](auto f, int x) {
		return x == 0 ? 0 : (x == 1 ? 1 : f(x - 1) + f(x - 2));});
	std::cout << fib(10) << std::endl;
}