読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

競技プログラミングにおけるstd::unordered_***

実装メモ

はい.
タイトルの通り,unordered_set,unordered_mapについてです.
これらはset,mapを平衡二分探索木ではなく,ハッシュと連結リストによって実装することにより平均アクセス速度を定数に抑えています.

ただし,悪意のある入力を除いて,です.

一部のプログラミングコンテストtopcoder,codeforces)には他人のコードを撃墜できるフェーズがあります.

例えば10^5個の整数を受け取る問題があったとします.
受け取った整数を全てunordered_setに格納したらどうなるでしょうか.

通常ならば入力サイズに比例した時間で処理が終了します.
しかし,unordered_setの最悪時の一回のアクセスの計算量はO(N)です.
hackにて全挿入にO(N)かかるようなケースが投げられた場合,TLEしてしまいます.

実際unoredered_mapを狙い撃ちするようなhackがCF350(div2)C問題で行われました.
http://codeforces.com/contest/670/problem/C
チャレンジに成功したケースはシステムテストのテストケースに追加されるようになっているので,unordered_mapを使った人はシステムテストであえなく落ちる結果になりました.

これを回避する方法については,以下が挙げられます

  • unordered系を使わない(set,mapで対処する)
  • 独自のhash関数を使う
  • 初期バケツサイズを変える(後述)
  • 挿入する値のxorをとる(後述)

下二つについて解説します.
そもそもunordered_***は内部は複数のバケツと呼ばれる連結リストで構成されています.
で,ローカルで適当に試してみた結果,恐らくですが挿入される値がどこに保持されるかは値をバケツサイズで割った余りになるようです.
(本当にそうだと流石に適当すぎると思うので間違ってると信じてます.詳しい方教えてください)
なので,現在のバケツサイズの倍数をひたすら挿入していくようなケースを作るだけで毎回のアクセスが重くなる(はず)です
(実際そのようなケースで10^5の入力を与えたらsetの400倍の時間がかかりました.)

なので,重要なのはmodの値をずらしてやることになります.

で,その一つの方法が初期バケツサイズを変えることになります.
ハッシュリストの負荷率が規定値を超えた場合バケツサイズの変更,リストの再構成が行われます.
正直バケツサイズの増え方があんまりよくわかってないんですが,大体2倍+1の大きさになる?ようです
デフォルトの初期バケツの大きさが2なので,これを3とかに変えてやるだけでほとんどのmodの値がずれるようになると思います.

もう一つの方法が挿入する値のxorをとることです.
(@climpetさんのツイートを参考にしました)
xor演算には暗号化,復号化が同じ鍵,同じ演算でできるという性質があり,高速に行えます.
↑修正後のコードではhashに暗号化を使っているだけで復号化は使っていません
xorを取った値はかなりmodの数がズレるはずなので,有効なはずです.

上記二つの対策を施したhashの実装が以下になります.

namespace myhash{
    const int Bsizes[]={3,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81};// num=20
    const int xor_nums[]={0x100007d1,0x5ff049c9,0x14560859,0x07087fef,0x3e277d49,0x4dba1f17,0x709c5988,0x05904258,0x1aa71872,0x238819b3,0x7b002bb7,0x1cf91302,0x0012290a,0x1083576b,0x76473e49,0x3d86295b,0x20536814,0x08634f4d,0x115405e8,0x0e6359f2};
    const int hash_key=xor_nums[rand()%20];
    template <typename T>
    struct myhash{
        std::size_t operator()(const T& val) const {
            return val^hash_key;
        }
    };
};
template <typename T>
class myhash_set:public std::unordered_set<T,myhash::myhash<T>> {
    using SET=std::unordered_set<T,myhash::myhash<T>>;
public:
    myhash_set():SET(){SET::rehash(myhash::Bsizes[rand()%20]);}
};
template <typename T,typename U>
class myhash_map:public std::unordered_map<T,U,myhash::myhash<T>> {
public:
    using MAP=std::unordered_map<T,U,myhash::myhash<T>>;
    myhash_map():MAP(){MAP::rehash(myhash::Bsizes[rand()%20]);}
};

上部にある配列が事前に用意した初期バケツサイズの候補,xor値の候補です(適当すぎて失敗すると困るので)
これらのどれかを乱数で決めて使います.
注意点として,range based forなどでアクセスするときには暗号化された値が帰ってくるのでgetoriginを利用して復号化する必要があります.

流石にコードが酷かったので修正しました(5/22)
hash関数でxorをとるようにしました.
やっぱりなんですけど,デフォルト実装だとキーの値をバケツの数でmodをとるクソシンプル(よくない)実装みたいです.
詳しい話は@zeosuttさんのこちらの問題の解説にも書いてあるので参考にしてみるといいと思います.
http://yukicoder.me/problems/1148