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

Question

假设我有两个排序的向量（1D numpy ndarrays）A和B。我想找出向量A中的哪些值也存在于向量B中。这将是某个函数的瓶颈，所以我想尽快确定。有一个函数努皮因德这正是我需要的。它可以通过告诉函数向量中的值是唯一的这一事实来增强。好的，很好。但是排序值呢？我相信知道这些值是排序的可以进一步提高性能，因为这将是复杂性O（1）。但没有理由说努皮因德向量被排序。。。或者有没有其他的方法或技巧可以帮助我？你知道吗

Answer 1

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)，尽管它没有利用针本身被分类的事实。你可以在Cython/C的O(N + M)中这样做，这对于大的（r）N来说会更快。你知道吗

Answer 2

也许你可以用每个向量创建集合，然后在集合上使用intersect。你知道吗

我认为向量应该允许建筑从它们出发，比如：

a = set(vectorA)
b = set(vectorB)
commons = a.intersection(b)