C++のmapについてのめも

速度向上を考える上で、mapの使い方で差が出たのでめも。

mapは[ ]演算子がオーバーロードされているので、演算子の書き方を多用していた。演算子で書くと存在しないkeyを指定した場合、自動で生成してくれる。これが便利なときもあれば不便なときもある。
例えば、メモ化探索にmapを利用していた場合、既に探索した状態かどうかを調べるときに[]演算子で勝手に状態生成してもらっては困る。
なので、今まではこんな感じで書いてた。

map<int,int> mii;

int dfs(int S){
  if( mii.count(S) ){
    return mii[S];
  }
  int ret = 0;
  /*
    処理
   */
  return mii[S] = ret;
}

countメソッドはkeyがあるかどうか(0or1)を返す。勝手に状態数は増えない。
でも、どう考えても　探索3回してるよねこれ

mapの[]演算子の内部処理をgdbデバッガで軽く見てみたところ、
lower_boundメソッドを呼んで、end()と比較して、等しくないならvalueを更新、そうでないならpairの挿入という処理の流れっぽかった。
countメソッドも覗いてみたら、内部でfindを呼んでいる。findの内部処理も、lower_boundの内部処理も同じような感じだった。
というわけで、無駄な探索を減らす。

map<int,int> mii;

int dfs(int S){
  map<int,int>::iterator it = mii.lower_bound(S);
  if( it!=mii.end() && it->first==S ){
    return it->second;
  }
  int ret = 0;
  /*
    処理
   */
  mii.insert(it,make_pair(S,ret));
  return ret;
}

insertメソッドでは、挿入位置のヒントが適切なら定数時間で済む、らしい。
以下のコードで簡単に時間計測してみた。

int main(){
  map<int,int> mii;
  map<int,int>::iterator it;
  for(int i=0; i<1000000; i+=2){
    mii[i] = i;
  }
  for(int i=0; i<1000000; i++){
    it = mii.lower_bound(i);
    
    //ver1
    //mii.insert(make_pair(i,i));

    //ver2
    mii.insert(it,make_pair(i,i));
  }
  return 0;
}

最適化なしでコンパイルした実行ファイルで、5回計測した平均値がこれ。
測定環境は、Gateway GT5020jにDDR2の1GB追加したマシンで、OSはカーネル2.6.35.11-83のFedora14

ver1 :: 2.4462
ver2 :: 1.8040

うおお、地味に差が出た。
mapの[]演算子は便利だけど、てきとーに使うと速度に影響が出る。

2011/03/25 13:22 追記
説明不足で誤解を招くような書き方をしてしまいましたが、
要素を追加するためだけに、lower_boundで探索してからinsertするのは無意味です。
上記は　一度探索してる　という前提の元で書いた記事です。
勘違いされた方、本当にごめんなさい…。