×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
ABC146 D Coloring Edges on Treeより
64bit環境ならsize_tも64bitのはずなので、int型2つ並べるだけで衝突は起きないはずだが、より汎用的にするためにboost::hash_combineを真似た。
2つの値をkeyにして値を取り出したいことは割と多い。
mapで計算量が間に合うならそれでも良いが、想定解法とは違うがC++パワーでunordered_mapを使えば間に合うなんてことがあるかもしれない。
そのためにpairのハッシュ関数を作成した。
namespace std {
template struct hash<pair<A, B>> {
size_t operator()(const pair<A, B> &p) const {
const static size_t rand_seed = random_device()() + 0x9e3779b9;
size_t seed = rand_seed;
seed ^= hash()(p.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash()(p.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
}
64bit環境ならsize_tも64bitのはずなので、int型2つ並べるだけで衝突は起きないはずだが、より汎用的にするためにboost::hash_combineを真似た。
テンプレートの特殊化の本来の目的に沿うとpair<int, int>を別に指定するべきなのだろうが、普通に面倒である。
このハッシュ関数をテンプレート入りさせようかなと考えているし、32bit環境のオンラインジャッジもあるかもしれないので、汎用性 is 正義である。
速度的にもintを2つ並べる場合とほとんど変わらない。
数回程度の試行だが、5ms程度しか違いがなく、ハッシュが衝突したのかジャッジシステムの誤差なのか分からないレベルなので問題なく動作しているだろう。(ABC146 D Coloring Edges on Treeで測定)
一応動くようにはなったのだが、方向性を参考にした記事と見比べてみると乱数の使い方が違う。
参考にした記事では、初期seedを0とし、pair要素のhash値と同様にseedをシフトしたものと足し合わせている。
pairの値によって定まる部分を定数とおくと、こちらはseedをシフトして足し合わせる回数が少ないのと、足し合わせる順番が最初になっただけなので、記事の方法でランダム性が確保されるなら初期値を乱数にするだけでも良さそうな気がするのだが、正直全く分からない。
偉い人に教えてもらいたい。
PR
コメント