NumPy だけでやる場合、配列の要素に対して処理する際に last
をグローバル変数として保持しておきながら高速に処理する方法を思い付けませんでした。numpy.vectorize
や numpy.ufunc.reduce
を使ってできないかと思ったのですが、上手く行きませんでした。また、NumPy 1.14.0 には「配列から、ある要素が含まれる最初のインデックスだけを出力する」という関数が未だに無いので、a
がソートされていない場合は NumPy のみでは素早い実行ができなさそうです。
代わりに Cython を使って高速化することはできたので、参考までに IPython での実装を共有いたします。こちらの環境では生 Python での実装に比べ 4 倍ほど速く実行されました。
In [1]: import numpy as np
# データの準備
len_a = 10000
len_b = 5000
a_arr = np.random.randint(low=0, high=10000, size=len_a)
b_mask = np.concatenate((np.ones((len_b,), dtype=bool), np.zeros((len_a - len_b,), dtype=bool)))
np.random.shuffle(b_mask)
b_arr = a_arr[b_mask]
a = list(a_arr)
b = list(b_arr)
In [2]: def search_plain(a, b):
result = [-1] * len(b)
last = 0
for i, n in enumerate(b):
result[i] = a.index(n, last)
last = result[i] + 1
return result
%timeit search_plain(a, b)
1.93 ms ± 150 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [3]: %reload_ext Cython
In [4]: %%cython
# cython: boundscheck=False, wraparound=False
def search_cython(a, b):
cdef int i, j
cdef int last = 0
cdef int len_a = len(a)
cdef int len_b = len(b)
result = [-1] * len_b
for i in range(len_b):
for j in range(last, len_a):
if a[j] == b[i]:
result[i] = j
last = j + 1
break
return result
In [5]: %timeit search_cython(a, b)
462 µs ± 14.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [6]: # asserting...
result_plain = search_plain(a, b)
result_cython = search_cython(a, b)
print("search_cython is valid:", set(result_plain) == set(result_cython))
search_cython is valid: True
b
の順序が保証されない場合
注意: 以下は私がご質問の内容を誤解して回答した際の、古いものです。
NumPy array から特定の値を持つインデックスを得るには、numpy.where
を使います。その値が複数ヶ所にある場合、numpy.where
はそれら全てを返します。
>>> import numpy as np
>>> a = np.array([1, 1, 2, 3, 5, 8])
>>> np.where(a == 3)
(array([3]),)
>>> np.where(a == 1)
(array([0, 1]),)
これを単純に b
の各要素について実行すれば良いのであれば、次のように書けます。
>>> a = np.array([1, 2, 3, 4, 5, 6])
>>> b = np.array([1, 4, 6])
>>> np.array([np.where(a == x) for x in b])
array([[[0]],
[[3]],
[[5]]])
a
が一次元配列のときに限るのであれば、次のように書いた方が冗長性を省けます。
>>> np.array([np.where(a == x)[0] for x in b])
array([[0],
[3],
[5]])
リスト内包表記では遅いということであれば、numpy.frompyfunc
や numpy.fromiter
を使う方法もあります (参考1、2)。
>>> where = lambda x: np.where(a == x)[0]
>>> np.frompyfunc(where, 1, 1)(b)
array([array([0]), array([3]), array([5])], dtype=object)
a
の要素が重複することは想定されていますでしょうか? 具体的にはたとえばa = [1, 1, 2]
,b = [1]
というのはありえますか?