std::map/std:setの性能改善
C++のコードでは、std::map
とstd::set
はよく見かけますが、std::unordered_map
とstd::unordered_set
の方はあんまり見ないのはなんでだろう、と思う時があります。
単純に知名度が低いだけなのか、それともカスタム型をキーとして使う時に自分でハッシュ関数を定義しないといけないせいで使いづらいからなのか。でもstd::map
もカスタム型をキーとして使う時は、そのカスタム型に<
演算子を定義しないといけないため、そう変わらないと思います。
後、std::unordered_map
とstd::unordered_set
はstd::map
とstd::set
よりパフォーマンスが断然いいので、もっと使ってもいいと思います。
なので、今回はstd::unordered_map
を紹介してみようと思います。
std::map
の要素はキーでソートされているのですが、std::unordered_map
の要素は名前通りソートされていないです。
ですので、要素の順番が大事なケースはstd::map
の方を使わないといけないです。でも順番がどうでもいいケースって結構あると思うのです。逆に順番が大事なケースって、for ループで毎回同じ順番で出力したい時ぐらいだと思います。
普通にキーを使って要素にアクセスする場合は、キーの順番などどうでもいいはずです。
std::map
はアクセス時間がO(1)
というイメージが強いですが、実は内部で赤黒木を使っているため、アクセス時間がO(log N)
です。
それに対して、std::unordered_map
はハッシュテーブルを使っていて、キーがすべて違う値にマッピングされている限り、アクセス時間がO(1)
です。
たくさんデータを扱っていると、使われたハッシュ関数によってハッシュ値が被ったりするため、ワーストケースがO(N)
になりますが、平均的にはstd::map
より速いです。
使い方は以下のようにstd::map
と完全に同じです。
#include <unordered_map>
std::unordered_map<std::string, int> umap;
umap["foo"] = 1;
umap["bar"] = 2;
for (const auto& pair : umap)
{
std::cout << pair.first << ", " << pair.second << std::endl;
}
キーとしてカスタム型を使いたい場合は、以下のように==
演算子とハッシュ関数を提供しないといけないです。
struct Data {
Data(int d)
: data(d)
{}
bool operator==(const Data& other) const
{
return data == other.data;
}
int data;
};
struct DataHash {
size_t operator()(const Data& d) const
{
return std::hash<int>()(d.data);
}
};
std::unordered_map<Data, int, DataHash> data_map;
カスタム型のメンバー変数が1つだけあって、それが基本型の場合は、そのメンバー変数をそのままstd::hash
に渡せればいいため、楽です。
std::hash
はすべての基本型で使えるようになっています。でもパフォーマンスが大事な場合は、std::hash
を使わずに、自分のカスタムなハッシュ関数を作ってもいいです。
複数のメンバー変数がある場合は、以下のようにそれぞれのハッシュ値を計算してから、一つに結合しないといけないです。
struct Point {
Point(int x, int y)
: x(x)
, y(y)
{}
bool operator==(const Point& other) const
{
return x == other.x && y == other.y;
}
int x, y;
};
struct PointHash {
size_t operator()(const Point& p) const
{
return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
}
};
この場合は、x
とy
のハッシュ値を計算してから、一方のビットを左にシフトしてから、AND
で結合しています。他にXOR
も使ったりします。boost::combine_hash
の中身を見てみると、もっと複雑な内容になっています。
本当は標準ライブラリにハッシュを結合する関数があればいいのですが、ハッシュ関数とユースケースによって違う最適な方法が変わるため、プログラマーが自分で定義しないといけないようになっています。
ハッシュ関数とハッシュ値を結合させる方法が良くないと、複数のキーが同じ値にマッピングされて同じバケットに入れられることが多くなり、そういうキーのアクセス時間がO(l)
からO(log N)
に変わります。
でもこれは、たくさんデータを扱っている場合のみ大事になるだけで、一般的なケースでは問題になることはないです。そもそもキーとして複数のメンバー変数を持っているカスタム型を使うこと自体がかなり稀だと思います。
纏めとして、使い分けと共に書いてみるとこんな感じになると思います。
- キーをソートしたい場合は
std::map
を使う - それ以外の場合は
std::unordered_map
を使う
ぜひ使ってみてください。
Discussion