Pythonが遅いときにPyPyを使うと救われることがある話 (AtCoder)

日紀

AtCoderのAtCoder Beginner Contest 189 (ABC189)に参加して、C問題でつまづいたのでメモ。私はふだんPythonを日常生活で使っており、AtCoderのコンテストもPythonを使って参加している。一方で、ピュアなPythonは遅いことがよく知られている。果たしてPythonが遅いことで不利益を被ることがあるだろうか？

日常生活ではPythonが遅いことで直接不利益を被ることはあまりない。数値計算をするときにはピュアなPythonではなくNumpy, Scipyを使うことが多く、十分な速度が得られる。また、日常生活ではたとえばC++だと0.1秒だがPythonだと3秒かかるみたいな場合も、たった3秒なら待てばいいだけなので問題がない（この計算を10000回回す必要がある、とかなってくると話は別）。

しかし、競技プログラミングで時間制限が厳しい場合はピュアなPythonによる実装によってはじかれる場合がある。今回、ABC189のC問題は、制限時間が1.5秒だった。コンテスト中にPythonで書いたコードをPython3として提出したが、TLE (Time Limit Exceeded, 実行時間超過)になった。計算量的にはO(N2)でNが最大で104なのでいけるんじゃないかなと思ってたので意外だった。やっぱりO(N)の解法があるのかなあとか考えていたらコンテストは終わった。

コンテスト終了後に公式解説を読んでみたら、自分がやった実装とほぼ同じ回答でいけると書いてあった。つまり、アルゴリズムはよかったが、Pythonが遅いせいで正答にならなかったパターンである。非常に不満だった（アルゴリズムを競いたい）が、他の人の回答を眺めていたらPyPyで提出している人を見つけた。

PyPyはPythonによるPythonの処理系である。基本的にピュアなPythonより高速で動くことが知られている。ふだんはライブラリが対応してないことや、ピュアなPythonで遅くても多少待ってればいいこと、Numpyを使うことなどがあるのでPyPyを使わない。一方、AtCoderでは提出言語でPyPyを選ぶことができる。

試しに、コンテストが終わった後、PythonではじかれたコードをPyPyで提出してみた。そうしたら通った。それが下記。

Image
全く同じコードをコピペして実行した結果

全く同じコードをコピペしてこの結果である。これを考えると、AtCoderでPythonでコードを書いたとしても、とりあえずPyPyのコードとして提出することで救われる場合があることがわかる。Pythonだと主要な言語であるC++とかに対して速度面で不利になることがあるが、PyPyを使うことでそのハンデを克服することができる。これは面白い発見だった。

Twitterで調べてみると、同じようにPythonが遅いことではまった人や、同じようにPyPyを使うことで何とかなった人がたくさん出てくる（下記）。今度からはPyPyでもよさそうな場合はPyPyで提出することにしよう。

コメント