Skip to main content
 首页 » 编程设计

python之从排序向量中查找值,这些值也存在于另一个排序向量中

2024年10月25日12kevingrace

假设我有两个排序向量(一维 numpy ndarrays)A 和 B。我想找出向量 A 中的哪些值也出现在向量 B 中。这将成为某个函数的瓶颈,所以我想尽可能快地制作。有一个函数 numpy.in1d 可以满足我的需要。它可以通过告诉函数向量中的值是唯一的这一事实来提升。好的,很好。但是排序后的值呢?我相信知道值已排序可以进一步提高性能,因为它的复杂度为 O(1)。但是没有理由告诉 numpy.in1d 向量已排序......或者是否有任何替代方法或技巧可以帮助我?

请您参考如下方法:

np.searchsorted 返回应在不破坏排序的情况下放置相应值的位置。如果您的“haystack”数组包含该值,它就会在那里。您只需要用针比较这些位置的值。但要小心越界访问:在 haystack 中大于最大值的针将产生 index == len(haystack) 并将产生 IndexError。您可以使用 np.take(..., mode='clip') 返回此类值的最大值(并且它将无法通过相等性测试)。

In [14]: haystack = np.array([1,2,4,5,8]) 
 
In [15]: needles = np.array([0,1,3,4,7,8,9]) 
 
In [16]: haystack.take(np.searchsorted(haystack, needles), mode='clip') 
Out[16]: array([1, 1, 4, 4, 8, 8, 8]) 
 
In [17]: haystack.take(np.searchsorted(haystack, needles), mode='clip') == needles 
Out[17]: array([False,  True, False,  True, False,  True, False], dtype=bool) 
 
In [18]: needles[haystack.take(np.searchsorted(haystack, needles), mode='clip') == needles] 
Out[18]: array([1, 4, 8]) 

如果您期望 needles 中的很多元素大于 haystack.max(),您可能需要在搜索之前修剪 needles避免在无关元素上浪费空间

needles = needles[needles <= haystack.max()] 

或更快的变体

needles = needles[:np.searchsorted(needles, haystack.max(), side='right')] 

编辑:这个解决方案是 O(N*logM),N = len(needles), M = len(haystack),尽管它没有使用事实上,针本身是经过分类的。您可以在 O(N + M) 中在 Cython/C 中执行此操作,这对于大型 (r) N 会更快。