シンクリッジ - STL と MFC の map 速度比較
コーディング小手先テクニックとは多少毛色が違うかもですが、ふと興味が沸いたので調査してみました。マップライブラリの速度比較です。 STL の map と hash_map と、さらに MFC の CMap を比較してみました。 これら全て同じような機能のものなので、どれを使っても普通に動作させることは出来ると思うんですが、多少でも処理速度を稼ぎたい場合にどれを使えばよいかの参考にしたいと思いました。 で、ベンチマークアプリを作って試してみました。 一番ありそうな、文字列(string)をキーとしたマップで、map hash_map CMap それぞれ、insert(SetAt)、find(LookUp) を３秒間にどれだけ行えるかを測定してます。 なお、CMap に関してはハッシュテーブルサイズ（bucketサイズ）を調整することが出来ます。ヘルプには「最高のパフォーマンス
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
STLのページ
角のページへ戻る STL(Standard Template Library) C++の標準テンプレートライブラリ、STLのページです。 2003/6/7 コンテナ全ページ標準に合わせて修正 目次(と予定) 更新履歴 はじめに STLとは? '99 11/07 作成 その前にC++で知っておかなければならないこと 馴染みがない(かもしれない)単語 '99 9/23 わずかに修正 テンプレート(template<>) 2001 1/31 更新 環境 '99 2/20 VCでSGI_STLを使う、BeOS、egcs等 使い方 イテレータ(反復子)の使い方 '99 6/19 更新 関数オブジェクトの使い方 '99 7/4 mem_fun()の使い方追加 早見表 STLで使う主なクラス '99 6/13 各クラスの説明、ヘッダをまとめた STLで使われる名前 '99 6/13 微妙に更
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://rararahp.cool.ne.jp/cgi-bin/lng/vc/vclng.cgi?print%20200601/06010025.txt