[[Python 競プロ用 Tips]]
現在位置: トップページ » アルゴリズム » Python 競プロ用 Tips
文書の表示
管理サイトマップ

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:python_tips [2020/07/01] – [事前コンパイル] ikatakosprogramming_algorithm:python_tips [2020/09/07] – ikatakos
行 251: 行 251:
 多くの競プロサイトはNumbaは使えないことが多いが、AtCoderは2020/04より使えるようになった。 多くの競プロサイトはNumbaは使えないことが多いが、AtCoderは2020/04より使えるようになった。
  
-競プロの文脈でポイントとなるのは、以下だろう。+そもそも、Pythonはお手軽に書けるのが一つの利点であり、 
 +使える関数やデータ型が限定されるNumbaに書き換えてまで 
 +Pythonにこだわる意味があるのか、というのはある。\\ 
 +AtCoder以外では今のところ使えないし、複雑な処理ではコンパイル可能なコードにするのが難しいこともある。 
 + 
 +そうは言っても、メイン言語がPythonの人にとって、1から%%C++%%などで書きなおす以外にPythonで通せる幅が広がったのは歓迎すべきことだ。 
 + 
 + 
 +Numbaの中でも使い方は複数あるが、競プロの文脈でポイントとなるのは、以下だろう。
  
-  * 高速化のため、NoPythonモード、事前コンパイル+  * 「実行時間」を短くしたい 
 +    * 高速化の恩恵の大きい "NoPython" モードでのコンパイルが基本となる 
 +    * 実行時コンパイル（JIT）では、実行時間に解析・コンパイル時間が含まれるため、なるべく事前コンパイル（AOT）したい
   * 使わない方がよい問題もある   * 使わない方がよい問題もある
     * 文字列の方が扱いやすい問題とか、多倍長整数が有効な問題とか     * 文字列の方が扱いやすい問題とか、多倍長整数が有効な問題とか
     * →全ての問題に共通して使うテンプレート、というのではなく、必要に応じて呼び出せるスニペットがよい     * →全ての問題に共通して使うテンプレート、というのではなく、必要に応じて呼び出せるスニペットがよい
-  * 提出コードとローカル環境で同じコードで動かしたい+  * ローカル環境でテストした上で提出する 
 +    * ローカル用と提出用でコードの変更が必要なら、ローカル用のコードをうっかり提出してしまうケアレスミスが発生する 
 +    * →なるべく同一のコードで動く方がよい
  
-そもそも、Pythonはお手軽に書けるのが一つの利点であり、 +このことを念頭に置いて、スニペットを作成する。
-使える関数やデータ型が限定されるNumbaに書き換えてまで +
-Pythonにこだわる意味があるのか、というのはある。 +
-AtCoder以外では今のところ使えないし、複雑な処理ではコンパイル可能なコードにするのがまず難しい。+
  
-そうは言っても、メイン言語がPythonの人にとって、1から%%C++%%などで書きなおす以外にPythonで通せる幅が広がったのは歓迎すべきことだ。+==== スニペット ==== 
 + 
 +以下、考慮すべきことと採択理由をメモしている。
  
-==== 事前コンパイル ====+=== 事前コンパイル ===
  
-Numbaのコンパイルには、大別して実行時コンパイル（JIT）と事前コンパイル（AOT）がある。+Numbaのコンパイルには、大別して実行時コンパイル（JIT）と事前コンパイル（AOT）がある。\\
 JITはその名の通り実行時間にコンパイル時間が含まれてしまうので、基本的にはAOTを行いたい。 JITはその名の通り実行時間にコンパイル時間が含まれてしまうので、基本的にはAOTを行いたい。
  
