numpyでvstackするかbuilt-inのlistから変換するか
Pythonには，数値計算，特にベクトル行列演算を高速かつ便利におこなう
numpyと呼ばれる強烈なライブラリがあります．
しかし，numpyのarray (Cの配列のようなものと考えて問題ない）は，
ベクトル行列演算をpythonのforループを用いた演算よりも果てしなく高速に実行できるのですが，
要素アクセスやメモリアロケーションを頻繁におこなったりすると
pythonのlistを使ったforループに速度で負けることがよくあります．
今回の問題は次のような設定です：
int型からなるnumpyのarray：labelsと，
float型からなるnumpyのarray：valuesが与えられる．
これらのarrayの長さは等しいものとする．
valuesについて，labelsの値の等しいインデックスの要素の和をそれぞれ計算せよ．
わかりづらいので，具体例で示すと：
labels = np.array([0, 0, 1, 1, 2, 2, 0 ]) values = np.array([0.1,0.2,0.3,0.4,0.5,0.6,0.7]) # results = np.array([0.1+0.2+0.7, 0.3+0.4, 0.5+0.6])
と，同じラベルを持つvaluesの要素をそれぞれ足しあわせた配列を結果として要求します．
これを解くために，いくつか解法を考えました．
その1：numpyの比較演算子をループ中で用いて，sliceを使って配列を切り出して足し合わせる方法
def naive_comp(labels, values, nof_labels): new_values = np.empty(nof_labels) for l in xrange(nof_labels): new_values[l] = values[labels==l].sum() return new_values
その2：numpyの比較演算子をループ中で用いて，内積をとる方法
def naive_dot(labels, values, nof_labels): new_values = np.empty(nof_labels) for l in xrange(nof_labels): new_values[l] = np.dot(values, labels==l) return new_values
その3：new_valuesへの要素アクセスを避けるため，numpy.vstackを用いて行列を前もって構築して行列積をとる方法
def vstack(labels, values, nof_labels): stacked_bool = (labels == 0) for l in xrange(1, nof_labels): stacked_bool = np.vstack((stacked_bool, labels==l)) return np.dot(values, stacked_bool.T)
その4：new_valuesへの要素アクセスを避けるため，list.appendを用いて行列を前もって構築して行列積をとる方法
def builtinlist(labels, values, nof_labels): listofbools = list() for l in xrange(nof_labels): listofbools.append(labels==l) stacked_bool = np.array(listofbools) return np.dot(values, stacked_bool.T)
また，labelsとvaluesは次のように構築します：
length = 1000 nof_labels = 20 labels = np.random.randint(nof_labels, size=length) values = np.random.random(size=length)
長さ1000，ラベルの種類20程度の小ささならばほぼ実行時間に違いはありませんでしたが，
長さやラベルの種類の数を増やすと実行時間に差が出始めます．
| length=1000, nof_labels=20 | length=100000, nof_labels=200 | length=200000, nof_labels=1000 | |
| naive_comp | 0.00022 | 0.043965 | 0.390768 |
| naive_dot | 0.000147 | 0.048827 | 0.478222 |
| vstack | 0.000352 | 0.479748 | 18.735946 |
| builtinlist | 0.000365 | 0.312864 | 3.148327 |
vstackは，lengthが大きくなってメモリが限界に近づくと露骨にパフォーマンスが落ちます．
巨大な行列を構築するときは，行列をだんだん成長させていくやり方だと
毎回メモリの再配置が行われて非常に非効率になります．
むしろ組み込みのリストで行列（のような何か）を作ってからそれをnumpy形式に変換した
ほうがずっと速くなります．
まとめ．
個人的には，builtinlist関数が一番速いんじゃないかと思っていましたが，
実際は一番遅いと思っていたnaive_compが最高速を記録しました．
下2つが上2つに負けた理由は，メモリアロケーションのせいだということは
想像がつくのですが，
上2つの中でnaive_dotがnaive_compに負けた理由がイマイチわかりません．
naive_dotは直接内積を計算しにかかるので，（内部の実装がどうなっているのか
確認していませんが）普通はメモリを新たに要求しないはずです．
一方，naive_compはいちいち新たなarrayを構築してそのsumをとっていますので，
毎回メモリを要求しています．
基本的にはメモリを要求しないほうが速いのですが，
この場合はnumpyのfancy indexingが非常に優秀ということなのでしょう．
特に，今回はTrue/Falseのarrayでindexingをしていますので，特別高速なのかもしれません*1．
「numpyの要素アクセスは遅いからできるだけ避けろ」
「numpyのfancy indexingは便利だが使い方によってはボトルネックになるから気をつけろ」
というようなことをよく聞きますが，今回に限ってはその原則に従わず，
内積よりもfancy indexingを使ったほうが速いという結果になりました．
「numpyで計算するときにどうすれば速いか，という問題に一般的な答えはなく，
問題の特性に大きく依存する」
という，これもまたよく聞く内容を確かめる結果となりました．
ちなみに，巷で噂のpypy*2で同じように実験してみた結果，次のようになりました：
| length=1000, nof_labels=20 | length=100000, nof_labels=200 | length=200000, nof_labels=1000 | |
| naive_comp | 0.006402 | 0.182519 | 1.772592 |
| naive_dot | 0.003382 | 0.515398 | 4.860914 |
| vstack | 0.004108 | 5.220479 | 232.755964 |
| builtinlist | 0.003341 | 2.476905 | 24.333794 |
うーん・・・
今回はほとんどの計算がnumpyの範疇なので，pypyの得意分野ではないようです*3．
