4

ランダムなnumpy配列があるとします:

X = np.arange(1000)

およびしきい値:

thresh = 50

X2 つのパーティションに分割しX_l、のX_rすべての要素が よりもX_l小さいか等しいように分割したいと考えています。その後、これら 2 つのパーティションが再帰関数に渡されます。threshX_rthresh

numpy を使用してブール配列を作成し、それを使用してパーティションを分割しXます。

Z = X <= thresh
X_l, X_r = X[Z == 0], X[Z == 1]
recursive_call(X_l, X_r)

これは数回行われますが、物事をより速くする方法はありますか? 各呼び出しでパーティションのコピーを作成しないようにすることは可能ですか?

4

2 に答える 2

7

X[~Z]は よりも高速ですX[Z==0]:

In [13]: import numpy as np

In [14]: X = np.random.random_integers(0, 1000, size=1000)

In [15]: thresh = 50

In [18]: Z = X <= thresh

In [19]: %timeit X_l, X_r = X[Z == 0], X[Z == 1]
10000 loops, best of 3: 23.9 us per loop

In [20]: %timeit X_l, X_r = X[~Z], X[Z]
100000 loops, best of 3: 16.4 us per loop

これが実際にコードのボトルネックであることを確認するためにプロファイリングしましたか? コードがこの分割操作に 1% の時間しか費やしていない場合、この操作をどれだけ最適化しても、全体的なパフォーマンスには 1% しか影響しません。

この 1 つの操作を最適化するよりも、アルゴリズムまたはデータ構造を再考することで、より多くのメリットが得られる場合があります。そして、これが本当にボトルネックである場合は、このコードを CまたはCythonで書き直したほうがよいかもしれません...

サイズが 1000 の numpy 配列がある場合、Python のリスト/セット/辞書を使用した方が速い可能性があります。NumPy 配列の速度の利点は、配列がかなり大きくなるまで明らかにならないことがあります。純粋な Python でコードを書き直し、2 つのバージョンをtimeitでベンチマークすることをお勧めします。

うーん、言い直そう。NumPy を速くしたり遅くしたりするのは、実際には配列のサイズではありません。小さな NumPy 配列を持つことは、多くの小さな NumPy 配列を作成している兆候である場合があり、NumPy 配列の作成は、たとえば Python リストの作成よりも大幅に遅くなります。

In [21]: %timeit np.array([])
100000 loops, best of 3: 4.31 us per loop

In [22]: %timeit []
10000000 loops, best of 3: 29.5 ns per loop

In [23]: 4310/295.
Out[23]: 14.610169491525424

また、純粋な Python でコーディングする場合は、NumPy に直接対応するものがない辞書とセットを使用する可能性が高くなります。これにより、より高速な代替アルゴリズムにつながる可能性があります。

于 2013-09-25T12:02:40.363 に答える
1

あなたの配列は常にすでにソートされていますか? あなたの例arangeでは、ソートされているため、ブール値のインデックス付けを行う必要はありません。適切な場所で配列を半分にスライスするだけです。これにより、「高度なインデックス作成」の使用が回避されるため、配列をコピーする必要がなくなります。

X = np.arange(0, 2*thresh)
i = X.searchsorted(thresh, side='right') # side='right' for `<=`
X_l, X_r = X[:i], X[i:]

これにより、並べ替えられた配列の時間を大幅に節約できますが、それ以外の場合は明らかに機能しません。

thresh = 500
X = np.arange(2*thresh)

%%timeit
i = X.searchsorted(thresh, side='right')
X_l, X_r = X[:i], X[i:]
100000 loops, best of 3: 5.16 µs per loop

%%timeit
Z = X <= thresh                         
X_l, X_r = X[Z], X[~Z]
100000 loops, best of 3: 12.1 µs per loop
于 2013-09-25T13:48:58.657 に答える