テンプレートでたらいまわし
できたような気もするけどこれ本当に動いてるのか?
#include <iostream> template <class T, class U> struct Typelist { typedef T Car; typedef U Cdr; }; class NullType; #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) > /* Length */ template <class TList> struct Length; template <> struct Length<NullType> { enum { value = 0 }; }; template <class T, class U> struct Length< Typelist<T, U> > { enum { value = 1 + Length<U>::value }; }; /* Tarai */ template <class TList> struct Tarai; template <class X, class Y, class Z> struct Tarai< TYPELIST_3(X, Y, Z) > { typedef Tarai< Typelist< Typelist<X, Y>, TYPELIST_3(X, Y, Z) > > T; typedef typename T::Result Result; enum { value = T::value }; }; template <class X, class Y, class Z, class T> struct Tarai< Typelist< Typelist< NullType, T >, TYPELIST_3(X, Y, Z) > > { typedef Y Result; enum { value = Length<Y>::value }; }; template <class X1, class X2, class Y1, class Y2, class Z1, class Z2, class T1, class T2> struct Tarai< Typelist< Typelist< Typelist<T1, T2>, NullType >, Typelist< Typelist<X1, X2>, Typelist< Typelist<Y1, Y2>, Typelist< Typelist<Z1, Z2>, NullType > > > > > { typedef Typelist<X1, X2> X; typedef Typelist<Y1, Y2> Y; typedef Typelist<Z1, Z2> Z; typedef typename Tarai< TYPELIST_3(X2, Y, Z) >::Result XX; typedef typename Tarai< TYPELIST_3(Y2, Z, X) >::Result YY; typedef typename Tarai< TYPELIST_3(Z2, X, Y) >::Result ZZ; typedef Tarai< TYPELIST_3(XX, YY, ZZ) > T; typedef typename T::Result Result; enum { value = T::value }; }; template <class X, class Y, class Z, class T1, class T2, class U1, class U2> struct Tarai< Typelist< Typelist< Typelist<T1, T2>, Typelist<U1, U2> >, TYPELIST_3(X, Y, Z) > > { typedef Tarai< Typelist< Typelist<T2, U2>, TYPELIST_3(X, Y, Z) > > T; typedef typename T::Result Result; enum { value = T::value }; }; typedef NullType T0; typedef Typelist<int, T0> T1; typedef Typelist<int, T1> T2; typedef Typelist<int, T2> T3; typedef Typelist<int, T3> T4; typedef Typelist<int, T4> T5; typedef Typelist<int, T5> T6; typedef Typelist<int, T6> T7; typedef Typelist<int, T7> T8; typedef Typelist<int, T8> T9; typedef Typelist<int, T9> T10; typedef Typelist<int, T10> T11; typedef Typelist<int, T11> T12; int main(int argc, char *argv[]) { int n = Tarai< TYPELIST_3(T12, T6, T1) >::value; std::cout << n << std::endl; return 0; }
- 実行結果
% time g++ tarai.cpp real 0m2.432s user 0m2.348s sys 0m0.064s % time ./a.out 12 real 0m0.002s user 0m0.000s sys 0m0.004s
比較のために普通にCで書いたものは、
#include <stdio.h> int tarai(int x, int y, int z) { if (x <= y) return y; else return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)); } int main(int argc, char *argv[]) { if (argc < 3) { printf("Usage: %s x y z\n", argv[0]); } else { int x = atoi(argv[1]); int y = atoi(argv[2]); int z = atoi(argv[3]); printf("tarai(%d, %d, %d) = %d\n", x, y, z, tarai(x, y, z)); } return 0; }
% time gcc tarai.c real 0m0.054s user 0m0.028s sys 0m0.024s % time ./a.out 12 6 1 tarai(12, 6, 1) = 12 real 0m0.015s user 0m0.012s sys 0m0.000s
となって、実行時間はテンプレート版の方がかろうじて早い(コンパイル時に計算を済ませているんだから当たり前)。本当は数字が大きい方が差が出やすいんだけど、テンプレートの方はあまり数字を大きくできないので益々使えない。
参考:前回までのあらすじ
改めて眺めてみると、およそ生産的でないことばっかりやってるな。