コンテナ内の検索の速度について(2) ～setの使いどころ～

C++エクササイズその3。前回、前々回の実験で、setの良さが発揮できなかったものの、何となく経験に反する結果だったので、もう一つだけ実験してみた。

具体的には、要素の中身をintからstringに変え、要素数2000から50000のコンテナに対してそれぞれ100万回検索をかけて時間を測定した。

結果

横軸がコンテナの要素数、縦軸が100万回findするのに要した時間（単位：秒）

ソート済みvectorはそれでも大健闘。挿入の速さやメモリ効率を考えると使いどころは多いと思う。string程度の大きさのオブジェクトで、ある程度比較関数も複雑になってくると、メモリ上の構造のシンプルさよりもアルゴリズム的な優位性が利いてきて、setに分がでてくるということなんだろうか。

まとめ

intのような単純なオブジェクトでなければ、やはりsetの方が検索は速いが、ソート済みvectorにも挿入の速さやメモリ効率などのアドバンテージがあるので、状況に応じて両方使いこなすとよい。単に検索目的であればunordered_set一択。

コード

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

using namespace std;

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

  uniform_int_distribution<int> distChar(65, 90);
  auto diceChar = bind(distChar, generator);

  uniform_int_distribution<size_t> distStrLen(16, 128);
  auto diceStrLen = bind(distStrLen, generator);

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

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

  vector<string> QUERY_DATA(1000000);

  for (auto& dat : QUERY_DATA)
  {
    auto len = diceStrLen();
    dat.reserve(len + 1);

    for (size_t i = 0; i < len; ++i)
      dat += (char)diceChar();
  }

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

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

    for (auto& val : vals)
    {
      auto len = diceStrLen();
      val.reserve(len + 1);

      for (size_t i = 0; i < len; ++i)
        val += (char)diceChar();
    }

    cout << DATA_LENGTH;
    {
      vector<string> 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<string> 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<string> 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[])
{
  BenchmarkFindString();
  return 0;
}