継承とメモ化と再帰関数

以前、任意の再帰関数をメモ化するためにもにょもにょする話があったが、アレはrecursiveがうまくいかなくて気持ち悪いことになった。

で、最近他人様のblogをちらほらと読んでいたのだが、id:mmatsuokaさんのところに継承を使った何とも怪しいプログラムを発見。

http://d.hatena.ne.jp/mmatsuoka/20051227#1135613159

むはー。基底であるFibクラスのメンバ関数fib内における再帰的な呼び出しで、うまいこと子クラスであるFastFibのfibを呼ばせたい。そこに仮想関数を使って、無理矢理子クラスのfibを呼ばせるわけだ。なるほど。遠い昔の記憶に、OCamlインタプリタかSchemeインタプリタでlet recを実装するときにはmutableかなんか（でしたっけ？）使わないとできないよって話があったを使ったのを思い出す。
というわけで、C++で実装しまする。

#include 
#include 
#include 

class Fib {
public:
  virtual int operator()(int n) {
    if (n < 2) return 1;
    else return (*this)(n-1) + (*this)(n-2);
  }
};

template 
class Memo : F {
public:
  int operator()(int n) {
    if (table.find(n) == table.end()) {
      int v = this->F::operator()(n);
      return table[n] = v;
    } else
      return table[n];
  }

private:
  __gnu_cxx::hash_map table;
};

int main()
{
  boost::timer t;
  Fib f;
  std::cout << f(42);
  std::cout << ": " << t.elapsed() << std::endl;

  t.restart();
  Memo m;
  std::cout << m(42);
  std::cout << ": " << t.elapsed() << std::endl;
}

うむ。これは、なかなかに気持ちいい。気をつけることと言えば、operator()をvirtualにすることくらいだ。int -> int以外にしたければ、そこもtemplateにすればよい。
そういえば、C++でhashを使うにはDinkumware使うか、STLport辺りを入れなければならないとか思っていたが、gccにも拡張としてあったんですね。よくよく考えれば、STLportと同じSGI系と聞いたような気がするから、その名残か。__gnu_cxxってnamespace長い・・・。やはり、hashが入ってないのはSTLの最大の汚点だと思うゾ。
このプログラムを書くときに、うっかり"then"って書いてしまったことは内緒。