在numpy中找到布尔条件的端点是否有比线性更快的方法？

Question

有没有人知道(常见情况)快于线性的方法来查找数组的布尔属性的端点.

例如,numpy.nonzero(a)[0] [ - 1]是(dimension = 0)的最后一个非零元素的索引,类似地,numpy.nonzero(a)[0] [0]是索引.第一个非零元素.

如果我们知道我们只关心第一个或最后一个元素,那么我们可以使用更少的内存并且具有比上面运行"非零"更好的公共情况运行时.例如,如果我们坚持线性搜索,我们至少可以从适当的一端开始(向后搜索以找到与条件匹配的最后一个值).或者我们可以使用二进制搜索(例如,如果中间元素匹配条件,我们不需要检查上半部分以找到它的真实的最后一个元素).这似乎很普遍,可能有一个现有的实现,但我没有找到类似的东西.

Answer 1

您可以使用找到布尔数组的第一个True元素argmax.

a = np.array([False, False, True, True, True])
first_True = a.argmax()
last_True = len(a) - 1 - a[::-1].argmax()

您可以使用argmin查找False值,这将比使用非零值更快并占用更少的内存,但这在长度上是线性的a.如果你想要比线性更快,你需要知道它a是"已排序",对于一个布尔数组,这意味着你有一个False块,后跟所有True.在这种情况下,您可以使用搜索排序来查找False和true之间的边界:

first_True = a.searchsorted(True, 'left')