通し番号をキーにしたmapは構築しないで！

やあ子供たち元気にしてるかい。今日は複数のオブジェクトがあるとき、それぞれのオブジェクトに通し番号をつけて、その通し番号でオブジェクトを逆に検索したい、なんていう場合の話だよ。こういうときに、int値の集合をキーにしたmapを構築してしかもそれを使って検索して、遅い！なんて嘯いてそうな人はいないかな。

もし本当にそんなことをしてたら今すぐそこはvectorに書き直そう。キーの全体集合が「連続するただのint値通し番号」なんだったら二分木なんて引っ張り出す必要は全くなくて、ただのvectorの添え字で十分だ。その方が構築も速いし検索も速い。これはもともとのオブジェクトの集合が、通し番号管理されていなかったり、あるいは散在していたりする場合に子供たちが陥ってしまいがちな危険なアンチパターンだとおじさんは考えているよ。

とくにオブジェクトの数が数万、数百万オーダーになってくると処理時間はmapの場合とvectorの場合とで数10倍以上も違ってくるのだから気をつけてくれ、5秒が500秒になったらユーザーはいくら時間があっても足りなくなってしまうし、そんなコードを書き散らかしてるらしいなんて上司や同僚に思われたら今すぐにでもファイアーされてしまうかも知れないからね。
以下では120万のオブジェクトをその通し番号で検索かけて取り出す処理の実験実装だよ。それぞれ、mapを使ったバージョンとvectorを使ったバージョンの用意して、その処理時間を計測してみた。
時間計測には ExclusiveMMTimer を使っているよ。こういうちょっと正確なタイマーが欲しいなんて時にExclusiveMMTimerは本当に便利だね。

  // A* のlist を構築
  const int N = 120*1e4;// 120万
  list< A* > va( N );
  {
    generate( va.begin(), va.end(), CreateA );
  }

  // map を使った探索
  {
    ExclusiveMMTimer* mm = // 時間計測用
      ExclusiveMMTimer::Create( MyCallback(), 1, 1 );	
    {
      // map の構築
      map< int, A* > mp;// 間違いの始まり（不適切なコンテナの選択）
      {
        int i=0;
        for each( A* ia in va ){
          mp.insert( make_pair( i, ia ) );
          ++i;
        }// ia, i
      }
      //　通し番号をキーにした、A*の探索テスト
      for( int query=0; query<2*N; ++query ){
        map< int, A* >::iterator it  = mp.find( query );    
      }// i
    }
    cout << mm->m_elapsed <<"ms"<<endl;// 時間計測用
    delete mm;// 時間計測用
  }
  // vector を使った探索
  {
    ExclusiveMMTimer* mm = // 時間計測用
      ExclusiveMMTimer::Create( MyCallback(), 1, 1 );	
    {
      // vector の構築
      vector< A* > mv;
      mv.reserve( va.size() );
      mv.assign( va.begin(), va.end() );
      //　通し番号をキーにした、A*の探索テスト
      for( int query=0; query<2*N; ++query ){
        if( query >=0 && query<N )
          A* it  = mv[ query ];    
      }// i
    }
    cout << mm->m_elapsed <<"ms"<<endl;// 時間計測用
    delete mm;// 時間計測用
  }

で、実行結果が以下だ。

500ms
17ms

とまあ、このように、この簡単な場合でも検索準備の構築時間を含めてざっと30倍ほど速度が異なってくるのがわかると思う。
いつも言ってることではあるけれど、どうしてもvector以外のコンテナを使わなくてはならないその理由をしっかり認識し、vector以外のコンテナを使うリスクを最小限にとどめて欲しいと、おじさんはいつも願っているよ。