読者です 読者をやめる 読者になる 読者になる

とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

フィボナッチ数列書いてみた

C++

何の変哲も無いフィボナッチ数列を4つ書きました。ホントは constexpr 関数がメモ化されるかどうかのテストだったのですが,結論から言うとこのコードではメモ化されてないみたいです。なので手動でメモ化もしてみたよ,という。

#include<unordered_map>
#include<iostream>
#include<boost/range/algorithm/for_each.hpp>
#include<boost/range/irange.hpp>
#include<boost/optional.hpp>
#include<boost/progress.hpp>

using namespace std; using namespace boost;

unsigned fib(unsigned n)
{
 return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}

constexpr unsigned fib_constexpr(unsigned n)
{
 return n < 2 ? 1 : fib_constexpr(n - 1) + fib_constexpr(n - 2);
}

unsigned fib_unordered_map(unsigned n)
{
 static unordered_map<unsigned, unsigned> memo;
 
 auto const it = memo.find(n);
 if(it != memo.cend())
  return it->second;
 unsigned const ret = n < 2 ? 1 : fib_unordered_map(n - 1) + fib_unordered_map(n - 2);;
 memo.insert({n, ret});
 return ret;
}

unsigned fib_vector(unsigned n)
{
 static vector<optional<unsigned>> memo(40);

 if(memo.size() <= n)memo.resize(n + 1);
 if(memo[n])
  return *memo[n];
 unsigned const ret = n < 2 ? 1 : fib_vector(n - 1) + fib_vector(n - 2);;
 memo[n] = make_optional(ret);
 return ret;
}

template<unsigned (&F)(unsigned), unsigned N = 45>
void test()
{
 progress_timer t;
 for_each(irange(0U, N), [](unsigned n){ cout << F(n) << ','; });
 cout << endl;
}

int main()
{
 test<fib>();
 test<fib_constexpr>();
 test<fib_unordered_map>();
 test<fib_vector>();
}

実行結果:

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811
,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914
296,433494437,701408733,1134903170,
18.89 s

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811
,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914
296,433494437,701408733,1134903170,
18.80 s

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811
,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914
296,433494437,701408733,1134903170,
0.05 s

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811
,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914
296,433494437,701408733,1134903170,
0.00 s

constexpr さん…,がんばって…。

追記

コメントいただきました。上の定義では Haskell でもメモ化されないそうです。


あ,GCC の話です。今,constexpr 動くの GCC しかないはずなので。バージョンは 4.6.1 と 4.7.0 20110806 (experimental) です。