Pythonで競プロをしよう！〜入門者が知っておくべきTips〜
こんにちは、Finatextグループのナウキャストでデータエンジニアをしているけびん( Twitter: @Kevinrobot34, AtCoder: Kevinrobot34 )です。先日、PyCon JP 2020で、「Pythonで競プロをしよう！ 〜入門者が知っておくべき高速化Tips〜」という題名で発表をさせていただきました。発表時のスライドと動画はこちらです。
この内容について、少し加筆してまとめようと思います。
はじめに
最近AtCoderを中心に、競技プログラミングの人気が高まっています。 C++で参加している人が最も多いですが、Pythonで参加している人もかなり増えています。 Pythonは書きやすい一方でC++と比べてしまうと実行速度が遅く、Logicは正しくてもPythonだとTLE(Time Limited Exceeded, 時間超過)してしまうことも少なくありません。 しかし実際にはPythonでも高速化が可能で、ほぼ全ての問題がPython(/PyPy)でAC(Accepted, 正解)することができると知られています。
このブログでは、競プロとPythonの基本的な部分は知っている人をメインターゲットに、実際にPythonで競技プログラミングをする際に把握しておくべき様々なTipsを紹介します。
紹介することは
- Pythonで競プロをする上で高速化のために気をつけた方が良い書き方
- PyPyを用いた高速化
- よくあるエラーの対処
で、紹介しないことは
- numpyやnumbaを用いた高速化
になります。numpyやnumbaを用いた高速化も強力な手法なので、気になる人は是非調べてみてください。
高速化関連
標準入力
inputとsys.stdin.readline
組み込み関数のinput()を使って標準入力を読み込むのは遅いです。
データ数nがはじめに与えられ、それからn行にわたって整数が入力される場合を考えましょう。
次のように sys.stdin.readline を使った方が早いです。
それぞれn=10**6の場合で速度を計測すると次のようになります
基本的なデータ構造の計算量
Listl を長さ n のListとします。
- ランダムアクセスはO(1) （といいつつ重いので、避けられるなら避けた方が良いです（後述））
- appendや末尾のpopは早いですが、末尾以外へのinsertやpopは遅いです
- 先頭への要素の追加・削除をしたい場合は後述のdequeを使いましょう
- inやmin、maxといった操作は直感的に短く書くことができ便利ですが、O(n)なので注意が必要です
- inを多用したい場合などは次節のset/dictを使いましょう
SetとDictsをset、dをdictとします。
- SetとDictはハッシュテーブルというデータ構造です
- C++の平衡二分探索木のSetとは全く別物です！！
- Listと違いinが早いです
少し話はそれますが、collections.defaultdictというものもあります。デフォルト値を設定できるdictみたいなやつです。これ使うと少しコードが綺麗になることがあります。
deque
double-ended queueのことで、StackとQueue両者の役割をこなせるデータ構造です。詳細はcollections.dequeを見てください。配列の先頭と末尾のpopやappendは早いですが、真ん中の要素へアクセスしようとすると遅いです。
先頭へのpop/appendが必要であればdeque、ランダムアクセスが頻繁に必要であればListを使うことを考えましょう。
Listの効率的な使い方
indexによるアクセスは遅い
次のように長さnのList aを用意して、for文でループしてアクセスすることを考えます。
for文の書き方としては以下の3つがぱっと考えられます。
はじめのa[i]のようなindexを使ったアクセスは遅いことが知られています。実際上記3つの実行速度を比較してみましょう。
このようにindexを使わずにfor文を書くとかなり早くなります。
indexが必要な場合には`enumerate`を使った書き方もアリです。
また、Indexでアクセスして値を書き込むのは更に遅いので注意が必要です。ABC142 E: Get Everything (500点) の以下のコードを例として見てみましょう。いわゆるbit DPの問題です。
アルゴリズムの詳細には立ち入らないですが、dpという長いlistを更新していくだけのコードです。15,16行目で実際にList dpを更新しています。
このコードの15,16行目とコメントアウトされている17行目は本質的には等価です。しかし17行目の方は毎回Listに値を書き込むことになるため非常に遅いです。
実際にそれぞれ利用したコードを提出して実行速度を比較すると以下のようになります。
このようにかなり速度が変わることが確認できます。Listへの不必要な書き込みがないか注意しながら書いてみましょう。
ListのListのソートにはoperator.itemgetter
ListのList（二次元配列）のソートは遅いですが、keyの指定の仕方で高速化できます。次のようなListを考えてみましょう。
これを2番目の要素(Listのインデックスとしては1)でソートすることを考えます。一番シンプルなkeyの指定方法はlamdba式を使って書くことだと思いますが、operator.itemgetterを使うと見やすくかつ早くなります。
実際速度を比較すると、以下の通りです。
List内の要素が文字列であったりすると更にsortは重くなるので、itemgetterを使っておくと無難です。
local変数を利用した高速化
Pythonではグローバル変数にアクセスするよりもローカル変数にアクセスする方が早いことが知られています。この性質により全ての処理をmain()などの関数に入れておくだけでも高速化が見込めます。
先程のABC142Eのコードを例にしてみましょう。以下のようにmain関数内に処理を書いておきます。
これを提出してみると実行時間はそれぞれ以下のようになります。
def main():と if __name__ == '__main__': の部分はテンプレートにしておいても良いかもしれません。
PyPyによる高速化
PyPyとは
PyPyとはPythonの実装の一つです。安定なJIT(=Just In Time)コンパイラで、CPythonよりも高速に動作します。Numpyなどのライブラリは使えませんが、ほぼ全てのPythonの組み込みモジュールが提供されています。
競技プログラミングでは基本的な制御構文とデータ構造を組み合わせてコードを書くことが多いと思うので、Pythonで書いたコードをそのまま何もせずPyPyとして提出するだけで速度がかなり上がることが多いです。
現在AtCoderで提供されているPyPy3 (7.3.0)はPython3.6.9と互換性のあるものになります。
Install方法
pyenvがおすすめです。pyenvはPythonのバージョン管理や仮想環境の管理をサポートしてくれるツールです。
このように簡単に指定したバージョンのインストールが可能です。
バージョンの切り替えも以下のように簡単にできます。
使い方の詳細についてはpyenvのGithubをご覧ください！
Pythonとの比較
AtCoderのEDPC B: Frog 2という動的計画法の問題を例にPythonとPyPyの比較をしてみましょう。以下のような実質二重ループのコードをPythonとPyPyの両方で提出してみます。
このように全く同じコードでも、PyPyとして実行するだけでかなり高速化されることが確認できます。
今回の問題ではPython3でもACすることができましたが、より厳しい制約の場合PyPy3しかACできないことも考えられます。
PyPyだと遅い処理
PyPyだと遅い処理もいくつか知られています。
- 再帰関数を用いた処理
- 文字列に関連した処理
- tupleの比較を含むような処理 （sort, heapqなど）
とりあえずlocal環境やAtCoderのコードテストで実行時間をPythonとPyPyで比較し、早い方の言語で提出するのが良いと思います。
よくあるエラー
RecursionError
競プロをしていると再帰関数で処理を書くことがよくありますが、再帰できる回数には上限が決められています。以下で現状の上限値は確認できます。
AtCoderのPython3.8だと上記は1000になっており、あっという間に上限に達してしまい、RE(=Runtime Error)となることがあります。
再起関数を使った処理をする場合には以下のように上限を操作をしておきましょう。
整数と浮動小数点
この話自体はPythonに限らないですが、Pythonは動的型付けの言語であり型のことを深く考えなくてもコードを書けてしまうので、数値の扱いには注意が必要です。例えばある変数が初めは整数を扱っていても、途中で除算(/)をすると浮動小数点（大抵C言語のdoubleを使って実装されている）に変換されてしまいます。割り切れるような場合でも/は浮動小数点を返します。
このように浮動小数点での計算には誤差が発生するので、原理的に全て整数で計算でき出力も整数な問題の場合、途中の計算処理は切り捨て除算//を使い整数で計算しておく方が良いです。
おわりに
僕の所属するFinatextグループでは様々な事業を展開しており、いろいろな領域のエンジニアを募集しております！是非興味がある方は採用ページへアクセスいただくか、@Kevinrobot34まで直接ご連絡ください！
参考文献
- https://github.com/Kevinrobot34/cp_python_tips : 今回のブログ執筆に使ったコード置き場です。
- https://wiki.python.org/moin/TimeComplexity
- ハイパフォーマンスPython
- Effective Python
