決定稿

以下コード．

#include <iostream>
#include <map>
#include <boost/timer.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/function.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/if.hpp>

template<class F>
class fixer;

template<class F>
fixer<F> fix(F f)
{
  return fixer<F>(f);
}

template<class F>
class fixer
{
public:
  explicit fixer(F f)
    : f_(f)
  {}

  template<class T>
  T operator()(T x)
  {
    return f_(fix(f_), x);
  }

private:
  F f_;
};

template<class F>
class memoized_fixer;

template<class F>
memoized_fixer<F> memoized_fix(F f)
{
  return memoized_fixer<F>(f);
}

template<class F>
class memoized_fixer
{
public:
  explicit memoized_fixer(F f)
    : f_(f)
    , p_memo_(new std::map<int, int>())
  {}

  memoized_fixer(memoized_fixer const &rhs)
    : f_(rhs.f_)
    , p_memo_(rhs.p_memo_)
  {}

  template<class T>
  T operator()(T x)
  {
    return p_memo_->find(x) != p_memo_->end()
      ? (*p_memo_)[x]
      : (*p_memo_)[x] = f_(*this, x)
      ;
  }

private:
  F f_;
  boost::shared_ptr<std::map<int, int> > p_memo_;
};

int main()
{
  using namespace std;
  using namespace boost;
  using namespace boost::lambda;

  function<int (function<int (int)>, int)> fib_maker
    = ret<int>(
        if_then_else_return(
          _2 <= 2
        , cref(1)
        , bind(_1, _2 - 1) + bind(_1, _2 - 2)
        )
      )
    ;

  timer t;
  int ans = memoized_fix(fib_maker)(30);
  double elapsed_time = t.elapsed();
  cout << "With memoization" << endl;
  cout << "Answer: " << ans << endl;
  cout << "Elapsed time: " << elapsed_time << "[s]" << endl;
  cout << endl;

  t.restart();
  ans = fix(fib_maker)(30);
  elapsed_time = t.elapsed();
  cout << "Without memoization" << endl;
  cout << "Answer: " << ans << endl;
  cout << "Elapsed time: " << elapsed_time << "[s]" << endl;

  return 0;
}