为另一个数组中的所有值查找一个数组的最接近的索引 - 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的顺序很重要,不应该改变。如果要应用排序,则应以某种方式保留原始索引。
下面是基于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对于大型数据集来说更是如此!
你真的需要'np.abs'吗?我认为你也可以使用'(A - sorted_B [sorted_idx-1]
此外,我不认为使用'np.allclose'来比较*索引*数组是有道理的。 –
在时间复杂度方面,*滑动窗口*可能是最有效的。 –
我看不到滑动窗口比当前解决方案更高效。据我所知,目前的解决方案是O(n),这是最好的希望。然后,有一些权衡要做,以尽量减少时间常数。但这取决于你的大案例是否会激发你的记忆力。如果这不是一个内存问题,那么使用广播和使用更多“numpy”计算可能会有所收获,但如果RAM内存是一个问题,那么这可能会减慢你的速度。 – JohanL
@JohanL RAM不是问题,时间不幸的是。这个简单的循环既是最简单的,也是我能想到的最好的方法..不幸的是,对于ref = 64和值= 200,000的数组大小,匹配需要10秒以上,目标会在一秒之内... – Alexander