Pythonのdict()が特定の入力に対し非常に遅い件について

初めに

これは競技プログラミングのために書かれた記事です。あくまでも特定の恣意的な入力に対し起こることであり、現実世界のデータを扱う際にこの事象が問題になることはほとんどないと思います。

この記事は、Codeforces Round #790 (Div. 4) の F 問題 で Python / PyPy による提出のほとんどすべてが Hack されたのをきっかけとして書かれました。
間違い等あれば気軽にコメントしていただけると助かります。

前提知識

Python の dict について

Python の dict は、以下のようなコンテナ（データを収納するための構造）です。

• 整数や文字列、タプル等の hashable なオブジェクトを key として、それぞれに value を割り当てることができる。（value は key と異なり任意のオブジェクトが格納可能。例えば配列を value とすることもできる。） key を指定して、 value が割り当てられているか判定したり value の値を求めたりできる。

今回は、key は非負整数であるものとします。

dict の内部挙動

value は結局のところ dict の中にある配列に格納されます。 key と配列の添え字とを何らかの規則に基づいて関連付けることで、 key から高速に value を求めることが可能になるというわけです。

dict に $(key, value)$ のペアが与えられた時、以下のようなアルゴリズムで対応する添え字を決定します。:

1. ある関数 $f$ を用いて、 $f(key)$ を求める。
2. もしまだ配列の $f(key)$ 番目に何も割り当てられていないなら、 $f(key)$ に $value$ を収納して、終了
3. もし $f(key)$ にすでに割り当てられているものがあるなら、 $key \leftarrow f(key)$ として、1.に戻る。

Python の dict における Hashing

dict 内の配列の長さを $size$ 、最初の hash（入力された key です）を $x_0$ とすると、 $x_{i + 1} = f(x_i)$ で 定める $x_{i + 1}$ は以下のようになります。

x_{i + 1} = f(x_i) = \left(5x_{i} + 1 + \left\lfloor\frac{x_0}{32^i} \right\rfloor\right) \mod size

つまり、 dict に $key = x_0$ を指定したとき、内部では $(x_0, x_1, x_2, x_3, x_4, \dots)$ を前から順に計算して確認し、空いてるか確認する、という挙動をします。そのため、あらかじめこれらの番地を順番に埋めてしまえば、 $key$ を呼ぶたびに大量の $f(x)$ の計算を行うことになり実行時間が非常に遅くなります。よって、$x$ を順番に dict に入れさせ、その後 $x_0$ を呼び出しまくるような入力を与えれば、Python の dict に対する hack ケースになるというわけです。

具体例

Python dicthack.py

size = 2 ** 32
d = {}
d[size + 1] = 1
x = 6
for i in range(2 * 10 ** 5):
    d[x] = 1
    x = 5 * x + 1
    x %= size

for i in range(2 * 10 ** 5):
    d[1] = 1

print("Done")

このシンプルなプログラムをAtCoderのコードテスト(PyPy3)で実行すると、10秒の制限時間を超過します。普通 dict の処理は $O(1)$ であると考えられているので、かなり意外な結果に感じられます。また、dict に対する hackケースは AtCoderでもあり得そうな範囲の大きさで、また生成が簡単なケースであることもわかると思います。

【5/13 追記】set に対する　hack ケースを見つけました。

python sethack.py

size = 2 ** 32
s = set()

for j in range(10):
    s.add(size + 1 + j)
x = 6
for i in range(10 ** 6):
    for j in range(10):
        s.add(x + j)
    x = 5 * x + 1
    x %= size

for i in range(10 ** 5):
    1 in s

print("Done")

$10^7$ 程度のループで set に数値を加えていくプログラムです。 AtCoder コードテストで実行すると、10 秒の時間制限を超過しました。

set については、 10 個程度の hash を並列してチェックしているそうですが、詳しい仕様や条件についてはよくわかっていません。わかる方いれば教えてください。

他のコンテナについて

defaultdict や Counter は dict のサブクラスとして実装されているため、同様の問題はこれらでも発生します。

対処法

上で述べたような仕組みはハッシュテーブルというデータ構造で、他に C++ の unordered_map やJava の HashMap が同様の構造をしています。よって、これらで起こる問題と同様のものが Python の dict でも起こりうるというわけです。
Codeforces において C++ の unordered_map をそのまま使うことは推奨されません。（ほぼ確実に Hack されるため）今までは Python の dict に対する Hack ケースは C++ のそれに比べ知名度が低かったですが、今後情報が広まるにつれて対策の必要が生じてきます。

C++ と違ってPython には任意の hashing を設定する方法がないので、 dict 単体をいじることでどうにかすることはできません。

要は「特定の数が特定の順番で埋まっていく」ことに問題があるので、それを防げればよいです。あらかじめ入力をソートする、入力に適当な数で xor をする（後で戻す）などの対処法があるでしょう。自作の hash 関数を作って、dict に入れる時にそれを噛ませるようにしてもいいです。

参考文献

• Anti-hash-table test in Python この記事はほとんどここを参考にして書きました。

• Python の dict の実装詳解 関数 $f$ の挙動を調べました。