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

さらに別のqueueたるBootstrapped Queueを実装し、この速度も見てみました。ソースは例によって続きに。

time cost of handling physicist's queue persistently.
Physicist's queueよりちょっと遅い。まあ誤差の範囲です。

Bootstrapped queueのソースです。Physicist's queueより書きやすかったような気がします。

template<typename Internal_>
struct BootstrappedQueue {};

// Implementation is either Deep (normal) or Nulltype.
template<int nhead_, typename Hd_, typename HdQ_, int ntail_, typename Tl_>
struct BootstrappedQueueDeep {};

template<>
struct IsEmpty<BootstrappedQueue<NullType> > {
  enum {value = 1};
};

template<int nh_, typename Hd_, typename Tl_, typename Q_,
	 int nt_, typename Rear_>
struct IsEmpty<BootstrappedQueue<BootstrappedQueueDeep<
				   nh_, TList<Hd_, Tl_>, Q_, nt_, Rear_> > > {
  enum {value = 0};
};

template<int nh_, typename Hd_, typename Tl_, typename Q_,
	 int nt_, typename Rear_>
struct Top<BootstrappedQueue<BootstrappedQueueDeep<
			       nh_, TList<Hd_, Tl_>, Q_, nt_, Rear_> > > {
  typedef Hd_ type;
};

template<int n, typename Front_, typename Q_, int m, typename Rear_>
struct BootstrappedQueueCheck2 {
  typedef BootstrappedQueue<BootstrappedQueueDeep<
			      n, Front_, Q_, m, Rear_> > type;
};

template<typename Q_>
struct BootstrappedQueueCheck2<0, NullType, Q_, 0, NullType> {
  typedef BootstrappedQueue<NullType> type;
};

template<int n, typename Q_, int m, typename Rear_>
struct BootstrappedQueueCheck2<n, NullType, Q_, m, Rear_> {
  typedef BootstrappedQueue<
    BootstrappedQueueDeep<n, typename Top<Q_>::type::type,
			  typename Pop<Q_>::type,
			  m, Rear_> > type;
};

template<int n, typename Front_, typename Q_,
	 int m, typename Rear_>
struct BootstrappedQueueCheck1
  : public If_<
  n >= m,
    BootstrappedQueueCheck2<n, Front_, Q_, m, Rear_>,
    BootstrappedQueueCheck2<n + m, Front_,
			    typename Push<Q_, Reverse<Rear_> >::type,
			    0, NullType> >::type {};

template<typename A_>
struct Push<BootstrappedQueue<NullType>, A_> {
  typedef BootstrappedQueue<
    BootstrappedQueueDeep<1, TList<A_, NullType>, BootstrappedQueue<NullType>,
			  0, NullType> > type;
};

template<int nh_, typename Front_, typename Q_,
	 int nt_, typename Rear_,
	 typename A_>
struct Push<BootstrappedQueue<BootstrappedQueueDeep<
				nh_, Front_, Q_, nt_, Rear_> >, A_ >
  : public BootstrappedQueueCheck1<nh_, Front_, Q_, nt_ + 1, TList<A_, Rear_> > {};

template<int n, typename Hd_, typename Front_, typename Q_,
	 int m, typename Rear_>
struct Pop<BootstrappedQueue<
	     BootstrappedQueueDeep<n, TList<Hd_, Front_>, Q_, m, Rear_> > >
  : public BootstrappedQueueCheck1<n - 1, Front_, Q_, m, Rear_> {};

typedef BootstrappedQueue<NullType> EmptyBootstrappedQueue;
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/451-275397e6
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。