7

ある配列の要素が別の配列で最初に出現する以下の要素のインデックスを見つける必要があります。機能する1つの方法は次のとおりです。

import numpy
a = numpy.array([10,7,2,0])
b = numpy.array([10,9,8,7,6,5,4,3,2,1])
indices = [numpy.where(a<=x)[0][0] for x in b]

インデックスの値は [0, 1, 1, 1, 2, 2, 2, 2, 2, 3] で、これが必要です。もちろん問題は、Python の "for" ループが遅く、配列に何百万もの要素が含まれている可能性があることです。これには派手なトリックはありますか?配列の長さが同じではないため、これは機能しません。

indices = numpy.where(a<=b) #XXX: raises an exception

ありがとう!

4

2 に答える 2

14

これは特殊なケースかもしれませんが、 numpy digitizeを使用できるはずです。ここでの注意点は、ビンが単調に減少または増加している必要があることです。

>>> import numpy
>>> a = numpy.array([10,7,2,0])
>>> b = numpy.array([10,9,8,7,6,5,4,3,2,1])

>>> indices = [numpy.where(a<=x)[0][0] for x in b]
[0, 1, 1, 1, 2, 2, 2, 2, 2, 3]

>>> numpy.digitize(b,a)
array([0, 1, 1, 1, 2, 2, 2, 2, 2, 3])

タイミング テストのセットアップ:

a = np.arange(50)[::-1]

b = np.random.randint(0,50,1E3)

np.allclose([np.where(a<=x)[0][0] for x in b],np.digitize(b,a))
Out[55]: True

いくつかのタイミング:

%timeit [np.where(a<=x)[0][0] for x in b]
100 loops, best of 3: 4.97 ms per loop

%timeit np.digitize(b,a)
10000 loops, best of 3: 48.1 µs per loop

2 桁のスピードアップのように見えますが、これはビンの数に大きく依存します。あなたのタイミングは異なります。


ジェイミーの答えと比較するために、次の2つのコードの時間を計りました。searchsorted主にvsの速度に注目したかったので、digitizeJamie のコードを少し減らしました。関連するチャンクは次のとおりです。

a = np.arange(size_a)[::-1]
b = np.random.randint(0, size_a, size_b)

ja = np.take(a, np.searchsorted(a, b, side='right', sorter=a)-1)

#Compare to digitize
if ~np.allclose(ja,np.digitize(b,a)):
    print 'Comparison failed'

timing_digitize[num_a,num_b] = timeit.timeit('np.digitize(b,a)',
                      'import numpy as np; from __main__ import a, b',
                      number=3)
timing_searchsorted[num_a,num_b] = timeit.timeit('np.take(a, np.searchsorted(a, b, side="right", sorter=a)-1)',
                      'import numpy as np; from __main__ import a, b',
                      number=3)

これは私の限られた matplotlib の能力を少し超えているので、これは DataGraph で行われます。の対数比をプロットしたtiming_digitize/timing_searchsortedので、0 より大きい値searchsortedは速く、0 より小さい値は速くなりますdigitize。色は相対速度も示します。たとえば、右上 (a = 1E6、b = 1E6)digitizeは約 300 倍遅く、searchsorted小さいサイズdigitizeでは最大 10 倍速くなることを示しています。黒い線はおおよそ損益分岐点です。

ここに画像の説明を入力searchsorted大規模なケースでは、生の速度はほとんどの場合高速である ように見えますが、単純な構文digitizeは、ビンの数が少ない場合とほぼ同じです。

于 2013-09-18T15:23:03.347 に答える