差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:python_tips [2020/07/01] – [事前コンパイル] ikatakosprogramming_algorithm:python_tips [2020/09/27] (現在) – [エラー対策] ikatakos
行 4: 行 4:
  
 Pythonで競プロに参加する上での、言語依存な書き方など。散発的になるのは仕方なし。 Pythonで競プロに参加する上での、言語依存な書き方など。散発的になるのは仕方なし。
 +
 +===== 環境 =====
 +
 +AtCoderにおけるPythonの環境
 +
 +<code - OS>
 +import subprocess
 +subprocess.run(['cat', '/etc/os-release'])
 +
 +
 +...
 +VERSION="18.04.4 LTS (Bionic Beaver)"
 +...
 +</code>
 +
 +<code - モジュール一覧>
 +import sys
 +import subprocess
 +subprocess.run([sys.executable, '-m', 'pip', 'list'])
 +
 +
 +
 +asn1crypto (0.24.0)
 +cryptography (2.1.4)
 +Cython (0.29.16)
 +decorator (4.4.2)
 +idna (2.6)
 +joblib (0.14.1)
 +keyring (10.6.0)
 +keyrings.alt (3.0)
 +llvmlite (0.31.0)
 +netifaces (0.10.4)
 +networkx (2.4)
 +numba (0.48.0)
 +numpy (1.18.2)
 +pip (9.0.1)
 +pycrypto (2.6.1)
 +Pygments (2.2.0)
 +pygobject (3.26.1)
 +python-apt (1.6.5+ubuntu0.2)
 +pyxdg (0.25)
 +PyYAML (3.12)
 +scikit-learn (0.22.2.post1)
 +scipy (1.4.1)
 +SecretStorage (2.3.1)
 +setuptools (46.1.3)
 +six (1.11.0)
 +unattended-upgrades (0.1)
 +wheel (0.30.0)
 +</code>
  
 ===== 入出力 ===== ===== 入出力 =====
行 48: 行 98:
  
   * input() と異なり、末尾の改行は残る   * input() と異なり、末尾の改行は残る
-    * 入力を数値になおす場合、''int(), float()'' などは末尾に改行が付いていても解釈してくれるので、特に取り除く必要は無い +    * 数値になおす場合、''int(), float()'' などは末尾に改行が付いていても解釈できるので、特に取り除く必要は無い 
-    * 入力をそのまま文字列として扱う場合に、改行文字に注意+    * そのまま文字列として扱う場合に、改行文字に注意
     * s.rstrip() で、sについた末尾の改行は削除できる     * s.rstrip() で、sについた末尾の改行は削除できる
   * 入力の終了   * 入力の終了
-    * 入力の終わりは「EOF」という特殊な文字で判断するので、手元でのテストなど入力をコマンドプロンプト(Windows)から与える場合、そのままでは実行が始まらない+    * 入力の終わりは「EOF」という特殊な記号で判断するので、手元で入力を直接打ち込むなどで与える場合、そのままでは実行が始まらない
     * Ctrl-D で「EOF」を入力できる     * Ctrl-D で「EOF」を入力できる
  
