[numpy][python 計測] 出現件数の集計

スポンサーリンク

np.unique

Counterと同様の集計が、numpy arrayに対しても行えます。np.unique を使うことができます。名称からは、重複を除いて一意化するようなメソッドであると推測できますが、return_counts オプションを指定することで、出現件数も受け取ることができます。

(2019/06/16現在、AtCoderのnumpyでは、バージョン違いによりreturn_countsは利用できません。)

他にも、各キーが元のarrayの何番目に現れたのかのインデックスなどを戻り値に含めることもできます。詳しくはこちらから。

np.bincount

類似のメソッドに、np.bincountがあります。これは、インデックス $n$ に対して $n$ の出現件数を書き込んだarrayを返します。

arrayの長さは、集計する整数の最大値 + 1となります。上の実行例を見れば分かるように、$10\leqq n < 20$ を満たす$n$が一切出現しない場合でもその部分が $0$ 埋めされて返ることになります。例えば元のarrayが $10^9$ 以下の整数からなる場合などに使用すると、膨大なメモリを使用することになってしまうため、注意が必要です。また、重みをつけた集計なども可能です。詳しくはこちら

パフォーマンス比較


ポイント
・狭い範囲に大量の値がある場合には、np.bincountのパフォーマンスが圧倒的。
(1度arrayを作ってさえしまえば、大量に $0$ 値を持っていても負荷にならない)
・ただし、集計値の範囲が広くなるとメモリを膨大に使う。

例題:AtCoder ABC 72 C

もうちょっと題材に適した例題があると思いますが、たまたま本問題を解いているときに記事にしようと思ったので。

・問題文 →
・自分の提出 →

0.15秒程度を「import numpy as np」の1文に使うため、AtCoder環境の易問では、numpy解法の実行速度が他の解法を上回ることは少ないです。しかしながら実際にはメインの処理部分はかなり速く実行できるため、ループを回すよりもTLEに強い解法となっています。

タイトルとURLをコピーしました