48

大きな配列にゼロ以外の値が少なくとも 1 つ含まれているかどうかを判断する最も効率的な方法を探しています。一見したところnp.any、この仕事のための明らかなツールのように見えますが、大規模な配列では予想外に遅く見えます。

この極端なケースを考えてみましょう:

first = np.zeros(1E3,dtype=np.bool)
last = np.zeros(1E3,dtype=np.bool)

first[0] = True
last[-1] = True

# test 1
%timeit np.any(first)
>>> 100000 loops, best of 3: 6.36 us per loop

# test 2
%timeit np.any(last)
>>> 100000 loops, best of 3: 6.95 us per loop

少なくともnp.any、ここでは漠然と賢明なことをしているようです - ゼロ以外の値が配列の最初の値である場合、 を返す前に他の値を考慮する必要はないはずなTrueので、テスト 1 はテスト 2 よりもわずかに速いと予想されます。

しかし、配列をもっと大きくするとどうなるでしょうか?

first = np.zeros(1E9,dtype=np.bool)
last = np.zeros(1E9,dtype=np.bool)

first[0] = True
last[-1] = True

# test 3
%timeit np.any(first)
>>> 10 loops, best of 3: 21.6 ms per loop

# test 4
%timeit np.any(last)
>>> 1 loops, best of 3: 739 ms per loop

予想どおり、テスト 4 はテスト 3 よりかなり遅いです。ただし、テスト 3 では、 ゼロ以外の値が少なくとも 1 つ含まれていることを知るためにnp.any、単一の要素の値をチェックするだけで済み ます。firstでは、なぜテスト 3 はテスト 1 よりもずっと遅いのでしょうか?

編集1：

Numpy の開発バージョン (1.8.0.dev-e11cd9b) を使用していますが、Numpy 1.7.1 を使用してもまったく同じタイミング結果が得られます。64 ビット Linux、Python 2.7.4 を実行しています。私のシステムは基本的にアイドリング状態 (私は IPython セッション、ブラウザー、およびテキスト エディターを実行しています) であり、間違いなくスワップにヒットしていません。Numpy 1.7.1 を実行している別のマシンでも結果を複製しました。

編集2：

Numpy 1.6.2 を使用すると、テスト 1 と 3 の両方で ~1.85us の時間が得られるため、jorgeca が言うように、この点に関して Numpy 1.6.2 と1.7.1 1.7.0 の間にパフォーマンスの低下があったようです。

編集3：

JF Sebastian と jorgeca のリードに従って、ゼロの配列を使用してさらにベンチマークを行いました。これは、最初の要素が 1 である配列np.allを呼び出すのと同じはずです。np.any

テスト スクリプト:

import timeit
import numpy as np
print 'Numpy v%s' %np.version.full_version
stmt = "np.all(x)"
for ii in xrange(10):
    setup = "import numpy as np; x = np.zeros(%d,dtype=np.bool)" %(10**ii)
    timer = timeit.Timer(stmt,setup)
    n,r = 1,3
    t = np.min(timer.repeat(r,n))
    while t < 0.2:
        n *= 10
        t = np.min(timer.repeat(r,n))
    t /= n
    if t < 1E-3:
        timestr = "%1.3f us" %(t*1E6)
    elif t < 1:
        timestr = "%1.3f ms" %(t*1E3)
    else:
        timestr = "%1.3f s" %t
    print "Array size: 1E%i, %i loops, best of %i: %s/loop" %(ii,n,r,timestr)

結果：

Numpy v1.6.2
Array size: 1E0, 1000000 loops, best of 3: 1.738 us/loop
Array size: 1E1, 1000000 loops, best of 3: 1.845 us/loop
Array size: 1E2, 1000000 loops, best of 3: 1.862 us/loop
Array size: 1E3, 1000000 loops, best of 3: 1.858 us/loop
Array size: 1E4, 1000000 loops, best of 3: 1.864 us/loop
Array size: 1E5, 1000000 loops, best of 3: 1.882 us/loop
Array size: 1E6, 1000000 loops, best of 3: 1.866 us/loop
Array size: 1E7, 1000000 loops, best of 3: 1.853 us/loop
Array size: 1E8, 1000000 loops, best of 3: 1.860 us/loop
Array size: 1E9, 1000000 loops, best of 3: 1.854 us/loop

