为另一个数组中的所有值查找一个数组的最接近的索引 - 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

回答

相关问题