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

boost::mpl::vectorには{push,pop}_{back,front}があり、それらの定数時間での動作が保証されています。そのため、そのままQueueとして使えます。

とりあえず性能を調べます。以前と同じく、要素をあらかじめBASE個入れたQueueを作り、それに要素をpushしてはtopを取りだすという操作をSIZE回行った結果を載せます。

time cost of handling boost::mpl::vector queue persistently.
横軸がpush-topの回数、縦軸が時間です。以前の、Physicist QueueとSimple Queueの結果や、Bootstrapped Queueの結果と比較してみてください。Simple Queueほど酷くはないものの、他の速いQueueと比べて要素が多いときのpushに時間がかかっていることがわかります。

さらに、BASEを横軸にして、SIZE=50と固定し、それぞれのQueueでpushがどれだけ時間がかかるか比較してみました。

comparing the time cost of handling queue::push among different implementations.
横軸がQueueにあらかじめ入っている要素の数、縦軸がそのQueueにpush&topを50回やったときのコンパイル時間です。値の幅が広すぎるので縦軸は対数にしました。mpl::vectorを利用したQueueは要素が多くなると遅くなることがよくわかります。

実装は非常に簡単でした。boost::mplに慣れてなくてエラーが出まくりましたが。

template<typename V_>
struct MPLVectorQueue {};

template<typename V_>
struct IsEmpty<MPLVectorQueue<V_> > {
  enum {value = boost::mpl::empty<V_>::type::value};
};

template<typename V_, typename A_>
struct Push<MPLVectorQueue<V_>, A_> {
  typedef MPLVectorQueue<typename boost::mpl::push_back<V_, A_>::type> type;
};

template<typename V_>
struct Top<MPLVectorQueue<V_> > {
  typedef typename boost::mpl::front<V_>::type type;
};

template<typename V_>
struct Pop<MPLVectorQueue<V_> > {
  typedef MPLVectorQueue<typename boost::mpl::pop_front<V_>::type> type;
};

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