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