背景

機械学習を学び始めて、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 のコンパイルが通らなかった時の対処

次は、自分のエラーパターンのメモ、残すつもりです。