コンテナ内の検索の速度について

追記：この記事には続きがあります。

C++エクササイズその2。前回の実験で、要素の追加についてはvectorの性能が際立っていたので、今度は要素の検索について実験してみた。

vectorに対して要素の検索をする場合、誰もが思いつくのはに定義されているstd::findだろうと思うが、setに対して公正な比較対象になるのはstd::lower_bound()（二分岐探索）だろう。

というわけで、今回はソート済みvectorに対するstd::lower_bound()、set::find()、unordered_set::find()の比較を行ってみた。

1. コンテナに対して100万回検索をかける
2. コンテナサイズは20000から500000まで、20000刻み。各コンテナは同じ乱数を使って初期化（中身は一緒）

結果

さすがにunordered_setは速い。しかしソート済みvectorに対する二分岐探索は、setよりも速い。あれ、set、いいとこ無いじゃん。vectorに比べて挿入は400倍遅くて、検索も2倍から3倍遅いとは。

まとめ

1. 検索に関してはunordered_set最強。これは技術書どおりでホッとした
2. ソート済みの要素に対して検索をかけられるならば、vectorのほうがsetよりも速い
3. 前回の結果と組み合わせると、ソート済みvectorは挿入も検索もsetを凌ぐパフォーマンスを示している。これはハードウェア的な問題なのか、単にsetの実装がマズいのか...。

コード

実験に使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)で、コンパイラオプションも特にいじらず素のリリースモジュールで実験しました。

#include <iostream>
#include <set>
#include <vector>
#include <unordered_set>
#include <random>
#include <functional>
#include <algorithm>
#include <omp.h>

using namespace std;

static void BenchmarkFind()
{
  default_random_engine generator;
  uniform_int_distribution<int> distribution;
  auto dice = bind(distribution, generator);

  vector<size_t> DATA_LENGTH_ARRAY(25);
  size_t next = 20000;

  for (auto& len : DATA_LENGTH_ARRAY)
  {
    len = next;
    next += 20000;
  }

  vector<int> QUERY_DATA(1000000);
  for (auto& dat : QUERY_DATA)
    dat = dice();

  cout << "size,vector,set,unordered_set" << endl;

  for (auto DATA_LENGTH : DATA_LENGTH_ARRAY)
  {
    vector<int> vals(DATA_LENGTH);

    for (auto& val : vals)
      val = dice();

    cout << DATA_LENGTH;
    {
      vector<int> cont(begin(vals), end(vals));
      sort(begin(cont), end(cont));
      cont.erase(unique(begin(cont), end(cont)), end(cont));
      double dStart = omp_get_wtime();

      for (auto val : QUERY_DATA)
        lower_bound(begin(cont), end(cont), val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      set<int> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      unordered_set<int> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }

    cout << endl;
  }
}

int main(int argc, char* argv[])
{
  BenchmarkFind();
  return 0;
}