差分

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

--- programming_algorithm:python_tips [2020/07/01] – [事前コンパイル] ikatakos
+++ programming_algorithm:python_tips [2020/09/07] – ikatakos
@@ 行 251: / 行 251: @@
 多くの競プロサイトは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を行いたい。
@@ 行 276: / 行 283: @@
   * [[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>
 つまり、以下のいずれかを行えばよい。
@@ 行 298: / 行 316: @@
 コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。
-=== AtCoderのジャッジシステムの仕組み ===
+こう書くとAOTはやたら面倒そうだが、スニペットとしてまとめ、使い方さえ把握しておけば大丈夫。
-AtCoderのジャッジシステムでは、テストケース実行前に ''ONLINE_JUDGE'' を実行時オプションとした処理が1回走る。
-  * [[https://docs.google.com/spreadsheets/d/1PmsqufkF3wjKN6g1L0STS80yP4a6u-VdGiEv5uOHe0M/]]
-C言語などにとってのコンパイル処理をするフェーズだが、
-スクリプト言語にとっても起動を速くする効果があったりするため、行われている。
-Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。
-コンパイルフェーズで生成されたファイルは削除されず残る。
-ただ、ファイルが残る仕様は悪用しようと思えば色々できてしまうと思うので、もしかしたら将来的になくなるかも知れない。
 === ローカル環境でのAOT ===
@@ 行 319: / 行 325: @@
 また、1つのコンパイル結果をそんなに何回も使い回さない。
-それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。
+それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。\\
 さらに、それならローカルではAOTでなくJITでいいよね、という話になる。
@@ 行 337: / 行 342: @@
 厳密には、JITの場合は型指定せずとも動くのは動く。
-ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない（つまり本来の意味での実行時コンパイルになる）。
+ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない（本来の意味での実行時コンパイルになる）。
 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。
@@ 行 358: / 行 363: @@
 ==== 関数を分ける ====
-処理の切り出しなどで複数の関数を書きたくなったとき、以下の2つがあるが、
+処理の切り出しなどで関数を複数に分けたくなったとき、以下の2つがあるが、
-  * それぞれを個別にコンパイル
+  * それぞれをグローバルに書いて個別にコンパイル
-  * 1つの大枠の関数の中で個々の関数定義も書いて、大枠の関数のみコンパイル
+  * 1つの大枠の関数の中で個々の関数定義を書いて、大枠の関数のみコンパイル（内部関数）
 前者は関数毎にコンパイル指定（JITなら''@njit''デコレータの付与、AOTなら''cc.export''への登録）の必要がある一方、
 後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。
-普通に後者でいいと今のところは思っている。
+ただし、内部関数が再帰を含む場合、コンパイルが通らない。
+  numba.core.errors.NotDefinedError: Variable '(内部関数名)' is not defined.
+通常は1つの大枠関数に入れた方が手間が少ないのでそうし、再帰関数のみ個別にコンパイルする。
 ==== 独自クラス ====
@@ 行 374: / 行 384: @@
 AOTでのコンパイル方法は探したけど見つかってない。
-クラスは一連の処理をまとめて理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。
+クラスは、1つのオブジェクトに関係する処理をまとめることで理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。
   * [[https://numba.pydata.org/numba-doc/latest/user/jitclass.html|jitclass]]
@@ 行 382: / 行 392: @@
 === AOT ===
-以下を参照させていただいた。あまり変わっていないが、手元環境でも同一コードで動く。
+以下を参照させていただいた。あまり変わっていないが、ローカル環境でも同一コードで動くようにした。
   * [[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()'' の中身と、あと必要なら最後の出力整形部分のみ書けばよい。
-処理を切り分けるものの、見た目的にあまり階層は深くしたくない。参照させていただいたコードはその点も配慮されていて、メインで記述する箇所が十分浅く、書きやすい。
 ++++ 実装例 |