下面是基於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對於大型數據集來說更是如此!
在時間複雜度方面,*滑動窗口*可能是最有效的。 –
我看不到滑動窗口比當前解決方案更高效。據我所知,目前的解決方案是O(n),這是最好的希望。然後,有一些權衡要做,以儘量減少時間常數。但這取決於你的大案例是否會激發你的記憶力。如果這不是一個內存問題,那麼使用廣播和使用更多「numpy」計算可能會有所收穫,但如果RAM內存是一個問題,那麼這可能會減慢你的速度。 – JohanL
@JohanL RAM不是問題,時間不幸的是。這個簡單的循環既是最簡單的,也是我能想到的最好的方法..不幸的是,對於ref = 64和值= 200,000的數組大小,匹配需要10秒以上,目標會在一秒之內... – Alexander