差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:python_tips [2020/06/29] – [方針] ikatakos | programming_algorithm:python_tips [2020/07/03] – [関数を分ける] ikatakos | ||
---|---|---|---|
行 251: | 行 251: | ||
多くの競プロサイトはNumbaは使えないことが多いが、AtCoderは2020/ | 多くの競プロサイトはNumbaは使えないことが多いが、AtCoderは2020/ | ||
- | 競プロの文脈では、どのように書くように習慣づけるのがよいだろうか。 | + | 競プロの文脈でポイントとなるのは、以下だろう。 |
- | ポイントとなるのは、以下だろう。 | + | |
- | * NoPythonモードでないと大きな高速化は期待できない | + | * "NoPythonモード" |
- | * Numba関数内部では、input(), | + | |
- | * 入力受け取り自体はNumba関数外部で行い、引数として与える必要がある | + | |
* 使わない方がよい問題もある | * 使わない方がよい問題もある | ||
* 文字列の方が扱いやすい問題とか、多倍長整数が有効な問題とか | * 文字列の方が扱いやすい問題とか、多倍長整数が有効な問題とか | ||
- | * 全ての問題に共通して使うテンプレート、というのではなく、必要に応じて呼び出せるスニペットがよい | + | * →全ての問題に共通して使うテンプレート、というのではなく、必要に応じて呼び出せるスニペットがよい |
- | * JITはコンパイル時間が実行時間に含まれるため、なるべくAOTしたい | + | * 提出コードとローカル環境で同じコードで動かしたい |
そもそも、Pythonはお手軽に書けるのが一つの利点であり、 | そもそも、Pythonはお手軽に書けるのが一つの利点であり、 | ||
- | 使える関数やデータ型が限定されるNumbaに書き換えてまで、 | + | 使える関数やデータ型が限定されるNumbaに書き換えてまで |
Pythonにこだわる意味があるのか、というのはある。 | Pythonにこだわる意味があるのか、というのはある。 | ||
AtCoder以外では今のところ使えないし、複雑な処理ではコンパイル可能なコードにするのがまず難しい。 | AtCoder以外では今のところ使えないし、複雑な処理ではコンパイル可能なコードにするのがまず難しい。 | ||
行 269: | 行 266: | ||
そうは言っても、メイン言語がPythonの人にとって、1から%%C++%%などで書きなおす以外にPythonで通せる幅が広がったのは歓迎すべきことだ。 | そうは言っても、メイン言語がPythonの人にとって、1から%%C++%%などで書きなおす以外にPythonで通せる幅が広がったのは歓迎すべきことだ。 | ||
- | ==== 方針 | + | ==== 事前コンパイル |
Numbaのコンパイルには、大別して実行時コンパイル(JIT)と事前コンパイル(AOT)がある。 | Numbaのコンパイルには、大別して実行時コンパイル(JIT)と事前コンパイル(AOT)がある。 | ||
- | JITは、その名の通り実行時間にコンパイル時間が含まれてしまうので、基本的にはAOTを行いたい。 | + | JITはその名の通り実行時間にコンパイル時間が含まれてしまうので、基本的にはAOTを行いたい。 |
ただし、JITでも '' | ただし、JITでも '' | ||
行 279: | 行 276: | ||
* [[http:// | * [[http:// | ||
+ | |||
+ | <WRAP center round box> | ||
+ | AtCoderのジャッジシステムでは、テストケース実行前に提出コードをコンパイルするフェーズがある。 | ||
+ | スクリプト言語にとっても起動を速くする効果があったりするため、行われている。 | ||
+ | |||
+ | * 下記ページ中の「コンパイルコマンド」がコンパイルフェーズに実行される | ||
+ | * [[https:// | ||
+ | |||
+ | Pythonでは '' | ||
+ | Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。 | ||
+ | </ | ||
つまり、以下のいずれかを行えばよい。 | つまり、以下のいずれかを行えばよい。 | ||
行 292: | 行 300: | ||
* AOTは、コンパイルと本処理で処理が明確に異なるため、切り分ける必要があり、記述が多少ごちゃごちゃしてしまう | * AOTは、コンパイルと本処理で処理が明確に異なるため、切り分ける必要があり、記述が多少ごちゃごちゃしてしまう | ||
* JITは関数に '' | * JITは関数に '' | ||
- | * ローカル環境でのテスト実行 | + | * ローカル環境での実行 |
* ローカル環境でAOT用のコードをジャッジシステムと同様に動かそうと思えば、コンパイルと本処理で2回実行することになる。それは面倒なので他の方法を採るにしろ、やはり多少、専用の記述が必要になる | * ローカル環境でAOT用のコードをジャッジシステムと同様に動かそうと思えば、コンパイルと本処理で2回実行することになる。それは面倒なので他の方法を採るにしろ、やはり多少、専用の記述が必要になる | ||
* JITは、ローカルでも提出コードで同じように動く | * JITは、ローカルでも提出コードで同じように動く | ||
* 実行速度 | * 実行速度 | ||
- | * AOTは、本処理時にはコンパイルした結果のみ読み込めばよい | + | * AOTは、本処理時にはコンパイルしたモジュールのみ読み込めばよい |
- | * JITは常にNumbaライブラリを読み込む必要があり、環境にも依るが~100ms程度は余分にかかる | + | * JITはNumbaライブラリ読み込みに加え、キャッシュの存在チェックなどが必要となり、環境にも依るが100ms程度は余分にかかる |
- | コードをスッキリと保ち、Numba用の改修を少なくしたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。 | + | コードをスッキリと保ちたいならJIT、ギリギリまで速度を求めたければAOT、でよいと思う。 |
- | === AtCoderのジャッジシステムの仕組み === | ||
- | |||
- | AtCoderのジャッジシステムでは、テストケース実行前に '' | ||
- | |||
- | * [[https:// | ||
- | |||
- | C言語などにとってのコンパイル処理をするフェーズだが、 | ||
- | スクリプト言語にとっても起動を速くする効果があったりするため、行われている。 | ||
- | |||
- | Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。 | ||
- | コンパイルフェーズで生成されたファイルは削除されず残る。 | ||
=== ローカル環境でのAOT === | === ローカル環境でのAOT === | ||
行 317: | 行 314: | ||
AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。 | AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。 | ||
- | AOTを用いる場合、コンパイルと本処理を切り分けると、2回実行する必要があり、煩わしい。 | + | AOTを用いる場合、ジャッジシステムでの挙動と同様にコンパイルと本処理を切り分けると、2回実行する必要があり、煩わしい。 |
- | 毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。 | + | また、1つのコンパイル結果をそんなに何回も使い回さない。 |
- | それならローカルではAOTでなくJITでいいよね、という話になる。 | + | それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。 |
- | 実際、AOTをローカル環境でやろうとすると、%%C++%%コンパイラが必要になる、JITよりも若干コンパイル時間がかかる、などあるので、手元ではJITの方で十分と感じる。 | + | さらに、それならローカルではAOTでなくJITでいいよね、という話になる。 |
+ | |||
+ | 実際、AOTをローカル環境でやろうとすると、%%C++%%コンパイラが必要、JITよりも若干コンパイル時間がかかる、などあるので、手元ではJITの方で十分と感じる。 | ||
OS環境はWindowsなら '' | OS環境はWindowsなら '' | ||
+ | これで切り分けて、ローカルならJITコンパイルして実行するようにスニペットを作っておく。 | ||
==== 入力受け取りと型指定 ==== | ==== 入力受け取りと型指定 ==== | ||
行 334: | 行 333: | ||
* [[https:// | * [[https:// | ||
- | |||
- | 上記のサンプルでは型指定用のクラスをimportして用いているが、型指定は文字列でも可能である。その方が余計なimportが不要になる。 | ||
厳密には、JITの場合は型指定せずとも動くのは動く。 | 厳密には、JITの場合は型指定せずとも動くのは動く。 | ||
- | ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない(つまり実行時にコンパイルされることになる)。 | + | ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない(つまり本来の意味での実行時コンパイルになる)。 |
型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。 | 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。 | ||
行 359: | 行 356: | ||
==== 関数を分ける ==== | ==== 関数を分ける ==== | ||
- | 処理の切り出しなどで複数の関数を書きたくなったとき、以下の2つがあるが、 | + | 処理の切り出しなどで関数を複数に分けたくなったとき、以下の2つがあるが、 |
- | * それぞれを個別にコンパイル | + | * それぞれをグローバルに書いて個別にコンパイル |
- | * 1つの大枠の関数の中で個々の関数定義も書いて、大枠の関数のみコンパイル | + | * 1つの大枠の関数の中で個々の関数定義を書いて、大枠の関数のみコンパイル(内部関数) |
前者は関数毎にコンパイル指定(JITなら'' | 前者は関数毎にコンパイル指定(JITなら'' | ||
後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 | 後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 | ||
- | 普通に後者でいいと今のところは思っている。 | + | ただし、内部関数が再帰を含む場合、コンパイルが通らない。 |
+ | |||
+ | numba.core.errors.NotDefinedError: | ||
+ | |||
+ | 通常は1つの大枠関数に入れた方が手間が少ないのでそうし、再帰関数のみ個別にコンパイルする。 | ||
==== 独自クラス ==== | ==== 独自クラス ==== | ||
行 375: | 行 377: | ||
AOTでのコンパイル方法は探したけど見つかってない。 | AOTでのコンパイル方法は探したけど見つかってない。 | ||
- | クラスは一連の処理をまとめて理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 | + | クラスは、1つのオブジェクトに関係する処理をまとめることで理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 |
* [[https:// | * [[https:// | ||
行 383: | 行 385: | ||
=== AOT === | === AOT === | ||
- | 以下を参照させていただいた。あまり変わっていないが、手元環境でも同一コードで動く。 | + | 以下を参照させていただいた。あまり変わっていないが、手元環境でも同一コードで動くようにした。 |
* [[https:// | * [[https:// | ||
- | 手元環境がWindowsであることを前提としており、'' | + | ローカル環境がWindowsであることを前提としており、'' |
- | MacやLinuxなら、'' | + | MacやLinuxなら、'' |
基本的に '' | 基本的に '' | ||
- | |||
- | 処理を切り分けるものの、見た目的にあまり階層は深くしたくない。参照させていただいたコードはその点も配慮されていて、メインで記述する箇所が十分浅く、書きやすい。 | ||
++++ 実装例 | | ++++ 実装例 | |