差分
このページの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でも '' | ||
それを用いると自動的にコンパイル結果をファイルとして保存し、以前のコンパイル結果があればそれを利用することができる。実質AOT。 | それを用いると自動的にコンパイル結果をファイルとして保存し、以前のコンパイル結果があればそれを利用することができる。実質AOT。 | ||
+ | ((キャッシュファイルは、スクリプトと同階層の '' | ||
* [[http:// | * [[http:// | ||
+ | |||
+ | |||
+ | <WRAP center round box> | ||
+ | AtCoderのジャッジシステムでは、Pythonはテストケース実行前に '' | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | C言語などにとってのコンパイル処理をするフェーズだが、 | ||
+ | スクリプト言語にとっても起動を速くする効果があったりするため、行われている。 | ||
+ | |||
+ | Numbaでのコンパイルも、このコンパイルフェーズを利用して行う。 | ||
+ | コンパイルフェーズで生成されたファイルは削除されず残る。 | ||
+ | </ | ||
+ | |||
つまり、以下のいずれかを行えばよい。 | つまり、以下のいずれかを行えばよい。 | ||
行 291: | 行 303: | ||
* 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 === | ||
- | AOTでもなるべく提出コードを変えずにローカルでも動くようにしたい。(JITなら普通に書けば特に支障なく可能) | + | AOTの方を採用する場合でも、なるべく提出コードを変えずにローカルで動くようにしたい。 |
- | AOTを用いる場合、コンパイルと本処理を切り分けると、2回実行する必要があり、煩わしい。 | + | AOTを用いる場合、ジャッジシステムでの挙動と同様にコンパイルと本処理を切り分けると、2回実行する必要があり、煩わしい。 |
- | 毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。 | + | また、1つのコンパイル結果をそんなに何回も使い回さない。 |
- | それならローカルではAOTでなくJITでいいよね、という話になる。 | + | それなら、毎回数秒かかってしまうが、常にコンパイル→本処理と1回で流すようにする方が楽。 |
- | 実際、AOTをローカル環境でやろうとすると、%%C++%%コンパイラが必要になる、JITよりも若干コンパイル時間がかかる、などあるので、手元ではJITの方で十分と感じる。 | + | さらに、それならローカルではAOTでなくJITでいいよね、という話になる。 |
- | Pythonによる環境の判定は、Windowsなら '' | + | 実際、AOTをローカル環境でやろうとすると、%%C++%%コンパイラが必要、JITよりも若干コンパイル時間がかかる、などあるので、手元ではJITの方で十分と感じる。 |
+ | OS環境はWindowsなら '' | ||
+ | これで切り分けて、ローカルならJITコンパイルして実行するようにスニペットを作っておく。 | ||
==== 入力受け取りと型指定 ==== | ==== 入力受け取りと型指定 ==== | ||
行 331: | 行 333: | ||
Numba関数内ではinput()など入力受け取り関数は使えない。素のPythonで受け取って、引数として与える必要がある。 | Numba関数内ではinput()など入力受け取り関数は使えない。素のPythonで受け取って、引数として与える必要がある。 | ||
- | 引数を取る関数をコンパイルするには、その型を指定してやる必要がある。 | + | そして、関数をコンパイルするには、引数と戻り値の型を指定してやる必要がある。 |
- | AOTでは必須。 | + | * [[https:// |
- | JITでは指定せずとも実際に関数が呼ばれたときに自動推論されるが、逆に呼ばれるまでされない(つまり実行時にコンパイルされることになる)。 | + | 厳密には、JITの場合は型指定せずとも動くのは動く。 |
+ | ただしその場合、実際に関数が呼ばれたタイミングで自動推論→コンパイルされるのであり、逆に言えば呼ばれるまでされない(つまり本来の意味での実行時コンパイルになる)。 | ||
型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。 | 型指定すれば定義された時点でコンパイルされるので、コンパイルフェーズに行いたければやはり型を指定する必要がある。 | ||
=== 入力の共通化 === | === 入力の共通化 === | ||
- | 毎回きちんと指定してやるのは手間だし、間違いも起こりやすい。 | + | 毎回きちんと型指定するのは手間だし、どう書けばいいんだっけ、と間違いも起こりやすい。 |
AtCoderでは、文字列を含まない問題の入力は全て整数であることが多い。 | AtCoderでは、文字列を含まない問題の入力は全て整数であることが多い。 | ||
行 347: | 行 350: | ||
inp = np.fromstring(sys.stdin.readline(), | inp = np.fromstring(sys.stdin.readline(), | ||
- | これを唯一の引数とするようにNumba関数を作ると、型指定は常に ''' | + | これを唯一の引数とするようにNumba関数を作ると、型指定は常に ''' |
- | 入力受け取り処理やNumbaへの型指定を問題に合わせて変更する必要が無くなり、「Numba関数の中身だけ書けばいい」という状態にできる。 | + | 問題に合わせて変更する箇所が少なくなり、「Numba関数の中身だけ書けばいい」という状態にできる。 |
- | 例外的に、小数を含む場合や、文字列を含むが前処理してNumbaに任せたい場合などは、仕方ないのでその都度、型を適切に合わせることにする。 | + | 小数や文字列を含む場合などは、共通化しにくいのでその都度、型を適切に合わせることにする。 |
行 359: | 行 362: | ||
* それぞれを個別にコンパイル | * それぞれを個別にコンパイル | ||
- | * 1つの大枠の関数の中で個々の関数定義も書いて、大枠の関数のみコンパイル | + | * 1つの大枠の関数の中で個々の関数定義も書いて、大枠の関数のみコンパイル(関数内関数) |
前者は関数毎にコンパイル指定(JITなら'' | 前者は関数毎にコンパイル指定(JITなら'' | ||
後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 | 後者は大枠関数のみの指定で特に問題なく内部の関数も型推論してくれる。 | ||
- | 普通に後者でいいと今のところは思っている。 | + | ただし、Numbaの内部関数が再帰を含む場合、それはコンパイルが通らない。 |
+ | |||
+ | numba.core.errors.NotDefinedError: | ||
+ | |||
+ | 通常は1つの大枠関数に入れた方が手間が少ないのでそうし、再帰関数のみ個別にコンパイルする。 | ||
==== 独自クラス ==== | ==== 独自クラス ==== | ||
行 372: | 行 380: | ||
AOTでのコンパイル方法は探したけど見つかってない。 | AOTでのコンパイル方法は探したけど見つかってない。 | ||
- | クラスは一連の処理をまとめて理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 | + | クラスは、1つのオブジェクトに関係する処理をまとめることで理解しやすくしてくれる点はあるが、競プロのような短いコードでは必須でもないので、今のところはクラスを使わない書き方で対処する方針で。 |
* [[https:// | * [[https:// |