背景
機械学習を学び始めて、Pythonに触れて、その流れで競技プログラミング（ほぼ AtCoder）も始めました。様々な問題や解法・考え方に触れはじめる段階では、解答が TLE となってもプログラムがまずいことが大半でしたが、最近は「解法はどうも合っている。どうやってTLEを回避したらいいかわからない」という状況にしばしば遭遇してきました。Pythonあるあるだと思います。
そんな時、 Pypy をとりあえず試せとあるのを見たり、AC の方のプログラムに Numba が使われていたりしました。それぞれにいろんな注意書きがあるものの、回避の仕方がわからないこと多く、その理解の前提となる「何しているの、これ」の知識も少なかったので、色々学んだメモです。
そもそも、Python のプログラム実行までの話を整理
Python 自体はプログラミング言語であって、インタープリタでもコンパイラでもない。Python というプログラミング言語のルールにそって、それを実行できる環境があれば良いわけです。インタープリタとして、通常は CPythonを指すことが多いようですが、当然それ以外にもあって。そして、その一つが CPython より高速に処理できる PyPy があります。
Pythonのインタープリタについてはこちらの記事をご参照ください。
Python はインタープリタ型言語だけど、コンパイルもある。
通常のスクリプトはインタープリタを介して走りますが、コンパイルが全く実行されないわけではない、というのが面白いところで、モジュール類は一旦コンパイルされています。毎回ではなく、更新があったらコンパイルして、そうでなければコンパイル済みのものを使う、ということのようです。
Pythonのコンパイル界隈の話はこちらのサイトをご参照ください。
そして、プログラム中でコンパイル（を指示）して、高速化するのが、Numba ということでしょうか。
Numba って何だ？
Numba
Numba - Wikipedia
numbaでざっくりPython高速化 - Qiita
ふんふん、要するにインタープリタ言語である Python をコンパイルして高速に動作するようにするのね。って、素直にそうですか、というほど知識のない入門者が理解できなかったのが、
- AOTって何？プログラムの中でコンパイルを指示しているのに「事前」ってどういうこと？
ということで、改めて調べてみた話。
AtCoder の提出の流れ
AtCoder で解答を提出すると、そのまま実行されるものだと思っていたのですが、改めてAtCoderのページを見てみると、実行コマンドだけではなく、コンパイル・インタープリタの欄にも記述がある。つまり、仮実行が走って、その後、本実行になる、ということで、この仮実行でコンパイルを掛けて、その情報を使えるようにしておく、というのが、AtCoder にて、Numbaを利用する流れになるということです。（毎回のコンパイルでも効果がある場合もあると思いますが）
ルール - practice contest AtCoder
Numba での実行の流れ
コンパイルの時点で @njit に catch=True でキャッシュしておいたり、コンパイル時の引数 ONLINE_JUDGE を使って、
if sys.argv[-1] == 'ONLINE_JUDGE':
というようなやり方が主流みたいです。
コードテストでも事前コンパイルは可能
ちなみに、ちゃんと事前にコンパイルは流れます。って、C++ とか Java とか考えたら、そうなっていないと困るよね。
終わりに
一通りの Numba の実行はできるようになりました。Numba の制約を理解していないとすぐに引っかかってしまうので、そのあたりは別途。
今まで見た中で、こちらが一番自分の引っ掛かりパターンについての説明が多かったと思います。
Numba のコンパイルが通らなかった時の対処
次は、自分のエラーパターンのメモ、残すつもりです。