テンプレートでたらいまわし(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も効いているので結果的には速い、ということのようだ。(この結果はコンパイラによっても変わってきそうだが)
テンプレートでたらいまわし(8回目)
継続渡し風味。
#include <iostream> /* True */ class True; /* False */ class False; /* Bool */ template <bool b> struct Bool; template <> struct Bool<true> { typedef True Result; }; template <> struct Bool<false> { typedef False Result; }; /* NullType */ class NullType; /* Typelist */ template <class T, class U> struct Typelist; #define TYPELIST_1(T1) \ Typelist<T1, NullType> #define TYPELIST_2(T1, T2) \ Typelist<T1, TYPELIST_1(T2) > #define TYPELIST_3(T1, T2, T3) \ Typelist<T1, TYPELIST_2(T2, T3) > #define TYPELIST_4(T1, T2, T3, T4) \ Typelist<T1, TYPELIST_3(T2, T3, T4) > #define TYPELIST_5(T1, T2, T3, T4, T5) \ Typelist<T1, TYPELIST_4(T2, T3, T4, T5) > #define TYPELIST_6(T1, T2, T3, T4, T5, T6) \ Typelist<T1, TYPELIST_5(T2, T3, T4, T5, T6) > #define TYPELIST_7(T1, T2, T3, T4, T5, T6, T7) \ Typelist<T1, TYPELIST_6(T2, T3, T4, T5, T6, T7) > #define TYPELIST_8(T1, T2, T3, T4, T5, T6, T7, T8) \ Typelist<T1, TYPELIST_7(T2, T3, T4, T5, T6, T7, T8) > #define TYPELIST_9(T1, T2, T3, T4, T5, T6, T7, T8, T9) \ Typelist<T1, TYPELIST_8(T2, T3, T4, T5, T6, T7, T8, T9) > #define TYPELIST_10(T1, T2, T3, T4, T5, T6, T7, T8, T9, T10) \ Typelist<T1, TYPELIST_9(T2, T3, T4, T5, T6, T7, T8, T9, T10) > /* Append */ template <class T, class U> struct Append; template <class U> struct Append<NullType, U> { typedef U Result; }; template <class T1, class T2, class U> struct Append<Typelist<T1, T2>, U> { typedef Typelist<T1, typename Append<T2, U>::Result> Result; }; /* Int */ template <int x> struct Int { enum { value = x }; }; /* Delay */ template <class TList> struct Delay; /* Force */ class Force; /* Tarai */ template <int x, int y, int z> struct Tarai; template <class TList> struct TaraiBody; template <class X, class Y, class Z, class R> struct Tarai0; template <class Y, class Z, class X, class R> struct Tarai1; template <class Z, class X, class Y, class R> struct Tarai2; template <class B, class Z, class X, class Y, class R> struct Tarai3; template <class X, class Y, class Z, class R> struct Tarai4; template <class Y, class Z, class X, class R> struct Tarai5; template <class Y, class Z, class X, class R> struct Tarai6; template <int x, int y, int z> struct Tarai { typedef TYPELIST_4(Int<0>, Int<x>, Int<y>, Int<z>) TList; enum { value = TaraiBody<TList>::value }; }; template <class X, class Y, class Z, class R> struct Tarai0 { typedef TYPELIST_3(Int<1>, Y, Z) K; typedef TYPELIST_2(Force, X) T; typedef typename Append<T, Typelist<K, R> >::Result TList; enum { value = TaraiBody<TList>::value }; }; template <class Y, class Z, class X, class R> struct Tarai1 { typedef TYPELIST_3(Int<2>, Z, X) K; typedef TYPELIST_2(Force, Y) T; typedef typename Append<T, Typelist<K, R> >::Result TList; enum { value = TaraiBody<TList>::value }; }; template <int x, int y, class Z, class R> struct Tarai2< Z, Int<x>, Int<y>, R > { typedef typename Bool< (x <= y) >::Result B; typedef TYPELIST_5(Int<3>, B, Z, Int<x>, Int<y>) T; typedef typename Append<T, R>::Result TList; enum { value = TaraiBody<TList>::value }; }; template <class X, class Y, class Z, class R> struct Tarai3< True, Z, X, Y, R > { typedef TYPELIST_2(Force, Y) T; typedef typename Append<T, R>::Result TList; enum { value = TaraiBody<TList>::value }; }; template <class X, class Y, class Z, class R> struct Tarai3< False, Z, X, Y, R > { typedef Delay<TYPELIST_4(Int<4>, X, Y, Z)> XX; typedef Delay<TYPELIST_4(Int<4>, Y, Z, X)> YY; typedef Delay<TYPELIST_4(Int<4>, Z, X, Y)> ZZ; typedef TYPELIST_4(Int<0>, XX, YY, ZZ) T; typedef typename Append<T, R>::Result TList; enum { value = TaraiBody<TList>::value }; }; template <class X, class Y, class Z, class R> struct Tarai4 { typedef TYPELIST_3(Int<5>, Y, Z) K; typedef TYPELIST_2(Force, X) T; typedef typename Append<T, Typelist<K, R> >::Result TList; enum { value = TaraiBody<TList>::value }; }; template <int x, class Y, class Z, class R> struct Tarai5< Y, Z, Int<x>, R > { typedef TYPELIST_4(Int<0>, Int<x - 1>, Y, Z) T; typedef typename Append<T, R>::Result TList; enum { value = TaraiBody<TList>::value }; }; template <class X, class Y, class Z, class R> struct TaraiBody< Typelist<Int<0>, Typelist<X, Typelist<Y, Typelist<Z, R> > > > > { enum { value = Tarai0<X, Y, Z, R>::value }; }; template <class X, class Y, class Z, class R> struct TaraiBody< Typelist<Int<1>, Typelist<Y, Typelist<Z, Typelist<X, R> > > > > { enum { value = Tarai1<Y, Z, X, R>::value }; }; template <class X, class Y, class Z, class R> struct TaraiBody< Typelist<Int<2>, Typelist<Z, Typelist<X, Typelist<Y, R> > > > > { enum { value = Tarai2<Z, X, Y, R>::value }; }; template <class X, class Y, class Z, class R, class B> struct TaraiBody< Typelist<Int<3>, Typelist<B, Typelist<Z, Typelist<X, Typelist<Y, R> > > > > > { enum { value = Tarai3<B, Z, X, Y, R>::value }; }; template <class X, class Y, class Z, class R> struct TaraiBody< Typelist<Int<4>, Typelist<X, Typelist<Y, Typelist<Z, R> > > > > { enum { value = Tarai4<X, Y, Z, R>::value }; }; template <class X, class Y, class Z, class R> struct TaraiBody< Typelist<Int<5>, Typelist<Y, Typelist<Z, Typelist<X, R> > > > > { enum { value = Tarai5<Y, Z, X, R>::value }; }; template <int n> struct TaraiBody< Typelist<Force, Typelist<Int<n>, NullType> > > { enum { value = n }; }; template <int n, class R1, class R2> struct TaraiBody< Typelist<Force, Typelist<Int<n>, Typelist<R1, R2> > > > { typedef typename Append< R1, Typelist<Int<n>, R2> >::Result TList; enum { value = TaraiBody<TList>::value }; }; template <class T, class R> struct TaraiBody< Typelist<Force, Typelist<Delay<T>, R> > > { typedef typename Append<T, R>::Result TList; enum { value = TaraiBody<TList>::value }; }; int main(int argc, char *argv[]) { int n = Tarai<12, 6, 0>::value; std::cout << n << std::endl; return 0; }