行 276: 行 287:
  
   * [[http://numba.pydata.org/numba-doc/latest/developer/caching.html|Notes on Caching — Numba 0.50.1 documentation]]   * [[http://numba.pydata.org/numba-doc/latest/developer/caching.html|Notes on Caching — Numba 0.50.1 documentation]]
 +
 +<WRAP center round box>
 +AtCoderのジャッジシステムでは、テストケース実行前に提出コードをコンパイルするフェーズがある。
 +スクリプト言語にとっても起動を速くする効果があったりするため、行われている。
 +
 +  * 下記ページ中の「コンパイルコマンド」がコンパイルフェーズに実行される
 +    * [[https://atcoder.jp/contests/language-test-202001|Language Test 202001 - AtCoder]]
 +
 +Pythonでは ''ONLINE_JUDGE'' を実行時オプションとした処理が1回走る。
 +Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。
 +</WRAP>
  
 つまり、以下のいずれかを行えばよい。 つまり、以下のいずれかを行えばよい。
行 284: 行 306:
 一長一短あるので使い分け。でも基本的にはJITの方が使い勝手がよい。 一長一短あるので使い分け。でも基本的にはJITの方が使い勝手がよい。
  
-=== メリット・デメリット ===+== メリット・デメリット ==
  
   * コードの見やすさ・改修の容易さ   * コードの見やすさ・改修の容易さ
行 298: 行 320:
 コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。 コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。
  
-=== AtCoderのジャッジシステムの仕組み ===+こう書くとAOTはやたら面倒そうだが、スニペットとしてまとめ、使い方さえ把握しておけば大丈夫。
  
-AtCoderのジャッジシステムでは、テストケース実行前に ''ONLINE_JUDGE'' を実行時オプションとした処理が1回走る。 +== ローカル環境でのAOT ==
- +
-  * [[https://docs.google.com/spreadsheets/d/1PmsqufkF3wjKN6g1L0STS80yP4a6u-VdGiEv5uOHe0M/]] +
- +
-C言語などにとってのコンパイル処理をするフェーズだが、 +
-スクリプト言語にとっても起動を速くする効果があったりするため、行われている。 +
- +
-Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。 +
-コンパイルフェーズで生成されたファイルは削除されず残る。 +
- +
-ただ、ファイルが残る仕様は悪用しようと思えば色々できてしまうと思うので、もしかしたら将来的になくなるかも知れない。 +
- +
-=== ローカル環境でのAOT ===+
  
 AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。 AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。
行 319: 行 329:
 また、1つのコンパイル結果をそんなに何回も使い回さない。 また、1つのコンパイル結果をそんなに何回も使い回さない。
  
-それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。 +それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。\\
 さらに、それならローカルではAOTでなくJITでいいよね、という話になる。 さらに、それならローカルではAOTでなくJITでいいよね、という話になる。
  
行 328: 行 337:
 これで切り分けて、ローカルならJITコンパイルして実行するようにスニペットを作っておく。 これで切り分けて、ローカルならJITコンパイルして実行するようにスニペットを作っておく。
  
-==== 入力受け取りと型指定 ====+=== 入力受け取りと型指定 ===
  
 Numba関数内ではinput()など入力受け取り関数は使えない。素のPythonで受け取って、引数として与える必要がある。 Numba関数内ではinput()など入力受け取り関数は使えない。素のPythonで受け取って、引数として与える必要がある。
行 337: 行 346:
  
 厳密には、JITの場合は型指定せずとも動くのは動く。 厳密には、JITの場合は型指定せずとも動くのは動く。
-ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない（つまり本来の意味での実行時コンパイルになる）。+ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない（本来の意味での実行時コンパイルになる）。
 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。
  
-=== 入力の共通化 ===+== 入力の共通化 ==
  
 毎回きちんと型指定するのは手間だし、どう書けばいいんだっけ、と間違いも起こりやすい。 毎回きちんと型指定するのは手間だし、どう書けばいいんだっけ、と間違いも起こりやすい。
行 356: 行 365:
  
  
-==== 関数を分ける ==== +=== 実装例 ===
- +
-処理の切り出しなどで複数の関数を書きたくなったとき、以下の2つがあるが、 +
- +
-  * それぞれを個別にコンパイル +
-  * 1つの大枠の関数の中で個々の関数定義も書いて、大枠の関数のみコンパイル +
- +
-前者は関数毎にコンパイル指定（JITなら''@njit''デコレータの付与、AOTなら''cc.export''への登録）の必要がある一方、 +
-後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 +
- +
-普通に後者でいいと今のところは思っている。 +
- +
-==== 独自クラス ==== +
- +
-''@jitclass'' デコレータによりJITでのコンパイルは可能だが、これはこれで関数とは別の書き方が必要であり、覚えることとが増えてしまう。 +
- +
-AOTでのコンパイル方法は探したけど見つかってない。 +
- +
-クラスは一連の処理をまとめて理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 +
- +
-  * [[https://numba.pydata.org/numba-doc/latest/user/jitclass.html|jitclass]] +
- +
-==== 実装例 ====+
  
 === AOT === === AOT ===
  
-以下を参照させていただいた。あまり変わっていないが、手元環境でも同一コードで動く。+以下を参照させていただいた。あまり変わっていないが、ローカル環境でも同一コードで動くようにした。
  
   * [[https://qiita.com/yniji/items/d012bb9f938e0445a3ff#numba-aot|AtCoderで Python を高速化する Numpy + Numba を使う - Qiita]]   * [[https://qiita.com/yniji/items/d012bb9f938e0445a3ff#numba-aot|AtCoderで Python を高速化する Numpy + Numba を使う - Qiita]]
  
-手元環境がWindowsであることを前提としており、''os.name'' でLinux（AtCoderのジャッジシステム）と区別できる。 +ローカル環境がWindowsであることを前提としており、''os.name'' でLinux（AtCoderのジャッジシステム）と区別できる。 
-MacやLinuxなら、''platform'' などでAtCoderのシステムと違う箇所を探すか、手元環境のみそれとわかる実行時オプションを付けて識別すればよい。+MacやLinuxなら、''platform'' モジュールなどでジャッジシステムと違う箇所を探すか、ローカル環境のみ実行時オプションを付けて識別するなどする。
  
 基本的に ''solve()'' の中身と、あと必要なら最後の出力整形部分のみ書けばよい。 基本的に ''solve()'' の中身と、あと必要なら最後の出力整形部分のみ書けばよい。
- 
-処理を切り分けるものの、見た目的にあまり階層は深くしたくない。参照させていただいたコードはその点も配慮されていて、メインで記述する箇所が十分浅く、書きやすい。 
  
 ++++ 実装例 | ++++ 実装例 |
行 432: 行 417:
 </sxh> </sxh>
 ++++ ++++
 +
 +
 +==== 関数を分ける ====
 +
 +処理の切り出しなどで関数を複数に分けたくなったとき、以下の2つがあるが、
 +
 +  * それぞれをグローバルに書いて個別にコンパイル
 +  * 1つの大枠の関数の中で個々の関数定義を書いて、大枠の関数のみコンパイル（内部関数）
 +
 +前者は関数毎にコンパイル指定（JITなら''@njit''デコレータの付与、AOTなら''cc.export''への登録）の必要がある一方、
 +後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。
 +
 +ただし、内部関数が再帰を含む場合、コンパイルが通らない。
 +
 +  numba.core.errors.NotDefinedError: Variable '(内部関数名)' is not defined.
 +
 +通常は1つの大枠関数に入れた方が手間が少ないのでそうし、再帰関数のみ個別にコンパイルする。
 +
 +
 +==== 独自クラス ====
 +
 +''@jitclass'' デコレータによりJITでのコンパイルは可能だが、これはこれで関数とは別の書き方が必要であり、覚えることとが増えてしまう。
 +
 +AOTでのコンパイル方法は探したけど見つかってない。
 +
 +クラスは、1つのオブジェクトに関係する処理をまとめることで理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。
 +
 +  * [[https://numba.pydata.org/numba-doc/latest/user/jitclass.html|jitclass]]
 +
 +==== エラー対策 ====
 +
 +Numbaを使うと、エラーのデバッグに若干手間取ることがある。
 +
 +特に、ローカルでは動くのにサーバではREが出た時に厄介。
 +
 +Numbaは今まさに発展中のモジュールなので、バージョンの違いで使える機能に結構大きな差が出てくる。\\
 +AtCoderの現在のNumbaのバージョンは 0.48.0 なので、差し支えなければこれに揃える。\\
 +ただ、Numbaだけを揃えても、他のNumPy等のモジュールの違いのせいなのか不明だが、REが出ることがある。
 +
 +  * AtCoderでは、コンパイルフェーズにエラーが出ても、Pythonの場合はCEでなくREとなる
 +    * 参考: [[https://atcoder.jp/contests/abc177/submissions/16507701|提出 #16507701 - AtCoder Beginner Contest 177]]
 +    * コンパイルフェーズでRE、本実行でWAとなるはずのコードだが、結果はREとなっている
 +
 +そのため、テストケースが全てREの場合はコンパイルフェーズの可能性も視野に入れる。
 +
 +また、
 +
 +  * 「コードテスト」における実行の場合は、Pythonのコンパイルフェーズは行われないっぽい
 +  * Numbaのエラーコメントはバックトレースが長く、コードテストの欄で最後まで表示されないことも多い
 +
 +このため、
 +
 +  * AOTではそもそも実行できない
 +  * JITに書き換えても、コンパイル時間が長いと10秒で打ち切られる
 +  * 実行してエラーを発生させても、エラーコメントからエラー箇所が見えない
 +
 +という問題により、ちょっとデバッグがしづらい。
 +
 +これの解決策は今のところ見つけられていない。Numbaを選択するときのリスクの1つ。
 +
programming_algorithm/python_tips.txt · 最終更新: 2020/09/27 by ikatakos
文書の表示
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0