週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

昨日の記事のつづき。とりあえずlistが遅くないことを確認します。まずはListByRange操作の速度を確認。コードは追記に載せました。

time cost of handling a list.
SIZE<250では線形に見えます。ちょっと歪んでいる気もしますが。

ところでSIZE>250でグラフが変です。実はここから先はテンプレートの再帰の深さ制限に引っかかっていて、コンパイルが通っていません。

$ g++ -DSIZE=250 testlist.cc
tlist.h:24: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating ‘struct ListByRange<250, 250>’
tlist.h:24:   instantiated from ‘ListByRangeWrap<false, 249, 250>’
tlist.h:19:   instantiated from ‘ListByRange<249, 250>’
tlist.h:24:   instantiated from ‘ListByRangeWrap<false, 248, 250>’

(snip)

tlist.h:24:   instantiated from ‘ListByRangeWrap<false, 0, 250>’
tlist.h:19:   instantiated from ‘ListByRange<0, 250>’
testlist.cc:13:   instantiated from here

tlist.h:24: error: invalid use of incomplete type ‘struct ListByRange<250, 250>’
tlist.h:18: error: declaration of ‘struct ListByRange<250, 250>’
testlist.cc: In function ‘int main(int, char**)’:
testlist.cc:16: error: ‘Result’ was not declared in this scope
testlist.cc:16: error: template argument 1 is invalid

gccのオプション -ftemplate-depth-"$SIZE"を使えばもっと再帰できます。デフォルトは500段。

さらにfoldrとreverseの速度を確認。こちらも遅くはなさそうです。foldrは中身が簡素すぎてうまく時間が計測できていませんが。

time cost of reversing a list.time cost of foldrighting a list.

リストの実装。

template<typename T>
struct Phantom {
  typedef T type;
};

template<int N>
struct IntType {
  enum {value = N};
};

template<typename CAR_, typename CDR_>
struct TList {
  typedef CAR_ car;
  typedef CDR_ cdr;
};

struct NullType {};

template<int n, int m> struct ListByRange;
template<bool b, int n, int m> struct ListByRangeWrap;

template<int n, int m>
struct ListByRange {
  typedef typename ListByRangeWrap<m == n, n, m>::type type;
};

template<int n, int m>
struct ListByRangeWrap<false, n, m> {
  typedef TList<IntType<n>, typename ::ListByRange<n + 1, m>::type> type;
};

template<int n, int m>
struct ListByRangeWrap<true, n, m> {
  typedef NullType type;
};

template<typename Ls>
struct ReverseList {
  template<typename ToReverse_, typename Reversed>
  struct ReverseListInternal {
    typedef typename ToReverse_::cdr to_reverse;
    typedef TList<typename ToReverse_::car, Reversed> reversed;
    typedef typename ReverseListInternal<to_reverse, reversed>::type type;
  };

  template<typename Reversed>
  struct ReverseListInternal<NullType, Reversed> {
    typedef Reversed type;
  };

  typedef typename ReverseListInternal<Ls, NullType>::type type;
};

template<template<typename, typename> class Fn_, typename F0_, typename Ls_>
struct FoldRight {
  typedef typename FoldRight<Fn_, F0_, typename Ls_::cdr>::type folded;
  typedef typename Fn_<typename Ls_::car, folded>::type type;
};

template<template<typename, typename> class Fn_, typename F0_>
struct FoldRight<Fn_, F0_, NullType> {
  typedef F0_ type;
};

template<template<typename, typename> class Fn_, typename A0_, typename Ls_>
struct FoldLeft {};

template<template<typename, typename> class Fn_, typename A0_,
	 typename Hd_, typename Tl_>
struct FoldLeft<Fn_, A0_, TList<Hd_, Tl_> > {
  typedef typename FoldLeft<Fn_, typename Fn_<A0_, Hd_>::type, Tl_>::type type;
};

template<template<typename, typename> class Fn_, typename A0_>
struct FoldLeft<Fn_, A0_, NullType> {
  typedef A0_ type;
};

そして計測に使用したプログラム。まずはListByRangeの計測。Reverseの計測もほぼ同じで、ただResult全体をreverseしただけでした。

template<int n_>
std::string className(Phantom<IntType<n_> > cl) {
  (void)cl;
  std::ostringstream oss;
  oss << "IntType(" << n_ << ")";
  return oss.str();
}

template<typename H, typename T>
  std::string className(Phantom<TList<H, T> > cl) {
  (void)cl;
  return "TList(" + className(Phantom<H>()) + " . "
    + className(Phantom<T>()) + ")";
}

template<typename CL>
std::string className(Phantom<CL> cl) {
  (void)cl;
  return typeid(CL).name();
}

typedef ListByRange<0, SIZE>::type Result;

int main(int argc, char* argv[]) {
  cout << className(Phantom<Result>()) << endl;
}

次いでfoldrの計測。

template<typename A_, typename B_>
struct AddFn{
  enum {
    value = A_::value + B_::value
  };
  typedef IntType<value> type;
};
const int result = FoldRight<AddFn, IntType<0>, ListByRange<0, SIZE>::type>::type::value;
int main(int argc, char* argv[]) {
  cout << result << endl;
}
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/441-fd3cc99f
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。