静的に std::unordered_set/map を構築してみる

std::unordered_map に言及しているブログを見て，記事にするのを忘れていたことを思い出しました．

重複のないデータセットがあるときは std::unordered_set/map に一つずつ登録するより，std::vector か何かに入れてから一気に std::unordered_set/map を構築した方が速くなるかもしれませんという内容です．なぜ速くなるのかについては，ハッシュ表の拡張にかかるコストをなくせることや，充填率が低い状態での登録になることが挙げられます．

実験結果を表にしてみました．ちょうど良い大きさ（約 900 万行）だったので，登録するデータセットには英語版 Wikipedia のタイトル一覧を使用しています．時間については /usr/bin/time -p により計測した real の値を示しています．

実験結果
- #lines: 先頭から何行目までを使用したか
- getline: 行単位で読み込むのにかかった時間（秒）
- vector: std::vector に登録するのにかかった時間（秒）
- set: std::unordered_set に登録するのにかかった時間（秒）
- vec+set: std::vector に登録してから std::unordered_set に登録しなおすのにかかった時間（秒）

#lines	getline	vector	set	vec+set
1024	0.00	0.00	0.00	0.00
2048	0.00	0.00	0.00	0.00
4096	0.00	0.00	0.00	0.00
8192	0.00	0.00	0.01	0.00
16384	0.00	0.01	0.01	0.01
32768	0.00	0.01	0.04	0.03
65536	0.01	0.03	0.09	0.06
131072	0.01	0.06	0.20	0.14
262144	0.04	0.11	0.43	0.28
524288	0.07	0.22	0.92	0.57
1048576	0.15	0.44	1.48	1.19
2097152	0.27	0.89	3.11	2.45
4194304	0.53	1.78	6.51	5.12
8388608	1.06	3.57	13.69	10.92

set と vec+set を比べると，劇的というほどではないものの，それなりに短縮されていることが分かります．実装に関する手間はほとんどないので，意外と使えるかもしれません．

実験に用いたソースコードは以下にあります．

// getline: std::getline() を使って文字列を行単位で読み込むだけです．
int main() {
  std::ios_base::sync_with_stdio(false);
  std::string line;
  while (std::getline(std::cin, line)) {
  }
  return 0;
}

// vector: std::getline() を使って読み込んだ文字列を std::vector に登録します．
int main() {
  std::ios_base::sync_with_stdio(false);
  std::string line;
  std::vector<std::string> vec;
  while (std::getline(std::cin, line)) {
    vec.push_back(line);
  }
  return 0;
}

// set: std::getline() を使って読み込んだ文字列を std::vector に登録します．
int main() {
  std::ios_base::sync_with_stdio(false);
  std::string line;
  std::unordered_set<std::string> set;
  while (std::getline(std::cin, line)) {
    set.insert(line);
  }
  return 0;
}

// vec+set: std::getline() を使って読み込んだ文字列を std::vector に登録します．
//          読み込みが終わってからまとめて std::unordered_set に登録します．
//          reserve() してから insert() するのでも同様の結果になりました．
int main() {
  std::ios_base::sync_with_stdio(false);
  std::string line;
  std::vector<std::string> vec;
  while (std::getline(std::cin, line)) {
    vec.push_back(line);
  }
  std::unordered_set<std::string> set(vec.begin(), vec.end());
  return 0;
}