行 251: 行 301:
 多くの競プロサイトは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: 行 337:
  
   * [[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: 行 356:
 一長一短あるので使い分け。でも基本的にはJITの方が使い勝手がよい。 一長一短あるので使い分け。でも基本的にはJITの方が使い勝手がよい。
  
-=== メリット・デメリット ===+== メリット・デメリット ==
  
   * コードの見やすさ・改修の容易さ   * コードの見やすさ・改修の容易さ
行 298: 行 370:
 コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。 コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。
  
-=== AtCoderのジャッジシステムの仕組み === +こう書くとAOTら面倒そうだが、スニペットとまとめ、使方さえ把握しておけ大丈夫
- +
-AtCoderのジャッジシステムで、テストケース実行前に ''ONLINE_JUDGE'' を実行時オプションとし処理が1回走る。 +
- +
-  * [[https://docs.google.com/spreadsheets/d/1PmsqufkF3wjKN6g1L0STS80yP4a6u-VdGiEv5uOHe0M/]] +
- +
-C言語などにとってのコンパイル処理をするフェーズだが、 +
-クリプ言語にも起動を速くする効果があったりするため、行われてる。 +
- +
-Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。 +
-コンパイルフェーズで生成されたファイルは削除されず残る。 +
- +
-ただ、ファイルが残る仕様は悪用しようと思え色々できてしまうと思うので、もしかしたら将来的になくなるかも知れない+
  
-=== ローカル環境でのAOT ===+== ローカル環境でのAOT ==
  
 AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。 AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。
行 319: 行 379:
 また、1つのコンパイル結果をそんなに何回も使い回さない。 また、1つのコンパイル結果をそんなに何回も使い回さない。
  
-それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。 +それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。\\
 さらに、それならローカルではAOTでなくJITでいいよね、という話になる。 さらに、それならローカルではAOTでなくJITでいいよね、という話になる。
  
行 328: 行 387:
 これで切り分けて、ローカルならJITコンパイルして実行するようにスニペットを作っておく。 これで切り分けて、ローカルならJITコンパイルして実行するようにスニペットを作っておく。
  
-==== 入力受け取りと型指定 ====+=== 入力受け取りと型指定 ===
  
 Numba関数内ではinput()など入力受け取り関数は使えない。素のPythonで受け取って、引数として与える必要がある。 Numba関数内ではinput()など入力受け取り関数は使えない。素のPythonで受け取って、引数として与える必要がある。
行 337: 行 396:
  
 厳密には、JITの場合は型指定せずとも動くのは動く。 厳密には、JITの場合は型指定せずとも動くのは動く。
-ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない(つまり本来の意味での実行時コンパイルになる)。+ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない(本来の意味での実行時コンパイルになる)。
 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。
  
-=== 入力の共通化 ===+== 入力の共通化 ==
  
 毎回きちんと型指定するのは手間だし、どう書けばいいんだっけ、と間違いも起こりやすい。 毎回きちんと型指定するのは手間だし、どう書けばいいんだっけ、と間違いも起こりやすい。
行 356: 行 415:
  
  
-==== 関数を分ける ====+=== 実装例 ===
  
-処理の切り出しなどで複数の関数を書きたくなったとき、以下の2つがあるが、 +以下を参照させていただいた。あまり変わっていないが、ローカル環境でも同一コードで動くようにした
- +
-  * それぞれを個別にコンパイル +
-  * 1つの大枠の関数の中で個々の関数定義も書いて、大枠の関数のみコンパイル +
- +
-前者は関数毎にコンパイル指定(JITなら''@njit''デコレータの付与、AOTなら''cc.export''への登録)の必要がある一方、 +
-後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 +
- +
-普通に後者でいいと今のところは思っている。 +
- +
-==== 独自クラス ==== +
- +
-''@jitclass'' デコレータによりJITでのコンパイルは可能だが、これはこれで関数とは別の書き方が必要であり、覚えることとが増えてしまう。 +
- +
-AOTでのコンパイル方法は探したけど見つかってない。 +
- +
-クラスは一連の処理をまとめて理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 +
- +
-  * [[https://numba.pydata.org/numba-doc/latest/user/jitclass.html|jitclass]] +
- +
-==== 実装例 ==== +
- +
-=== 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: 行 465:
 </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の場合はコンパイルフェーズの可能性も視野に入れる。
 +
 +また、
 +
 +  * <del>「コードテスト」における実行の場合は、Pythonのコンパイルフェーズは行われないっぽい</del>
 +    * 実行環境が、''os.getcwd() == '/imojudge/sandbox''' となるので、これによる切り分けが可能
 +  * Numbaのエラーコメントはバックトレースが長く、コードテストの欄で最後まで表示されないことも多い
 +
 +このため、
 +
 +  * AOTではそもそも実行できない
 +  * JITに書き換えても、コンパイル時間が長いと10秒で打ち切られる
 +  * 実行してエラーを発生させても、エラーコメントからエラー箇所が見えない
 +
 +という問題により、ちょっとデバッグがしづらい。
 +
 +これの解決策は今のところ見つけられていない。Numbaを選択するときのリスクの1つ。
 +
 +==== コンパイル時間超過 ====
 +
 +Numbaの中身が複雑だったりしてコンパイルに時間がかかりすぎると、どうも勝手に打ち切られるらしい。
 +
 +その場合、コンパイルフェイズでモジュールが生成されない→実行フェイズでモジュールが存在しないので、全てのテストケースで ''RE'' となる。
 +
 +コンパイル時間を短くするような書き方については要調査。
 +
 +  * [[https://imoz.jp/note/onlinejudge.html|いもす研 (imos laboratory)]]
 +    * オンラインジャッジでコンパイルが終了しない場合は適切に打ち切る必要を語られている
 +  * [[https://twitter.com/imos/status/788791806125158400|いもすさんはTwitterを使っています 「imos contestとか懐かしい.2008年とかもう8年前か……….使われていたのは第一世代 Imo Judge かしら?(※ AtCoderで使われているのは第三世代 Imo Judge」 / Twitter]]
 +    * 少なくとも2016年では上を元にしたジャッジシステムが使われているっぽい
 +
 +
 +
programming_algorithm/python_tips.1593595354.txt.gz · 最終更新: 2020/07/01 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0