Numpy v1.7.0
Array size: 1E0, 100000 loops, best of 3: 5.881 us/loop
Array size: 1E1, 100000 loops, best of 3: 5.831 us/loop
Array size: 1E2, 100000 loops, best of 3: 5.924 us/loop
Array size: 1E3, 100000 loops, best of 3: 5.864 us/loop
Array size: 1E4, 100000 loops, best of 3: 5.997 us/loop
Array size: 1E5, 100000 loops, best of 3: 6.979 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.196 us/loop
Array size: 1E7, 10000 loops, best of 3: 116.162 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.112 ms/loop
Array size: 1E9, 100 loops, best of 3: 11.061 ms/loop

Numpy v1.7.1
Array size: 1E0, 100000 loops, best of 3: 6.216 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.257 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.318 us/loop
Array size: 1E3, 100000 loops, best of 3: 6.247 us/loop
Array size: 1E4, 100000 loops, best of 3: 6.492 us/loop
Array size: 1E5, 100000 loops, best of 3: 7.406 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.426 us/loop
Array size: 1E7, 10000 loops, best of 3: 115.946 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.102 ms/loop
Array size: 1E9, 100 loops, best of 3: 10.987 ms/loop

Numpy v1.8.0.dev-e11cd9b
Array size: 1E0, 100000 loops, best of 3: 6.357 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.399 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.425 us/loop
Array size: 1E3, 100000 loops, best of 3: 6.397 us/loop
Array size: 1E4, 100000 loops, best of 3: 6.596 us/loop
Array size: 1E5, 100000 loops, best of 3: 7.569 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.445 us/loop
Array size: 1E7, 10000 loops, best of 3: 115.109 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.094 ms/loop
Array size: 1E9, 100 loops, best of 3: 10.840 ms/loop

編集4：

seberg のコメントに従って、のnp.float32代わりに配列を使用して同じテストを試みましたnp.bool。この場合、Numpy 1.6.2 も配列サイズが大きくなるにつれて速度が低下します。

Numpy v1.6.2
Array size: 1E0, 100000 loops, best of 3: 3.503 us/loop
Array size: 1E1, 100000 loops, best of 3: 3.597 us/loop
Array size: 1E2, 100000 loops, best of 3: 3.742 us/loop
Array size: 1E3, 100000 loops, best of 3: 4.745 us/loop
Array size: 1E4, 100000 loops, best of 3: 14.533 us/loop
Array size: 1E5, 10000 loops, best of 3: 112.463 us/loop
Array size: 1E6, 1000 loops, best of 3: 1.101 ms/loop
Array size: 1E7, 100 loops, best of 3: 11.724 ms/loop
Array size: 1E8, 10 loops, best of 3: 116.924 ms/loop
Array size: 1E9, 1 loops, best of 3: 1.168 s/loop

Numpy v1.7.1
Array size: 1E0, 100000 loops, best of 3: 6.548 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.546 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.804 us/loop
Array size: 1E3, 100000 loops, best of 3: 7.784 us/loop
Array size: 1E4, 100000 loops, best of 3: 17.946 us/loop
Array size: 1E5, 10000 loops, best of 3: 117.235 us/loop
Array size: 1E6, 1000 loops, best of 3: 1.096 ms/loop
Array size: 1E7, 100 loops, best of 3: 12.328 ms/loop
Array size: 1E8, 10 loops, best of 3: 118.431 ms/loop
Array size: 1E9, 1 loops, best of 3: 1.172 s/loop

なぜこれが起こる必要がありますか？ブール値の場合と同様に、np.all返される前に最初の要素をチェックするだけでよいため、時間は配列サイズに関して一定である必要があります。

4

1 に答える 1

31

コメントで推測されているように、配列の処理がチャンクで行われていることが確認できます。最初に、コードのどこにあるのかを示し、次にチャンク サイズを変更する方法と、それがベンチマークに与える影響を示します。

Numpy ソース ファイルのどこにリダクション処理がありますか

