差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:python_tips [2020/07/01] – [事前コンパイル] ikatakos | programming_algorithm:python_tips [2020/09/27] (現在) – [エラー対策] ikatakos | ||
---|---|---|---|
行 4: | 行 4: | ||
Pythonで競プロに参加する上での、言語依存な書き方など。散発的になるのは仕方なし。 | Pythonで競プロに参加する上での、言語依存な書き方など。散発的になるのは仕方なし。 | ||
+ | |||
+ | ===== 環境 ===== | ||
+ | |||
+ | AtCoderにおけるPythonの環境 | ||
+ | |||
+ | <code - OS> | ||
+ | import subprocess | ||
+ | subprocess.run([' | ||
+ | |||
+ | ↓ | ||
+ | ... | ||
+ | VERSION=" | ||
+ | ... | ||
+ | </ | ||
+ | |||
+ | <code - モジュール一覧> | ||
+ | import sys | ||
+ | import subprocess | ||
+ | subprocess.run([sys.executable, | ||
+ | |||
+ | ↓ | ||
+ | |||
+ | 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) | ||
+ | </ | ||
===== 入出力 ===== | ===== 入出力 ===== | ||
行 48: | 行 98: | ||
* input() と異なり、末尾の改行は残る | * input() と異なり、末尾の改行は残る | ||
- | * 入力を数値になおす場合、'' | + | * 数値になおす場合、'' |
- | * 入力をそのまま文字列として扱う場合に、改行文字に注意 | + | * そのまま文字列として扱う場合に、改行文字に注意 |
* s.rstrip() で、sについた末尾の改行は削除できる | * s.rstrip() で、sについた末尾の改行は削除できる | ||
* 入力の終了 | * 入力の終了 | ||
- | * 入力の終わりは「EOF」という特殊な文字で判断するので、手元でのテストなど入力をコマンドプロンプト(Windows)から与える場合、そのままでは実行が始まらない | + | * 入力の終わりは「EOF」という特殊な記号で判断するので、手元で入力を直接打ち込むなどで与える場合、そのままでは実行が始まらない |
* Ctrl-D で「EOF」を入力できる | * Ctrl-D で「EOF」を入力できる | ||
行 251: | 行 301: | ||
多くの競プロサイトはNumbaは使えないことが多いが、AtCoderは2020/ | 多くの競プロサイトはNumbaは使えないことが多いが、AtCoderは2020/ | ||
- | 競プロの文脈でポイントとなるのは、以下だろう。 | + | そもそも、Pythonはお手軽に書けるのが一つの利点であり、 |
+ | 使える関数やデータ型が限定されるNumbaに書き換えてまで | ||
+ | Pythonにこだわる意味があるのか、というのはある。\\ | ||
+ | AtCoder以外では今のところ使えないし、複雑な処理ではコンパイル可能なコードにするのが難しいこともある。 | ||
+ | |||
+ | そうは言っても、メイン言語がPythonの人にとって、1から%%C++%%などで書きなおす以外にPythonで通せる幅が広がったのは歓迎すべきことだ。 | ||
+ | |||
+ | |||
+ | Numbaの中でも使い方は複数あるが、競プロの文脈でポイントとなるのは、以下だろう。 | ||
- | * 高速化のため、NoPythonモード、事前コンパイル | + | |
+ | | ||
+ | * 実行時コンパイル(JIT)では、実行時間に解析・コンパイル時間が含まれるため、なるべく事前コンパイル(AOT)したい | ||
* 使わない方がよい問題もある | * 使わない方がよい問題もある | ||
* 文字列の方が扱いやすい問題とか、多倍長整数が有効な問題とか | * 文字列の方が扱いやすい問題とか、多倍長整数が有効な問題とか | ||
* →全ての問題に共通して使うテンプレート、というのではなく、必要に応じて呼び出せるスニペットがよい | * →全ての問題に共通して使うテンプレート、というのではなく、必要に応じて呼び出せるスニペットがよい | ||
- | * 提出コードとローカル環境で同じコードで動かしたい | + | * ローカル環境でテストした上で提出する |
+ | * ローカル用と提出用でコードの変更が必要なら、ローカル用のコードをうっかり提出してしまうケアレスミスが発生する | ||
+ | * →なるべく同一のコードで動く方がよい | ||
- | そもそも、Pythonはお手軽に書けるのが一つの利点であり、 | + | このことを念頭に置いて、スニペットを作成する。 |
- | 使える関数やデータ型が限定されるNumbaに書き換えてまで | + | |
- | Pythonにこだわる意味があるのか、というのはある。 | + | |
- | AtCoder以外では今のところ使えないし、複雑な処理ではコンパイル可能なコードにするのがまず難しい。 | + | |
- | そうは言っても、メイン言語がPythonの人にとって、1から%%C++%%などで書きなおす以外にPythonで通せる幅が広がったのは歓迎すべきことだ。 | + | ==== スニペット ==== |
+ | |||
+ | 以下、考慮すべきことと採択理由をメモしている。 | ||
- | ==== 事前コンパイル | + | === 事前コンパイル === |
- | Numbaのコンパイルには、大別して実行時コンパイル(JIT)と事前コンパイル(AOT)がある。 | + | Numbaのコンパイルには、大別して実行時コンパイル(JIT)と事前コンパイル(AOT)がある。\\ |
JITはその名の通り実行時間にコンパイル時間が含まれてしまうので、基本的にはAOTを行いたい。 | JITはその名の通り実行時間にコンパイル時間が含まれてしまうので、基本的にはAOTを行いたい。 | ||
行 276: | 行 337: | ||
* [[http:// | * [[http:// | ||
+ | |||
+ | <WRAP center round box> | ||
+ | AtCoderのジャッジシステムでは、テストケース実行前に提出コードをコンパイルするフェーズがある。 | ||
+ | スクリプト言語にとっても起動を速くする効果があったりするため、行われている。 | ||
+ | |||
+ | * 下記ページ中の「コンパイルコマンド」がコンパイルフェーズに実行される | ||
+ | * [[https:// | ||
+ | |||
+ | Pythonでは '' | ||
+ | Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。 | ||
+ | </ | ||
つまり、以下のいずれかを行えばよい。 | つまり、以下のいずれかを行えばよい。 | ||
行 284: | 行 356: | ||
一長一短あるので使い分け。でも基本的にはJITの方が使い勝手がよい。 | 一長一短あるので使い分け。でも基本的にはJITの方が使い勝手がよい。 | ||
- | === メリット・デメリット | + | == メリット・デメリット == |
* コードの見やすさ・改修の容易さ | * コードの見やすさ・改修の容易さ | ||
行 298: | 行 370: | ||
コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。 | コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。 | ||
- | === AtCoderのジャッジシステムの仕組み === | + | こう書くとAOTはやたら面倒そうだが、スニペットとしてまとめ、使い方さえ把握しておけば大丈夫。 |
- | + | ||
- | AtCoderのジャッジシステムでは、テストケース実行前に '' | + | |
- | + | ||
- | * [[https:// | + | |
- | + | ||
- | 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なら'' | + | |
- | 後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 | + | |
- | + | ||
- | 普通に後者でいいと今のところは思っている。 | + | |
- | + | ||
- | ==== 独自クラス ==== | + | |
- | + | ||
- | '' | + | |
- | + | ||
- | AOTでのコンパイル方法は探したけど見つかってない。 | + | |
- | + | ||
- | クラスは一連の処理をまとめて理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 | + | |
- | + | ||
- | * [[https:// | + | |
- | + | ||
- | ==== 実装例 ==== | + | |
- | + | ||
- | === AOT === | + | |
- | + | ||
- | 以下を参照させていただいた。あまり変わっていないが、手元環境でも同一コードで動く。 | + | |
* [[https:// | * [[https:// | ||
- | 手元環境がWindowsであることを前提としており、'' | + | ローカル環境がWindowsであることを前提としており、'' |
- | MacやLinuxなら、'' | + | MacやLinuxなら、'' |
基本的に '' | 基本的に '' | ||
- | |||
- | 処理を切り分けるものの、見た目的にあまり階層は深くしたくない。参照させていただいたコードはその点も配慮されていて、メインで記述する箇所が十分浅く、書きやすい。 | ||
++++ 実装例 | | ++++ 実装例 | | ||
行 432: | 行 465: | ||
</ | </ | ||
++++ | ++++ | ||
+ | |||
+ | |||
+ | ==== 関数を分ける ==== | ||
+ | |||
+ | 処理の切り出しなどで関数を複数に分けたくなったとき、以下の2つがあるが、 | ||
+ | |||
+ | * それぞれをグローバルに書いて個別にコンパイル | ||
+ | * 1つの大枠の関数の中で個々の関数定義を書いて、大枠の関数のみコンパイル(内部関数) | ||
+ | |||
+ | 前者は関数毎にコンパイル指定(JITなら'' | ||
+ | 後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 | ||
+ | |||
+ | ただし、内部関数が再帰を含む場合、コンパイルが通らない。 | ||
+ | |||
+ | numba.core.errors.NotDefinedError: | ||
+ | |||
+ | 通常は1つの大枠関数に入れた方が手間が少ないのでそうし、再帰関数のみ個別にコンパイルする。 | ||
+ | |||
+ | |||
+ | ==== 独自クラス ==== | ||
+ | |||
+ | '' | ||
+ | |||
+ | AOTでのコンパイル方法は探したけど見つかってない。 | ||
+ | |||
+ | クラスは、1つのオブジェクトに関係する処理をまとめることで理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | ==== エラー対策 ==== | ||
+ | |||
+ | Numbaを使うと、エラーのデバッグに若干手間取ることがある。 | ||
+ | |||
+ | 特に、ローカルでは動くのにサーバではREが出た時に厄介。 | ||
+ | |||
+ | Numbaはバージョンの違いで使える機能に結構差が出てくる。\\ | ||
+ | AtCoderの現在のNumbaのバージョンは 0.48.0 なので、差し支えなければこれに揃える。\\ | ||
+ | ただ、Numbaだけを揃えても、他のNumPy等のモジュールの違いのせいなのか不明だが、REが出ることがある。 | ||
+ | |||
+ | * AtCoderでは、コンパイルフェーズにエラーが出ても、Pythonの場合はCEでなくREとなる | ||
+ | * 参考: [[https:// | ||
+ | * コンパイルフェーズでRE、本実行でWAとなるはずのコードだが、結果はREとなっている | ||
+ | |||
+ | そのため、テストケースが全てREの場合はコンパイルフェーズの可能性も視野に入れる。 | ||
+ | |||
+ | また、 | ||
+ | |||
+ | * < | ||
+ | * 実行環境が、'' | ||
+ | * Numbaのエラーコメントはバックトレースが長く、コードテストの欄で最後まで表示されないことも多い | ||
+ | |||
+ | このため、 | ||
+ | |||
+ | * AOTではそもそも実行できない | ||
+ | * JITに書き換えても、コンパイル時間が長いと10秒で打ち切られる | ||
+ | * 実行してエラーを発生させても、エラーコメントからエラー箇所が見えない | ||
+ | |||
+ | という問題により、ちょっとデバッグがしづらい。 | ||
+ | |||
+ | これの解決策は今のところ見つけられていない。Numbaを選択するときのリスクの1つ。 | ||
+ | |||
+ | ==== コンパイル時間超過 ==== | ||
+ | |||
+ | Numbaの中身が複雑だったりしてコンパイルに時間がかかりすぎると、どうも勝手に打ち切られるらしい。 | ||
+ | |||
+ | その場合、コンパイルフェイズでモジュールが生成されない→実行フェイズでモジュールが存在しないので、全てのテストケースで '' | ||
+ | |||
+ | コンパイル時間を短くするような書き方については要調査。 | ||
+ | |||
+ | * [[https:// | ||
+ | * オンラインジャッジでコンパイルが終了しない場合は適切に打ち切る必要を語られている | ||
+ | * [[https:// | ||
+ | * 少なくとも2016年では上を元にしたジャッジシステムが使われているっぽい | ||
+ | |||
+ | |||
+ |