AtCoderでnumpyを使いたい

numpyを使いたい理由

自分の研究で計測実験を日々行っており、excelでのデータ整理・解析に限界を感じていた。やむなくpythonに手を出して勉強するうちに、科学技術の分野でnumpyが良く使われているというのを知った。画像処理をやることもあるのだが、そちらで使われるopenCVをにもnumpyが必須。自分がやりたいデータ解析は、ほとんどの場合numpyのブロードキャストを使った配列の定数倍と足し算引き算で済むのだが、たまに別の解析をしたいこともある。そんなときもたいていはnumpyの関数使うと解決した。
プログラムをもう少し勉強したいのとnumpyに慣れたいと思いAtCoderを始めた。解説記事にはnumpy早いとかよく見るが、実際にnumpyをAtCoderで使っている人は多くない気がする。自分がハマるC問題D問題以降は他の人の回答見ると圧倒的にpypyでの提出が多い。pypyとnumpyは同時に使えないようで、高速化目的では多くの人はpypyを選択しているようである。問題によってはpythonの解答例自体が少なく、python使っている人もnumbaのJIT/AOTで高速化していて、numpy使って問題解いている人があまり多くない。勉強にと思って始めたが、参考になる解答例が少ないことがある。どうもnumpy使う場合はある程度自分で考えないとダメらしい。どうやってfor文while文を削ってnumpy関数で処理するか、というところを毎回悩んでいる。ときおり、こんな便利な関数があるんだ、というような発見があったときは嬉しい。

numpyの注意点

• 配列サイズは頻繁に変化させてはいけない
  要素の追加・削除を頻繁に行う場合はpython組み込みのlist, setを使う。for文の中で毎回要素数の異なるnumpy配列を作っていると遅い。np.stack関数で複数のnumpy配列を結合する場合も、元の配列が巨大だとメモリの確保に時間がかかる？配列サイズが分かっているなら、最初から要素数の大きい配列を初期化して用意しておいた方が良い。
• 要素数の異なる多次元リストはnumpy配列にできない
  たまに要素数が一定でない問題に出くわす。どうしてもnumpyで処理したい場合はダミーの要素を追加してからnumpy配列にする等工夫がいる。
• 配列の一部要素のみを頻繁に指定する必要がある場合はlistのほうが良い
  大きな配列のうち一部の要素にしかアクセスしないような場合、numpyだと遅くなる。for文で顕在化。numpy使うときは配列全体の更新をするような計算を心がける。
• numpyとlistの変換を頻繁に行ってはいけない
  listのほうが早い処理があっても、numpyとlistの変換に時間がかかるため、for文の中で変えない方が良い。途中・最後に数回だけ変換するような処理を考える。
• for文はなるべく使わない
  そもそもfor文を使わなくとも良いようにnumpy使っているので、numpy使う処理を10^5回行うようなfor文ならnumpy使わない方が良い。ただしどうしても使わないといけない場面は出てくる。numpy配列が10^4台でfor文が10^3回の繰り返しくらいなら、見た目10^7回の演算で不安だが意外と高速。こういうコードが通るとnumpy凄いと思う。
• 要素は数値に変換
  文字列もnumpy配列にできるが処理はあまり得意では無さそう。np.where等で文字列を数値に変換してから処理すること。True,Falseのbool型であればnumpyでも高速。

よく使う関数 Sort系

a_sort=np.sort(a,kind="stable")
ind=np.argsort(a,kind="stable") #ind: index
a_sort=a[ind]
ind2=np.lexsort((c,b,a))

sortはsort済みの配列を、argsortはsortした添え字の順番を返す。順番を覚えておきたいときはargsortで添え字を出力しておく。デフォルトだと元の配列の順番が入れ替わりたまに意図しない結果になることがあるので、kind="stable"オプションで安定ソートを使った方が良い。このオプションで遅くなって困る、ということは基本的に無いと思うので、kind="stable"は毎回指定しておいた方が無難。
lexsortは複数の配列を優先順位決めてsortするときに使う。添え字を返すので、実際のsort済み配列を得るには、返された添え字配列を元のnumpy配列の添え字に指定する。後ろに指定した配列ほどsortの優先順位が高い。上の例だとa→b→cの順でsortする。lexsortはあまり早くない気がする。

二分探索 np.searchsorted

ind=np.searchsorted(a,b)

AtCoderの問題で出るような10^6程度の配列だと、python組み込みのbisectのほうが早いらしい。numpyの利点は、探索する数値に配列を指定できること。上の例ではbに数値ではなく配列を代入することで、それらが挿入されるaのindexを一度にまとめて処理できる。bに配列を使えるとnumpyで処理した感が出る。

配列初期化

a=np.zeros((n,),dtype=np.int)
b=np.ones((n,),dtype=np.int)
c=np.fill((n,),c0,dtype=np.int)
d=np.empty((n,),dtype=np.int)

要素数nの1次元配列の初期化例。zerosは初期値に0が代入される。onesは1,fullはc0が代入される。emptyは何が代入されるか分からないらしいがメモリ確保が最も高速。極限まで速さを追求するのでなければ基本zerosを使えば良いと思う。dtypeはデフォルトでは浮動小数点型。AtCoderでは多くの場合整数を扱うことが多いのでdtypeを指定する。np.intは64byteなので、普通に使う分にはオーバーフローしない。ただしpythonで使う整数と違い、2^64を超えるとnp.intではオーバーフローするはず。結構大きいサイズの配列でも、np.int64とnp.int8で計算速度はほとんど変わらないので、メモリ節約の目的がないのであればnp.intで良いと思う。実際の計測データだと巨大なデータを保持するのに必要なメモリが2GBか16GBでPCの要求スペックが変わるので、配列中の要素の最大値が256や2^16=65536未満であることが分かっているなら、np.int8やnp.int16を使う理由は十分ある。

座標圧縮もできるnumpy.unique

配列中の要素の出現回数を数えるのに使う関数。return_counts, return_index, return_inverse等いくつかオプションがあり毎回google検索している。

u,inverse=np.unique(a,return_inverse=True)

とすると、inverseは元の配列を座標圧縮した配列になっているはず。