np.all(x) は x.all() と同じです。all() は実際には np.core.umath.logical_and.reduce(x) を呼び出します。

numpy のソースを掘り下げたい場合は、バッファー/チャンク サイズが使用されていることを確認する方法を説明します。確認するすべてのコードを含むフォルダーは、numpy/core/src/umath/ です。

ufunc_object.c の PyUFunc_Reduce() は、reduce を処理する C 関数です。PyUFunc_Reduce() では、PyUFunc_GetPyValues() 関数 (ufunc_object.c) を介して何らかのグローバル ディクショナリで reduce の値を検索することにより、チャンク (またはバッファー) のサイズが検出されます。私のマシンで、開発ブランチからコンパイルすると、チャンク サイズは 8192 です。reduction.c の PyUFunc_ReduceWrapper() は、反復子をセットアップするために呼び出され (チャンク サイズに等しいストライドで)、渡されたループ関数を呼び出します。 ufunc_object.c の reduce_loop() です。

reduce_loop() は基本的にイテレータを使用し、チャンクごとに別の innerloop() 関数を呼び出します。innerloop 関数は loops.c.src にあります。ブール配列と all/logical_and の場合、適切なインナーループ関数は BOOL_logical_and です。BOOLEAN LOOPS を検索することで適切な関数を見つけることができます。それはその下の 2 番目の関数です (ここで使用されているテンプレートのようなプログラミングのため、見つけるのは困難です)。そこでは、短絡が実際に各チャンクに対して行われていることがわかります。

ufunctions で使用されるバッファ サイズを変更する方法 (したがって、任意/すべてで)

np.getbuffersize() でチャンク/バッファサイズを取得できます。私にとっては、手動で設定せずに8192を返します。これは、コードのバッファサイズを出力して見つけたものと一致します。np.setbuffersize() を使用してチャンク サイズを変更できます。

より大きなバッファ サイズを使用した結果

ベンチマーク コードを次のように変更しました。

import timeit
import numpy as np
print 'Numpy v%s' %np.version.full_version
stmt = "np.all(x)"
for ii in xrange(9):
    setup = "import numpy as np; x = np.zeros(%d,dtype=np.bool); np.setbufsize(%d)" %(10**ii, max(8192, min(10**ii, 10**7)))
    timer = timeit.Timer(stmt,setup)
    n,r = 1,3
    t = np.min(timer.repeat(r,n))
    while t < 0.2:
        n *= 10
        t = np.min(timer.repeat(r,n))
    t /= n
    if t < 1E-3:
        timestr = "%1.3f us" %(t*1E6)
    elif t < 1:
        timestr = "%1.3f ms" %(t*1E3)
    else:
        timestr = "%1.3f s" %t
    print "Array size: 1E%i, %i loops, best of %i: %s/loop" %(ii,n,r,timestr)

Numpy はバッファ サイズが小さすぎたり大きすぎたりするのを好まないので、Numpy は 1E8 のバッファ サイズを好まなかったため、8192 よりも小さくなったり 1E7 よりも大きくなったりしないようにしました。それ以外の場合は、バッファ サイズを処理中の配列のサイズに設定していました。私のマシンには現在4GBのメモリしかないため、1E8までしか上がりませんでした。結果は次のとおりです。

Numpy v1.8.0.dev-2a5c2c8
Array size: 1E0, 100000 loops, best of 3: 5.351 us/loop
Array size: 1E1, 100000 loops, best of 3: 5.390 us/loop
Array size: 1E2, 100000 loops, best of 3: 5.366 us/loop
Array size: 1E3, 100000 loops, best of 3: 5.360 us/loop
Array size: 1E4, 100000 loops, best of 3: 5.433 us/loop
Array size: 1E5, 100000 loops, best of 3: 5.400 us/loop
Array size: 1E6, 100000 loops, best of 3: 5.397 us/loop
Array size: 1E7, 100000 loops, best of 3: 5.381 us/loop
Array size: 1E8, 100000 loops, best of 3: 6.126 us/loop

バッファ サイズの制限により複数のチャンクが処理されるため、最後のタイミングでわずかな上昇があります。

于 2013-06-17T04:34:39.160 に答える