爲另一個數組中的所有值查找一個數組的最接近的索引 - Python/NumPy

我有一個複數的列表，我希望找到另一個複數列表中最接近的值。爲另一個數組中的所有值查找一個數組的最接近的索引 - Python/NumPy

我與numpy的目前的做法：

import numpy as np 

refArray = np.random.random(16); 
myArray = np.random.random(1000); 


def find_nearest(array, value): 
    idx = (np.abs(array-value)).argmin() 
    return idx; 

for value in np.nditer(myArray): 
    index = find_nearest(refArray, value); 
    print(index);

不幸的是，這需要年齡了大量的值。有沒有更快或更多的「pythonian」方式將myArray中的每個值與refArray中最接近的值進行匹配？

供參考：我不一定需要在我的劇本numpy。

重要提示： myArray以及refArray的順序很重要，不應該改變。如果要應用排序，則應以某種方式保留原始索引。

來源

2017-07-27 Alexander

在時間複雜度方面，*滑動窗口*可能是最有效的。 –

我看不到滑動窗口比當前解決方案更高效。據我所知，目前的解決方案是O（n），這是最好的希望。然後，有一些權衡要做，以儘量減少時間常數。但這取決於你的大案例是否會激發你的記憶力。如果這不是一個內存問題，那麼使用廣播和使用更多「numpy」計算可能會有所收穫，但如果RAM內存是一個問題，那麼這可能會減慢你的速度。 – JohanL

@JohanL RAM不是問題，時間不幸的是。這個簡單的循環既是最簡單的，也是我能想到的最好的方法..不幸的是，對於ref = 64和值= 200,000的數組大小，匹配需要10秒以上，目標會在一秒之內... – Alexander

下面是基於this post與np.searchsorted一個量化的方法 -

def closest_argmin(A, B): 
    L = B.size 
    sidx_B = B.argsort() 
    sorted_B = B[sidx_B] 
    sorted_idx = np.searchsorted(sorted_B, A) 
    sorted_idx[sorted_idx==L] = L-1 
    mask = (sorted_idx > 0) & \ 
    ((np.abs(A - sorted_B[sorted_idx-1]) < np.abs(A - sorted_B[sorted_idx]))) 
    return sidx_B[sorted_idx-mask]

簡要說明：

獲取左側位置來分類指數。我們通過 - np.searchsorted(arr1, arr2, side='left')或np.searchsorted(arr1, arr2)來做到這一點。現在，searchsorted預計排序數組作爲第一個輸入，所以我們需要在那裏做一些準備工作。
將那些左側位置的值與其右側位置的值(left + 1)進行比較，並查看哪一個最接近。我們在計算mask的步驟中執行此操作。
根據左邊的或右邊的是最接近的，選擇相應的。這是通過將mask值作爲將偏移量轉換爲ints來減去索引來完成的。

標杆

原始的方法 -

def org_app(myArray, refArray): 
    out1 = np.empty(myArray.size, dtype=int) 
    for i, value in enumerate(myArray): 
     # find_nearest from posted question 
     index = find_nearest(refArray, value) 
     out1[i] = index 
    return out1

時序和驗證 -

In [188]: refArray = np.random.random(16) 
    ...: myArray = np.random.random(1000) 
    ...: 

In [189]: %timeit org_app(myArray, refArray) 
100 loops, best of 3: 1.95 ms per loop 

In [190]: %timeit closest_argmin(myArray, refArray) 
10000 loops, best of 3: 36.6 µs per loop 

In [191]: np.allclose(closest_argmin(myArray, refArray), org_app(myArray, refArray)) 
Out[191]: True

50x+加速的貼樣品和hopef對於大型數據集來說更是如此！

來源

2017-07-27 12:05:15 Divakar

你真的需要'np.abs'嗎？我認爲你也可以使用'（A - sorted_B [sorted_idx-1]

此外，我不認爲使用'np.allclose'來比較*索引*數組是有道理的。 –

爲另一個數組中的所有值查找一個數組的最接近的索引 - Python/NumPy

回答

相關問題