2つのnumpy配列で最も近い値を見つける

Question

ここでの目的はスピードです。問題の配列をループするのをやめようとしています。しかし、2つの配列がソートされていると仮定することができます。

今

a = np.arange(10) 
b = np.array([2.3, 3.5, 5.8, 13]) 
c = somefunc(a,b) 

somefuncbの値があまりにも最も近いいるaのインデックスが、すなわち

In []: c 
Out[]: array([2, 3or4, 6, 9]) #3 or 4 depending on python2 or 3 

もう一度、これはループで行うことができるが、私は何かを探しています見つける必要がありますずっと速い。

np.argmin(np.abs(a[:, np.newaxis] - b), axis=0) 

しかし、これは少しでも不必要な減算が行われるため、少し遅いです。

Answer 1

がsearchsorted使用することが線形O（LEN A + LEN b）は、私はベクター上np.argminより大きいデータセットに迅速である次に来方法：

def finder(a, b): 
    dup = np.searchsorted(a, b) 
    uni = np.unique(dup) 
    uni = uni[uni < a.shape[0]] 
    ret_b = np.zeros(uni.shape[0]) 
    for idx, val in enumerate(uni): 
     bw = np.argmin(np.abs(a[val]-b[dup == val])) 
     tt = dup == val 
     ret_b[idx] = np.where(tt == True)[0][bw] 
    return np.column_stack((uni, ret_b)) 

Answer 2

は、aの現在のインデックス用とb用の2つのポインタを追跡します。ポインターaをインクリメントすると、pointed_a> pointed_bになるまで、指し示されている要素間の最小の差とインデックスを追跡します。 min差分とインデックスを再度更新します（変更がある場合）。そこに最初の要素に対する私たちの答えがあります。同様にbのポインタを増やして検索を続行し、途中からポインタaを取り上げます。

複雑：だから@Eelcoから提案を使用して

Answer 3

scipy.spatial.cKDTreeはこの問題の最も簡単な解決方法です。ベクタライズされたもので、あなたのアプリケーションには十分なものです。データがソートされているため、理論的には最適ではありません。

また、numpy.searchsortedを使用することもできます。これを使用して左または右の挿入ポイントを見つけ、そのポイントと次のポイントを比較して最も近いポイントを見つけます。