はじめに
「俺の妹がこんなに可愛いわけがない」の桐乃は本当に可愛いですね。
リアルタイムで見ていた二期の最終話、桐乃の可愛さにやられて一日中眠れませんでした。
でも、僕の使っているC++のunordered_mapも非常に可愛いんですよね。
競技プログラミングだと、結構な頻度でmapやunordered_mapなど、ランダムなキーをもつデータ構造を使用することがあります。
($0, ..., N$を連続とします。)
入力が$N = 10^5$個くらいで、$1$~$10^{18}$までの値が$10^5$個ランダムに与えられることがあるため、map, unordered_mapを使用するしかありません。
そして、前回のAtCoderBeginner139のE問題では、unordered_mapの可愛さが一段と輝いていました。
最初は
int main() {
map<pair<int, int>, vector<int>> mp;
}
のような、pairをキーにもつmapを使用していました。
そのときのソースコードです。
しかし、入力が大きく$O(N^2logN^2)$は厳しかったようでTLEしてしまいました。
そこで、unordered_mapならワンチャン間に合うんじゃないか？と思い以下のようにデータ構造を書き換えました。
int main() {
unordered_map<pair<int, int>, vector<int>> mp;
}
unordered_mapならキーをハッシュ化して、順序は取れないものの$O(1)$で平均要素アクセスができるため、間に合うのでは？と思ったためです。
しかし、以下のようになります。
In file included from /Library/Developer/CommandLineTools/usr/include/c++/v1/unordered_map:384:
/Library/Developer/CommandLineTools/usr/include/c++/v1/__hash_table:868:5: error: static_assert failed due to requirement '__check_hash_requirements<pair<int, int>, hash<pair<int, int> > >::value' "the specified hash does not meet the Hash requirements"
static_assert(__check_hash_requirements<_Key, _Hash>::value,
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Library/Developer/CommandLineTools/usr/include/c++/v1/__hash_table:883:1: note: in instantiation of template class 'std::__1::__enforce_unordered_container_requirements<std::__1::pair<int, int>, std::__1::hash<std::__1::pair<int, int> >, std::__1::equal_to<std::__1::pair<int, int> > >' requested here
typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
^
/Library/Developer/CommandLineTools/usr/include/c++/v1/unordered_map:828:26: note: while substituting explicitly-specified template arguments into function template '__diagnose_unordered_container_requirements'
static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
^
/Users/students/students_folder/ganariya/ClionProjects/ICPC/main.cpp:57:48: note: in instantiation of template class 'std::__1::unordered_map<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> >, std::__1::hash<std::__1::pair<int, int> >, std::__1::equal_to<std::__1::pair<int, int> >, std::__1::allocator<std::__1::pair<const std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > > > >' requested here
unordered_map<pair<int, int>, vector<int>> mp;
^
In file included from /Users/students/students_folder/ganariya/ClionProjects/ICPC/main.cpp:6:
/Library/Developer/CommandLineTools/usr/include/c++/v1/unordered_map:407:11: error: call to implicitly-deleted default constructor of 'std::__1::hash<std::__1::pair<int, int> >'
: _Hash() {}
^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:2176:39: note: in instantiation of member function 'std::__1::__unordered_map_hasher<std::__1::pair<int, int>, std::__1::__hash_value_type<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > >, std::__1::hash<std::__1::pair<int, int> >, true>::__unordered_map_hasher' requested here
_LIBCPP_INLINE_VISIBILITY constexpr __compressed_pair_elem() = default;
^
/Library/Developer/CommandLineTools/usr/include/c++/v1/unordered_map:871:5: note: in instantiation of member function 'std::__1::__hash_table<std::__1::__hash_value_type<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > >, std::__1::__unordered_map_hasher<std::__1::pair<int, int>, std::__1::__hash_value_type<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > >, std::__1::hash<std::__1::pair<int, int> >, true>, std::__1::__unordered_map_equal<std::__1::pair<int, int>, std::__1::__hash_value_type<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > >, std::__1::equal_to<std::__1::pair<int, int> >, true>, std::__1::allocator<std::__1::__hash_value_type<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > > > >::__hash_table' requested here
unordered_map()
^
/Users/students/students_folder/ganariya/ClionProjects/ICPC/main.cpp:57:48: note: in instantiation of member function 'std::__1::unordered_map<std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> >, std::__1::hash<std::__1::pair<int, int> >, std::__1::equal_to<std::__1::pair<int, int> >, std::__1::allocator<std::__1::pair<const std::__1::pair<int, int>, std::__1::vector<int, std::__1::allocator<int> > > > >::unordered_map' requested here
unordered_map<pair<int, int>, vector<int>> mp;
^
/Library/Developer/CommandLineTools/usr/include/c++/v1/utility:1567:36: note: default constructor of 'hash<std::__1::pair<int, int> >' is implicitly deleted because base class '__enum_hash<std::__1::pair<int, int> >' has a deleted default constructor
struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp>
^
/Library/Developer/CommandLineTools/usr/include/c++/v1/utility:1561:5: note: '__enum_hash' has been explicitly marked deleted here
__enum_hash() = delete;
エラコードたくさん吐いてかわいい〜（キレそう）
というわけで今回は、僕のunordered_mapをpair型がキーに来ても、対応できるようにすることを目指します。
map、そしてunordered_mapとは
そもそもmap, unordered_mapとは何でしょうか？
map・unordered_mapは、C++の標準ライブラリとして整備されているSTLコンテナです。
#include <map>
#include <unordered_map>
以上のコードでincludeできます。
map
mapは、C++の標準ライブラリの平衡二分木というデータ構造です。
map内部では、常に要素がキーでソートされています。
（ソートされている、というよりかは、木構造にすることで大小関係を作っている、というイメージです。）
キーの要素で常にソートされるため、キーに使用できる値には比較演算子が定義されている必要があります。
pair型は、まずfirstで比較する、そしてsecondで比較するという演算子がすでにtemplateで定義されているため、pairなどの組み込み型ならすぐにそのままキーに使用することができます。
挿入・削除・検索、すべてが$O(logN)$でアクセスできるスグレモノです。
ただ、要素が大きくなってくると毎回のアクセスが遅くなるため、定数倍が厳しくTLEしてしまいます。
unordered_map
一方、unordered_mapは俗にいわれるハッシュ・連想配列というデータ構造です。
unordered_mapでは、要素は一切ソートされていません。
forで要素アクセスをしてもどの順番でアクセスされるかは保証されていないほど、ランダムです。
しかし、キーをハッシュ化することで、要素を格納する位置を$O(1)$で求めることができ
衝突しなければ挿入・削除・検索すべてを$O(1)$に定数倍かかるくらいでアクセスすることができます。
衝突しなければ、というのがポイントで、キーのハッシュ値がべらぼうに衝突すれば、著しく実行スピードは低下します。
通常の日常業務なら、おそらくそこまで衝突しませんが、競技プログラミングでは衝突するようにテストケースを作られて落とされることがあるため、注意が必要です。
どうしてpair型をunordered_mapのキーにデフォルトではできないのか？
map, unordered_mapの違いを見てきました。
それでは、どうしてpair型をunordered_mapのキーにデフォルトではできないのでしょうか？
map型のキーは、常に内部ソートをするために比較演算子が定義されている必要があります。
pair型は、templateでfirst->secondの順番で比較するように予め定義するため、ユーザは自分で定義することなく、pair型をmapのキーにできます。
一方、unordered_map型のキーはハッシュ可能でなければなりません。
これは、unordered_mapが動く仕組みがそもそも、キーに来た値をハッシュして利用しているためです。
int, double, stringなどの基本の組み込み型は、すでにこのハッシュ可能になるような関数オブジェクト(ファンクタ)が定義されているため、そのままunordered_mapのキーにすることができます。
しかし、pair型には、ハッシュ可能になるような関数オブジェクト(ファンクタ)というものが予め定義されていません。
そのため、最初からpair型をキーにすることができません。
よって、ユーザがpair型などをunordered_mapのキーにしたい場合は
関数オブジェクト(ファンクタ)を定義すればよいようです。
int main() {
//templateの第3項目に自作関数オブジェクトを入れる
//HashPairの実装はのちほど
unordered_map<pair<int, int>, vector<int>, HashPair> mp;
}
僕たちは、関数オブジェクトと、C++でのハッシュの仕組みを理解しないといけないようです。
関数オブジェクト(ファンクタ)
それでは関数オブジェクトとは何なのでしょうか？
他の多くのC++の記事だと以下のように書かれています。
通常の関数に、状態を保持できるようにしたもの。STLなどと組み合わせるとシンプルにかけて嬉しい。
よくわからないのできちんと自分でも勉強してみようと思います。
関数オブジェクトは、ただの演算子オーバーロード
実は関数オブジェクトは、普通のクラス構造に、()という演算子のオーバーロードをしているだけです。
struct Functor {
int m_base;
Functor(int base) : m_base(base) {
}
int operator()(int x) {
return x * m_base++;
}
};
int main() {
Functor functor(10);
for (int i = 0; i < 10; i++) {
cout << functor(10) << endl;
}
// 100
// 110
// 120
// 130
// 140
// 150
// 160
// 170
// 180
// 190
}
例えば、以上のような場合を考えてみます。
Functorクラス(struct構造体を使ってpublicをサボっていますが)
を定義して、その中に()演算子をオーバーロードしています。
そして、main側では、Functorインスタンスを関数呼び出しのように使用しています。
ここの特徴として、functorインスタンスがそれぞれm_baseという状態変数をインスタンスごとに保持しながら関数のように扱える、というのが嬉しい点ですね。
関数オブジェクトのメリット
関数オブジェクトが、()をオーバーロードして変数を内部で保存できる、という事がわかりました。
それでは、どうしてこのような関数オブジェクトがいるのでしょうか？
別に関数に外部変数を持っておけばよいのではないでしょうか？
メリット1 インスタンスごとに状態が持てる
struct Functor {
int m_base;
Functor(int base) : m_base(base) {
}
int operator()(int x) {
return x * m_base++;
}
};
int main() {
Functor functor(10);
for (int i = 0; i < 10; i++) {
cout << functor(10) << endl;
}
Functor functor2(1342300);
for (int i = 0; i < 10; i++) {
cout << functor2(10) << endl;
}
}
以上のようにしてみます。
こうすると、functor, functor2の振る舞いは当然異なります。
なぜなら、これらのインスタンスは別々であり、その内部で状態を各自もっています。
よって、コンストラクタ時にそれぞれの違う内部状態の設定などができる、というのも嬉しい点だと思います。
メリット2 関数に、関数オブジェクトを関数として渡せる
struct Functor {
int m_base;
Functor(int base) : m_base(base) {
}
int operator()(int x) {
return x * m_base++;
}
};
void use_functor(function<int(int)> func, int x) {
cout << func(x) << endl;
//200
}
int main() {
Functor functor(10);
use_functor(functor, 20);
}
例えば、以上のように関数オブジェクトをまるで関数自体を渡すかのように振る舞うことができます。
use_functor関数では、funcというintを引数にとりintを帰り値という関数自体を引数にとりますが、それにFunctorオブジェクトを渡し
関数のように振る舞わせることができます。
このようにすれば、昔のC言語のように関数のポインタ渡しをしなくてよいので嬉しいです。
メリット3 実行速度がはやい
関数オブジェクトは、なぜか色々と早いそうです。
理由がわかっていないので、詳しい方にコメントいただければ助かります。
kazatsuyuさんからコメントをいただきました！
ありがとうございます！
関数の実現方法には
- 関数（関数ポインタ）
- 関数オブジェクト（ファンクタ）
の２つがあります。
C++では、関数の名前自体がその関数が定義されているアドレスを指しています。つまり、関数ポインタ==関数の名前、が成り立ちます。
この通常の関数の関数ポインタを使用する場合と、関数オブジェクトを使用する場合なら、関数オブジェクトを使用するほうが早いときもあるらしいです。
これは、コンパイル時の最適化・実行時のアドレス推測などから影響してくるようですが、ケースバイケースらしいので、実際に測ってみないとわからないようです。
メリット4 STLと相性がいい
int main() {
vector<int> a(10);
iota(a.begin(), a.end(), 0);
for(int i = 0;i<10;i++) cout << a[i] << " ";
//0 1 2 3 4 5 6 7 8 9
}
以上のiotaというstd関数は、iotaの第３引数0をスタートとしてインクリメントしながら、コンテナの要素を埋めてくれます。
しかし、場合によっては初期値を$3$として$2$ずつ増やしたい。
つまり$3 ,5 ,7, 9 ,11,13, 15, 17, 19, 21$のようにしたいときもあります。
そこで、関数オブジェクトを使うことができます。
struct InitFunctor {
InitFunctor(int base, int increment) :
m_base(base), m_increment(increment) {
}
//xを参照する
int operator()(int &x) {
x = m_base;
m_base += m_increment;
}
private:
//初期値
int m_base;
//一回分の増加
int m_increment;
};
int main() {
vector<int> a(10);
for_each(a.begin(), a.end(), InitFunctor(3, 2));
for(int i = 0;i<10;i++) cout << a[i] << " ";
//3 5 7 9 11 13 15 17 19 21
}
以上のプログラムではfor_eachという関数を利用しています。
これは、コンテナの要素に対して、第3項目で渡した関数を実行するというものです。
先程まで関数オブジェクトは、関数のように振る舞うということを示しました。
そのため、第３項目に関数オブジェクトを渡せば、初期値$base =3 $、増加分$increment = 2$となり、
operatorの引数を参照型にすることで、2ずつ増やすことができます。
このように、STLにファンクタを組み合わせると、多くの表現を行うことができます。
ラムダ式
関数オブジェクト（ファンクタ）ですが
最近では、ラムダ式というものがあるため、影が強まっています。
というのもラムダ式は即時関数というどの言語にもある概念で
特にメジャーなのがjavascriptの書き方だと思います。
ただ、C++だと後発してラムダ式が出ているため少し複雑な書き方になっています。
このラムダ式はコンパイルすると関数オブジェクトになります。
そして、当然ですが関数オブジェクトをユーザが書くより、ラムダ式として書いたほうが高速な最適化を受けながら、シンプルに書くことができます。（ようです、僕はまだ理解できてないです）
よって、最近ではラムダ式のほうが人気なようです。
std::hash
ここまで関数オブジェクトを見てきました。
それでは、C++のunordered_mapがどうハッシュを扱っているのか？
を見てみましょう。
std::hashの組み込み型
その前にまず、組み込み型のint, double, stringに対して
ハッシュがどう行われているのかを見てみましょう。
int main() {
hash<int> int_hash{};
hash<double> double_hash{};
hash<string> string_hash{};
cout << int_hash(232) << endl;
cout << double_hash(42432.34242432) << endl;
cout << string_hash("Hello, World") << endl;
/*
232
4676064670319368440
7750308374451649530
*/
}
以上のようにstd::hashは、テンプレートで宣言されているクラスです。
使用するまえには、まずhashのように型を指定してインスタンスを生成します。
そして、hashインスタンスは先程見たとおり関数オブジェクトとして定義されています。
そのため、int_hash(232)のように関数呼び出しのように使用すれば、ハッシュ値が帰ってきます。
intだとそのまま帰ってきますが、double, stringだと面白い結果が帰ってきますね。
hashクラス
このようにstd::hashは、std名前空間に定義されているテンプレートクラスのようです。
そして、hash, hashといった基本的な型に関してはテンプレートの特殊化がなされており、関数オブジェクトとして()の演算子定義内に、ハッシュ処理がすでにライブラリ側で実装されているようです。
テンプレートの特殊化とは
「テンプレートにすると、すべての型をいちいちそれぞれ書かなくてよいので楽だなぁ〜〜〜！あっ、でもintの型指定があったときだけは、別の処理で動かしたいなぁ〜〜！」
みたいな、基本的にはテンプレートですが、ある型のみは特別な処理で例外で動かす、といった別行動を可能とするものです。
そして、int, doubleなどの基本組込型に対しては、（）の演算子定義がすでに特殊化で実装されているようです！
しかし、当然ですが以下のコードは動きません。
int main() {
hash<pair<int, int>> pair_hash{};
cout << pair_hash(make_pair(10, 20)) << endl;
}
C++のライブラリ側ではpairの場合のテンプレートの特殊化がなされておらず
pair_hash(make_pair())のように関数のように振る舞わせても、そもそもまだ定義されていないので、実行できずエラーになるのです。
よって、C++にpair型の場合のhashの（）の降る舞いを定義してあげる必要があります。
実装（仮）
いよいよ実装です。
hashクラスに、pair型の場合が来た場合の（）演算子のオーバーロードを明記してあげます。
struct HashPair {
//注意 constがいる
template<class T1, class T2>
size_t operator()(const pair<T1, T2> &p) const {
//first分をハッシュ化する
auto hash1 = hash<T1>{}(p.first);
//second分をハッシュ化する
auto hash2 = hash<T2>{}(p.second);
//重複しないようにハッシュ処理
size_t seed = 0;
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
int main() {
//第3項目にHashPairという
//()をオーバーロードしたクラスを指定する
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
mp[make_pair(i, j)] = i + j;
}
}
}
以上のように, unordered_mapでキーに使用したいものを受け取る
struct/classを（）演算子オーバーロードします。
そして、その内部で、どうキーをハッシュするか？を記述すればよいです。
pair型ではまず
firstをstd::hashでハッシュ化
secondをstd::hashでハッシュ化しています。
当然、このfirst,secondはstdですでにライブラリで定義されているハッシュを使用しているため、このfirstに自作クラスなどを使うときはそれようにまた自分で定義が入ります。
その後のseedの部分はboostライブラリのハッシュ化の方法を真似しています。
これによって、衝突しづらくなるようです。
これでひとまず、pair型などをキーにできるようになりました。
自作クラスに()を定義してその中でハッシュ内容を作ってそれを
unordered_mapの第三要素に指定すればよいです！うれしい。
注意 constが要ります
上記の実装についてですが、HashPairの()演算子の関数の最後にconstがついています。
struct HashPair {
//注意 constがいる
template<class T1, class T2>
size_t operator()(const pair<T1, T2> &p) const {
}
};
このconstは、constメンバ関数にするためのconstです。
constメンバ関数とは、その関数によって、インスタンスのメンバが変更されないことを保証する！という関数になります。
constをつけることによって、どう頑張ってもインスタンスのメンバの値を変更することができません。
これによって、内部のメンバの値が操作されないことが保証されるため、安全に副作用なく関数を使用することができます。
HashPairの()演算子オーバーロードは、ハッシュ値を返しますが、できればメンバの値を変更したくなりません。
もし、メンバの値を変更したときに、同じ入力に対して、異なるハッシュ値が出てきてほしくないためです。
よって、constをつけないとエラーが出るようになっています。
Hackの危険性
しかし、このままだと競技プログラミングだと使いづらくなってしまいます。
Codeforcesという競技プログラミングコンテストサイトでは、コンテスト終了後にHacking Phaseというものが存在します。
これは、攻撃者が問題のテストケースをユーザが自作して、他の人のソースコードプログラムにそのテストケースを与えて、テストケースに対して正しい答えを求めることができなければ、攻撃者が点をもらえて、攻撃された側が点を失ってしまう、というルールです。
unordered_mapをコンテストで使用すると、多少の確率で海外競技プログラマーに、攻撃されることがあります。
なぜなら、そのままのunordered_mapを使用すると、キーのハッシュが衝突しやすい入力テストケースを作ることができるため、実行時間が超過してしまい、攻撃に成功されて、自分の点数が失われて、相手に点を取られてしまいます。
このようにunordered_mapはキーのハッシュが衝突すると、非常に遅くなりTLEしてしまうため、改善が必要です。
実装（真）
キーのハッシュが衝突するような攻撃を避けるために、実行時のランダム要素を取り入れます。
struct HashPair {
static size_t m_hash_pair_random;
template<class T1, class T2>
size_t operator()(const pair<T1, T2> &p) const {
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
size_t seed = 0;
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= m_hash_pair_random + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
size_t HashPair::m_hash_pair_random = (size_t) random_device()();
int main() {
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
mp[make_pair(i, j)] = i + j;
}
}
}
以上のようにしてみます。
HashPairクラスに、実行する現実時間によって値がランダムに変化する値を入れる
m_hash_pair_randomなどの変数を用意します。
static変数なので、クラスの外側でrandom_device()()でランダム値を取り入れます。
これによって、毎回異なる値のハッシュを作れるため、攻撃されることがかなり低くなると思います。
検証
計算速度を計測して性能を見てみます。
計測するに使用するクラスは
class ProcessingTime {
public:
ProcessingTime(const std::string &name = "Process", bool start = true) :
m_name(name),
m_isActive(start) {
if (start) {
this->restart();
}
}
~ProcessingTime() {
this->stop();
}
///<summary>
///計測のリスタート
///</summary>
void restart() &{
m_start = std::chrono::system_clock::now();
m_isActive = true;
}
///<summary>
///計測を終了し出力
///</summary>
void stop() &{
if (!m_isActive)
return;
const auto end = std::chrono::system_clock::now();
const auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - m_start).count();
std::cout << elapsed << "ms" << std::endl;
m_isActive = false;
}
private:
std::string m_name;
std::chrono::system_clock::time_point m_start;
bool m_isActive;
};
でこちらの記事からお借りしました。
ありがとうございます！
以下のように実行時間をチェックしました。
class ProcessingTime {
public:
ProcessingTime(const std::string &name = "Process", bool start = true) :
m_name(name),
m_isActive(start) {
if (start) {
this->restart();
}
}
~ProcessingTime() {
this->stop();
}
///<summary>
///計測のリスタート
///</summary>
void restart() &{
m_start = std::chrono::system_clock::now();
m_isActive = true;
}
///<summary>
///計測を終了し出力
///</summary>
void stop() &{
if (!m_isActive)
return;
const auto end = std::chrono::system_clock::now();
const auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - m_start).count();
std::cout << elapsed << "ms" << std::endl;
m_isActive = false;
}
private:
std::string m_name;
std::chrono::system_clock::time_point m_start;
bool m_isActive;
};
struct HashPair {
static size_t m_hash_pair_random;
template<class T1, class T2>
size_t operator()(const pair<T1, T2> &p) const {
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
size_t seed = 0;
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= m_hash_pair_random + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
size_t HashPair::m_hash_pair_random = (size_t) random_device()();
int main() {
{
ProcessingTime time("unordered");
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i <= 4000; i++) {
for (int j = 0; j <= 4000; j++) {
mp[make_pair(i, j)] += i + j;
}
}
}
//32838ms
{
ProcessingTime time("map");
map<pair<int, int>, int> mp;
for (int i = 0; i <= 4000; i++) {
for (int j = 0; j <= 4000; j++) {
mp[make_pair(i, j)] += i + j;
}
}
}
//26552ms
}
unordered_mapだと32838ms, mapだと26552msでした！
あれ、おかしいですね...
unordered_mapのほうが著しく遅いですが...
int main() {
{
ProcessingTime time("unordered");
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i <= 1000; i++) {
for (int j = 0; j <= 1000; j++) {
mp[make_pair(i, j)] += i + j;
}
}
}
//1062ms
{
ProcessingTime time("map");
map<pair<int, int>, int> mp;
for (int i = 0; i <= 1000; i++) {
for (int j = 0; j <= 1000; j++) {
mp[make_pair(i, j)] += i + j;
}
}
}
//1427ms
}
要素数を減らしてみました。
このようにすると、unordered_mapのほうが早いです。
やはり、要素数が多すぎると衝突回数が増えて、著しくunordered_mapのほうが遅くなってしまうようです。
int main() {
{
ProcessingTime time("unordered");
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 1000; j++) {
mp[make_pair(i, j)] += i + j;
}
}
}
//76ms
{
ProcessingTime time("map");
map<pair<int, int>, int> mp;
for (int i = 0; i <= 100; i++) {
for (int j = 0; j <= 1000; j++) {
mp[make_pair(i, j)] += i + j;
}
}
}
//126ms
{
ProcessingTime time("unordered");
unordered_map<int, int> mp;
for (int i = 0; i <= 100000; i++) {
mp[i] = i;
}
}
//42ms
{
ProcessingTime time("map");
map<int, int> mp;
for (int i = 0; i <= 100000; i++) {
mp[i] = i;
}
}
//172ms
}
一応int型も試してみました。
ただ、ランダムアクセスをしていないのでこのような結果になっているのかな、という感覚もします。
int main() {
mt19937 mt;
uniform_int_distribution<int> dist(1, 1000000000);
{
ProcessingTime time("unordered");
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i < 100000; i++) {
mp[make_pair(dist(mt), dist(mt))] = i;
}
}
//106ms
{
ProcessingTime time("map");
map<pair<int, int>, int> mp;
for (int i = 0; i < 100000; i++) {
mp[make_pair(dist(mt), dist(mt))] = i;
}
}
//126ms
{
ProcessingTime time("unordered");
unordered_map<int, int> mp;
for (int i = 0; i < 100000; i++) {
mp[dist(mt)] = i;
}
}
//73ms
{
ProcessingTime time("map");
map<int, int> mp;
for (int i = 0; i < 100000; i++) {
mp[dist(mt)] = i;
}
}
//101ms
}
使用する値をランダムにしてみました。
あんまり変わりませんが、やはり要素が少なければunorderedのほうが早いですね
int main() {
mt19937 mt;
uniform_int_distribution<int> dist(1, 1000000000);
{
ProcessingTime time("unordered");
unordered_map<pair<int, int>, int, HashPair> mp;
for (int i = 0; i < 10000000; i++) {
mp[make_pair(dist(mt), dist(mt))] = i;
}
}
//14699ms
{
ProcessingTime time("map");
map<pair<int, int>, int> mp;
for (int i = 0; i < 10000000; i++) {
mp[make_pair(dist(mt), dist(mt))] = i;
}
}
//26235ms
{
ProcessingTime time("unordered");
unordered_map<int, int> mp;
for (int i = 0; i < 10000000; i++) {
mp[dist(mt)] = i;
}
}
//12549ms
{
ProcessingTime time("map");
map<int, int> mp;
for (int i = 0; i < 10000000; i++) {
mp[dist(mt)] = i;
}
}
//22564ms
}
ランダムアクセスかつ、アクセス回数を$10^7$に増やしました。
ランダムなら、unordered_mapも衝突しないのか、mapよりも早いですね。
采配が難しい気がします。
まとめ
僕のunordered_mapちゃんはなんとか、pair型をキーにできたようです。
桐乃は本当に可愛いなぁと思います。
C++などプログラミング言語を理解していないため、ぜひアドバイスやご指摘のコメントをいただければとありがたいです！
参考にさせていただいたサイト
第28回目 staticメンバ、および、クラス外でメンバを定義する
手を動かしてさくさく理解する
C++ ハッシュ連想配列クラス unordered_map 入門
C++日本語リファレンス
techiedelight
std::unordered_setはデフォルトではpairが使えない
error for hash function of pair of ints
うさぎ小屋 std::unordered_mapのhash衝突による速度低下をさせてみる
ぬの部屋 C++のunordered_mapで自作クラスを使う (主にハッシュ値生成について)
C++ 処理時間計測classを作ってみる