睡眠不足?! RSSフィード

2371597

2012-11-11

[]mapとunordered_mapのアイテム全走査の比較とmapの存在意義について考える

過去の記事でvectorに比べてmapの全走査が遅いという比較を行ったことを思い出し,そういえばunordered_mapとの比較をしていなかったので比較をすることにした.

前回のコードに以下のようなコードを追加して実験.

今回は以下のようなデータ構造を追加

  • (a) unordered_map<int, int>
  • (b) vector<int> + map<int, int>
  • (c) vector<int> + unordered_map<int, int>

(b)や(c)は,keyのデータを別途vector配列に入れておいて,そちらを走査しながらmapを引くというコードをよく書いているので,これやるとどんくらい遅くなるのだろうということを調べるため.

前回のコードとのdiffはこんな感じ.

6d5
< #include <unordered_map>
46,47d44
<   std::vector<int> key_vec;
<   std::unordered_map<int, int> um;
53,54d49
<     um[ *itr ] = 1;
<     key_vec.push_back( *itr );
79,117c74,75
<   // unordered_map
<   double t5 = gettimeofday_sec();
<   double umsum = 0.0;
<   std::unordered_map<int, int>::iterator uitr = um.begin();
<   while (uitr != um.end()) {
<     umsum += (uitr->first * uitr->second);
<     ++uitr;
<   }
<   double t6 = gettimeofday_sec();
<
<
<   // map + key vec
<   double t7 = gettimeofday_sec();
<   std::vector<int>::iterator kitr = key_vec.begin();
<   double kmsum = 0.0;
<   while (kitr != key_vec.end()) {
<     int key = *kitr;
<     kmsum += (key * m[ key ]);
<     ++kitr;
<   }
<   double t8 = gettimeofday_sec();
<
<
<   // unordered_map + key vec
<   double t9 = gettimeofday_sec();
<   std::vector<int>::iterator kitr2 = key_vec.begin();
<   double kumsum = 0.0;
<   while (kitr2 != key_vec.end()) {
<     int key = *kitr2;
<     kumsum += (key * um[ key ]);
<     ++kitr2;
<   }
<   double t10 = gettimeofday_sec();
<
<
<   if (msum != vsum ||
<       msum != umsum ||
<       msum != kumsum) {
<     std::cerr << "ERROR: msum != vsum or brabrabra" << std::endl;
---
>   if (msum != vsum) {
>     std::cerr << "ERROR: msum != vsum" << std::endl;
126,128d83
<   std::cout << "    umap time=" << (t6 - t5) << " sec." << std::endl;
<   std::cout << " vec+map time=" << (t8 - t7) << " sec." << std::endl;
<   std::cout << "vec+umap time=" << (t10 - t9) << " sec." << std::endl;

結果

O3最適化オプションの結果は以下のとおり.実験条件は前回と同じ.

% ./map-vs-vector_each_O3
========================================
  min=0 max=100000000 num=1000000
  idnum=994988
     map time=0.025021 sec.
  vector time=0.00304701 sec.
    umap time=0.0163119 sec.
 vec+map time=0.148234 sec.
vec+umap time=0.05696 sec.
========================================
========================================
  min=0 max=100000000 num=2000000
  idnum=1980206
     map time=0.0489781 sec.
  vector time=0.00605991 sec.
    umap time=0.036946 sec.
 vec+map time=0.305442 sec.
vec+umap time=0.125602 sec.
========================================
========================================
  min=0 max=100000000 num=3000000
  idnum=2955469
     map time=0.0753331 sec.
  vector time=0.0090471 sec.
    umap time=0.0403191 sec.
 vec+map time=0.455493 sec.
vec+umap time=0.144672 sec.
========================================

考察

  • unordered_mapの全走査はmapよりも速い (1.5-2倍程度)
  • keyだけvectorに入れてmap/unordered_mapから引くという操作をすると5倍以上遅くなる
    • map vs. vec+map, umap vs vec+umapの比較

以外なことにunordered_mapがmapよりも速い.そしてkeyだけvectorに入れるとこれほどまで遅くなるとはこれまた意外.

なお@tkngさんのブログ記事によるとunordered_mapはメモリ的にもmapより効率がよいみたいなので,もはやmapを使う理由が存在しないような気がする.

unordered_といういかにもtypoしそうなタイピングコストとコンパイル時の-std=c++0xというタイピングコストくらいなのではないだろうか.前者はマクロを使えば解決するので,もはやmapの存在意義がわからない.

unordered_mapのハッシュがどのように実装されているのかソース読んでいないので知らないけれどきっとチェインハッシュだろうと勝手に考えてみる.そうするとテーブル部分は当然配列で持っているだろうし,各チェインについてたとえばvectorのような可変長配列で持っておくとキャッシュ効率的によい.というわけで全舐めについてもunodered_mapがmapに対して効率的だということがなんとなく納得できる感じ.さてハッシュだと衝突によるチェインの長さ増加を避けるためにテーブルサイズを最初から大き目に取っておくとする.するとアイテム数がごく少量の場合はmapの方が省メモリになるのではないか.


追加実験

それくらいなら調べられるだろうと思って調査.単純にmap<int, int>とunordered_map<int, int>を空の状態で作成した場合といくつか要素を追加した際のプロセスの使用メモリの比較をした.使用メモリは /proc/<process id>/statusのVmRSS の数字を用いた.いずれも最適化オプションは無し.

  • 初期状態 (宣言のみ)
    • map: 808kB
    • umap: 856kB
  • 1アイテム追加
    • map: 872kB
    • umap: 872kB
  • 5アイテム追加
    • map: 872kB
    • umap: 872kB
  • 10アイテム追加
    • map: 872kB
    • umap: 872kB
  • 100アイテム追加
    • map: 876kB
    • umap: 872kB
  • 1000アイテム追加
    • map: 900kB
    • umap: 896kB

追加実験で得られた結果をまとめる

  • ハッシュのテーブル初期サイズはどうやら6000 (= 48000 / (4 + 4)) アイテム?
  • 宣言のみの状態だとmapの方が使用メモリが大きい
  • アイテムを1個でも追加した状態では使用メモリサイズは等しくなる
  • 1000個追加でunordered_mapの方が省メモリになる
  • 予想と@tkngさんの検証からきっとこれよりアイテム数が増えてもunordered_mapの方が省メモリ

結論

ありがとうmap.君のことは忘れないよ.

kariya_mitsurukariya_mitsuru 2013/01/09 21:52 亀コメントですみません。
頻繁に追加削除が行われる&常にソートされてて欲しい場合は依然として map が良いですね。

sleepy_yoshisleepy_yoshi 2013/02/03 12:09 レスありがとうございます.なるほど追加削除は考えていませんでした.
常にソートされているというのが必要なのは,たとえばある値を取得したあとに,次に大きい,小さい値が欲しいといったような操作のときですよね.
確かにハッシュだとその際全走査が必要になりますね.それは見落としていました.ありがとうございます.

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

リンク元
Connection: close