有没有更快的方法来搜索numpy数组？

Question

我有一个约为3125000个条目的 numpy 数组，使用以下数据类型进行结构化

dt = np.dtype([('startPoint', '<u8' ), ('endPoint', '<u8')])

这些数据来自于之前根据 endPoint 进行排序的文件，然后再读取到数组中。

现在我需要搜索这个数组并检查是否包含特定的终端点。我将使用以下代码进行二分查找：

def binarySearch(array, index):
lowPoint = 0
highpoint = len(array) - 1


while (lowPoint <= highpoint):
    midPoint = int((lowPoint + highpoint) / 2)

    if(index == array[midPoint]['endPoint']):
        return midPoint

    elif(index < array[midPoint]['endPoint']):
        highpoint = midPoint - 1

    else:
        lowPoint = midPoint + 1

return -1

我的问题是，在这个数组中是否有更快的搜索条目的方法。是否有内置的Numpy搜索，可能比我的二进制搜索更快。

- Scott

---

numpy.searchsorted 是一个用 C 实现的二分查找函数。 - Max Linke

我查看了scipy页面上的searchSorted，但我不清楚如何将其与我创建的自定义dtype进行比较。是否有我错过的示例链接？ - Scott

Answer 1

尝试使用numpy.searchsorted，如果数组过大，也可以使用内存映射。searchsorted实现为二分查找。

- Patrick the Cat

---

如果numpy数组包含dtypes，您如何为此结构searchsorted？在我的实例中，索引是一个长整型，但要搜索的内容在array[x][endPoint]中。 - Scott

@Scott 这正是你要传递给 np.searchsorted 的内容，即 arr['endPoint'].searchsorted(x)。 - ali_m

那么当searchsorted完成后，我应该在返回的索引处查看数组，以查看它是否是我正在搜索的元素吗？ def contains(array, x): return x == array[array.searchsorted(x)] 这是一个很好的使用示例吗？ - Moberg