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

前回列挙したような細かい時間計測はほぼ無理としてあきらめることにしました。

型レベルプログラミングでは計算時間を測るには全く向いていません。そもそもコンパイル時間を計算時間として測るので非常に誤差が大きいです。また、致命的なことに型レベル計算では理論上よりも長い時間がかかることがよくあります。詳しくはC++ Template MetaprogrammingのAppendixを参照。

time cost of PhysicistQueue::push in a rough expt.
これは空のPhysicistQueueに要素をSIZE個pushしたときの時間を計測したものです。10回計測を行い、その平均をとりました。見てのとおり、これだけでは意味のある結果が全くとれません。

次のように、一回のコンパイルの間に何度も同じ計算を行うと意味のある結果が出ます。

time cost of PhysicistQueue::push in a good expt.
このグラフは、空のグラフに要素をSIZE個pushしたときの時間を計測したものです。一回のコンパイル中にこの操作を100回繰り返し、それを10回時間測定しその平均を載せています。そのためSIZE=62,63間でギャップが生じているのは、この間に遅延したサンクを処理しているためです。このギャップについて解説するのが目的なのですが、上に書いたとおり時間計測が不安なので無理です。そもそも直線のはずのグラフが曲がりまくっています。

あと出来るのは既存ライブラリとの比較くらいです。しかしboost mplにqueueはあるのでしょうか。dequeはvectorと同じと書いてあるので使えなそうです。

スポンサーサイト
コメント
この記事へのコメント
mplのvectorは"supports constant-time insertion and removal of elements at both ends"
http://www.boost.org/doc/libs/1_39_0/libs/mpl/doc/refmanual/vector.html
らしいので比較になるのではないでしょうか。(自分では使ったことがないので自信ないですが…。あと、少なくとも昔はpush_backが未実装だったので今どうなっているかも謎です)
2009/06/01(月) 08:56 | URL | k.inaba #-[ 編集]
おっと*both* endsでしたか。ありがとうございます。斜め読みしてうしろだけかと思ってました。試してみます。
2009/06/01(月) 09:22 | URL | Gus #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/456-b8b9f514
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。