FibBuzz で fibonacci をメモ化
前回の続き。
Boost.Flyweight を使用してfibonacci をメモ化しました。
これで実行速度が鬼のように早くなった。
[ソース]
#include <boost/flyweight.hpp> #include <boost/flyweight/key_value.hpp> #include <boost/flyweight/no_tracking.hpp> #include <boost/phoenix/bind.hpp> #include <boost/phoenix/operator.hpp> #include <boost/phoenix/core/argument.hpp> #include <boost/phoenix/object/construct.hpp> #include <boost/range/irange.hpp> #include <boost/range/algorithm/for_each.hpp> #include <boost/range/adaptor/transformed.hpp> #include <boost/lexical_cast.hpp> namespace fw = boost::flyweights; struct compute_fibonacci; typedef fw::flyweight< fw::key_value<unsigned long int, compute_fibonacci>, fw::no_tracking > fibonacci; struct compute_fibonacci{ compute_fibonacci(unsigned long int n) : result( n == 0 ? 0 : n == 1 ? 1 : fibonacci(n-1).get() + fibonacci(n-2).get() ){} operator unsigned long int() const{ return result; } private: unsigned long int result; }; std::string fizz_buzz(unsigned long int n){ return n % 15 == 0 ? "FizzBuzz" : n % 3 == 0 ? "Fizz" : n % 5 == 0 ? "Buzz" : boost::lexical_cast<std::string>(n); } int main(){ namespace phx = boost::phoenix; using phx::arg_names::arg1; using boost::adaptors::transformed; int size = 60; boost::for_each( boost::irange(1, size) |transformed(phx::bind(&fibonacci::get, phx::construct<fibonacci>(arg1))) |transformed(phx::bind(&fizz_buzz, arg1)), std::cout << arg1 << ", " ); return 0; }
[出力]
1, 1, 2, Fizz, Buzz, 8, 13, Fizz, 34, Buzz, 89, Fizz, 233, 377, Buzz, Fizz, 1597, 2584, 4181, FizzBuzz, 10946, 17711, 28657, Fizz, Buzz, 121393, 196418, Fizz, 514229, Buzz, 1346269, Fizz, 3524578, 5702887, Buzz, Fizz, 24157817, 39088169, 63245986, FizzBuzz, 165580141, 267914296, 433494437, Fizz, Buzz, 1836311903, 2971215073, Buzz, Fizz, 3996334433, Buzz, 2886509027, 1776683621, Fizz, 2144908973, Buzz, Fizz, 2876210327, 3239286329,
Boost.Flyweight でこんな事ができるのかー。
Boost には知らないことがまだまだ多い。
