C++11 unordered_map

C++11でハッシュコンテナが正式に採用されたということで、
挿入と検索の性能比較を行なってみました。

ネット上に既に色々な人が行った結果がありますが、
入力データの条件に多少は影響を受けるので自前の計測コードを書いておきたかった
というのもあります。

標準入力から文字列を読み込んで、文字列をキーとして様々なコンテナへの格納と
全要素キーの検索を行い、それぞれにかかる時間を計測してみます。

今回はstd::set, std::map, std::unordered_map, boost::unordered_mapを
計測対象とし、入力データは、MacのLibraryフォルダ下のファイルのフルパスを
ソートなしで生成して50000件の文字列を作ってみました。
(パスをキーにしているのはとある事情もあります)

入力データ生成方法:

$ sudo find /Library -exec ls -1df {} \; | head -n 50000 > pathlist.txt

計測条件:

• PC : MacBook 13inch Late2007, 2.2GHz Core 2 Duo
• コンパイラ : g++ 4.6.2, コンパイルオプションは -O2 -std=c++0x
• Boost C++ライブラリ : 1.48
• 計測コンテナ : std::set, std::map, std::unordered_map, boost::unordered_map

※std::setについてはvalue_typeをpair<string,int>として、
　value_typeのfirstで比較・検索するラッパクラスを作成して計測しました

計測結果:

• コンテナ: 挿入, 検索
• set: 0.093635 , 0.083189
• map: 0.092562 , 0.077603
• unordered_map: 0.055996 , 0.032631
• boost::unordered_map: 0.060219 , 0.051342

setとmapはどちらも同じ赤黒二分木の実装のはずなので、違いは誤差の範囲でしょうね。

std::unordered_mapとboost::unordered_mapの差は興味深いですね。
ハッシュアルゴリズムの差かなとも思い、何パターンかの入力データで試してみましたが、
どのパターンでも同じような結果になりました。

std::stringをキーにする限り、ソートされていなくても構わない連想コンテナであればstd::unordered_mapを使っておけば問題なさそうですね。

ちなみに、vectorコンテナを使い挿入をpush_back, 検索をstd::findで実装してみると、
挿入は当然最速になりunordered_mapに対して2倍程度の優位なのに対して、
検索はなんと120秒ととても実用にならない性能になります。まあ当然ですけれど。

タグ：C++11 std::unordered_map