う え き ぷ に き あ く ん 笑 Advent Calendar 2021 4日目です
環境
AtCoderコードテスト
Python 3.8.2
PyPy 3.7.0
Cython 0.29.16
この記事について
競技プログラミングをPython3でやっている際にTLE, MLEが出たときの対処法を、あまり見かけない情報に絞って書き連ねていきます。※計算量改善ではなく、定数倍高速化についての記事です
本記事内でのそれぞれの言語のバージョンは、「環境」で示したものとし、以降バージョンは省略させていただきます。
本記事内では、「環境」で示した3つの言語の総称として"3言語"という言葉を使用いたします。
実行は全てAtCoderコードテストで行っています。
細かい仕様などに触れた記事ではありません。チートシートの様な使い方をしていただけたら幸いです、
3言語のうちどれを使えばいいのか？
この3言語は、それぞれ特徴があります。この後にある程度の紹介・比較はしますが、基本的にはPyPyを使用することをお勧めいたします。
PyPyの特徴
ではまず、PyPyの特徴について大まかに説明させていただきます。
メリット
・動作が速い
デメリット
・メモリの使用量が多い
・再帰の動作が遅い
わかりやすいですね。
Cythonの特徴
次はCythonです。（ちなみに読み方はサイソンらしいです。非自明すぎる...）
メリット
・最適化を突き詰めれば動作がとても速い
・再帰の動作が速い
・省メモリ
デメリット
・最適化をしないと速度は普通
・PyPyの方が簡潔なので、基本的にPyPyでいい（デメリットか？これ）
となっています。
ループを回してみる
実際のコードを実行した際の実行速度及びメモリ使用量は以下の通りです。それぞれ、whileは10^8回、再帰関数は10^6回のループとなります。
単純なwhileループ（10^8）
i = 0
while i < 10**8:
i += 1
このコードをは以下の通りです（上位2桁以降は丸めています）。
Python:6600ms, 2900KB
PyPy :200ms, 28000KB
Cython:5300ms, 6900KB
やはりPyPyはとても速く、とてもメモリを使っています。
ABC189-C Mandarin Orange など、O(N^2)解法がPyPy以外では通らない場合があります。
再帰関数（10^6）
import sys
sys.setrecursionlimit(10**7)
def f(x):
if x == 10**6:
return
f(x+1)
f(0)
Python:650ms, 830000KB
PyPy :1300ms, 980000KB
Cython:160ms, 150000KB
PyPyとCythonの差は歴然です。
記事のネタバレになってしまいますが、再帰関数でTLEやMLEが出た場合はCythonに変えると通ることが多いです。
再帰関数で引っかかる場合
Cythonで提出し直しましょう おわり
boolを使わない（PyPyの場合）
3言語の内PyPyに限り、bool型の動作が遅いです。
flag = False
for i in range(10**8):
if flag:
flag = False
else:
flag = True
PyPy:780ms, 26000KB
代わりにint（0, 1）で表すと
flag = 0
for i in range(10**8):
if flag:
flag = 0
else:
flag = 1
PyPy:290ms, 26000KB
かなり違います。
分岐が重いわけではなく、値の書き換えが重いようです。
ABC182-E AkariなどでTLEになる可能性があります。
リストではなくsetなどで代替する
制約的にありうる状態全てのリストを用意すると、MLEになることがあります。setやdictで値を管理しましょう。
例えば、次のような問題のときです。
長さNのリストA, 長さMのリストBが与えられる。 全てのA_i(1 ≤ i ≤ N)について、以下の動作を行う。
・全てのB_j(1 ≤ j ≤ M)について、A_i + B_jを計算し、紙に書く
全ての動作を終えたとき、紙に書かれた数は何種類あるか出力してください。
1 ≤ N, M ≤ 1000
1 ≤ A_i, B_j ≤ 10^9
この問題について、A_i + B_jとしてありうる数値は2 ~ 2*10^9であり、種類の数はおよそ2*10^9です。 この全てについて、出現したかどうかのフラグを管理する長さ≒2*10^9のリストを作ると、MLEとなってしまいます。また、仮にリストの長さがMLEにならない10^8で足りるとしても、単純にリストの用意で500msほどかかってしまい、問題によってはACすることが難しくなってしまいます。
この解決法として、setやdictを使うことがあります。出現した数や状態のみを追加することで、メモリを節約できます。ある数や状態xがすでに出現したかどうかは、x in [set]などでO(1)で調べられます。
実際、この問題では高々10^6種類の数しか出現しないため、MLEにはなりません。
ABC224-D 8 Puzzle on Graphのような問題も該当します。
自作ライブラリが遅い！
代替できる標準ライブラリがある場合、大抵はそちらの方が実装含め速いです。
二分探索 → bisect
ヒープ → collections.heapq
順列 → itertools.permutations
gcd → math.gcd
階乗 → math.factorial
などは頻出です。
また、繰り返し二乗法 → pow などもあり、3言語中、PythonとCythonではmod逆元もpow関数で行うことができます。
queueが遅い！
dequeを使いましょう queueはdequeを用いて実装されているらしく、dequeの方が速いようです。（ぼくは調べれていないので、責任は取りかねます）（最悪）
リストにtupleを入れると遅い！
ダイクストラなどで(cost, t)のようなtupleをそのままheapq（リスト）に入れると間に合わないことがあります。このとき、intで代用することができ、そちらの方が速いです。
上記の例だと、t < kを満たす定数kをあらかじめ決めておくことで、以下のコードで実現できます。
def pack(cost, t, k):
return cost*k + t
def unpack(v, k):
return (v//k, v%k)
print(pack(1000, 10, 100))
# 100010
print(unpack(100010, 100))
# (1000, 10)
また、長さ3以上のtupleも、kをすべての要素より大きい値に設定し、i番目の要素に対してk^iを掛けた合計をreturnすることで同様にintにすることができますが（unpackは逆の手順を踏む）、packの結果が64bitに収まる範囲でないと遅くなってしまう点や、復元の作業も必要なため、長いtupleにはあまり適しません（基本的には3以上は遅くなります）。
ZONeエナジー プログラミングコンテスト “HELLO SPACE”-E 潜入などではほぼ必須テクです。
最後に
このように、TLEやMLEが起きてしまう要因は思わぬところにあります。Pythonで競技プログラミングをするなら、こういった定数倍高速化に欠かせない要素は覚えていきたいですね。
明日のアドベントカレンダーの担当はうえきさんです。