テンプレートでたらいまわし(7回目)
引数を遅延評価するようにしたらかえって遅くなった。
#include <iostream> /* Int */ template <int x> struct Int { enum { value = x }; }; /* Tarai */ template <int x, int y, int z> struct Tarai; template <class X, class Y, class Z> struct Tarai0; template <bool b, class X, class Y, class Z> struct Tarai1; template <class X, class Y, class Z> struct Tarai2; template <class X, class Y, class Z> struct TaraiDelay2; template <class T> struct TaraiForce; template <int x, int y, int z> struct Tarai { enum { value = Tarai0< Int<x>, Int<y>, Int<z> >::value }; }; template <class X, class Y, class Z> struct Tarai0 { enum { x = TaraiForce<X>::value, y = TaraiForce<Y>::value }; enum { value = Tarai1< (x <= y), Int<x>, Int<y>, Z >::value }; }; template <class X, int y, class Z> struct Tarai1<true, X, Int<y>, Z> { enum { value = y }; }; template <class X, class Y, class Z> struct Tarai1<false, X, Y, Z> { typedef TaraiDelay2<X, Y, Z> XX; typedef TaraiDelay2<Y, Z, X> YY; typedef TaraiDelay2<Z, X, Y> ZZ; enum { value = Tarai0< XX, YY, ZZ>::value }; }; template <class X, class Y, class Z> struct Tarai2 { enum { x = TaraiForce<X>::value }; enum { value = Tarai0< Int<x - 1>, Y, Z >::value }; }; template <int n> struct TaraiForce< Int<n> > { enum { value = n }; }; template <class X, class Y, class Z> struct TaraiForce< TaraiDelay2<X, Y, Z> > { enum { value = Tarai2<X, Y, Z>::value }; }; int main(int argc, char *argv[]) { int n = Tarai<48, 24, 0>::value; std::cout << n << std::endl; return 0; }
% time g++ tarai7.cpp real 0m12.758s user 0m12.001s sys 0m0.136s % time ./a.out 48 real 0m0.003s user 0m0.004s sys 0m0.000s
悔しいので、なんとか速くならないかと足掻いてみると、以下のコードでかろうじて6回目のものを上回った。
#include <iostream> /* Int */ template <int x> struct Int { enum { value = x }; }; /* Tarai */ template <int x, int y, int z> struct Tarai; template <class X, class Y, class Z> struct Tarai0; template <bool b, class X, class Y, class Z> struct Tarai1; template <class X, class Y, class Z> struct Tarai2; template <class X, class Y, class Z> struct TaraiDelay2; template <int x, int y, int z> struct Tarai { enum { value = Tarai0< Int<x>, Int<y>, Int<z> >::value }; }; template <int x, int y, class Z> struct Tarai0< Int<x>, Int<y>, Z > { enum { value = Tarai1< (x <= y), Int<x>, Int<y>, Z >::value }; }; template <class X, int y, class Z> struct Tarai1< true, X, Int<y>, Z > { enum { value = y }; }; template <int x, int y, class Z> struct Tarai1<false, Int<x>, Int<y>, Z> { typedef Int<x> X; typedef Int<y> Y; enum { xx = Tarai0< Int<x - 1>, Y, Z>::value, yy = Tarai0< Int<y - 1>, Z, X>::value }; typedef Int<xx> XX; typedef Int<yy> YY; // この部分を有効にするだけでかなり遅くなる // typedef TaraiDelay2<Z, X, Y> ZZ; typedef void ZZ; enum { value = Tarai0< XX, YY, ZZ>::value }; }; template <int x, class Y, class Z> struct Tarai2< Int<x>, Y, Z> { enum { value = Tarai0< Int<x - 1>, Y, Z >::value }; }; // 実際には使われない template <class Y, class Z, class XX, class YY, class ZZ> struct Tarai2< TaraiDelay2<XX, YY, ZZ>, Y, Z > { enum { x = Tarai2<XX, YY, ZZ>::value }; enum { value = Tarai0< Int<x - 1>, Y, Z >::value }; }; int main(int argc, char *argv[]) { int n = Tarai<48, 24, 0>::value; std::cout << n << std::endl; return 0; }
% time g++ tarai7-2.cpp real 0m3.378s user 0m3.252s sys 0m0.104s % time ./a.out 48 real 0m0.002s user 0m0.000s sys 0m0.004s
ただ、ここまで変えてしまうと問題の本質からは外れてしまっている気がする。しかもそこまでしてもわずかしか速くならないのはどういうことか。どうもテンプレートのインスタンス化は相当重い処理のようで、下手に遅延評価のための構造を増やすよりも、zの無駄な計算をやる方が、memoizeも効いているので結果的には速い、ということのようだ。(この結果はコンパイラによっても変わってきそうだが)