Существует ли более быстрый, чем линейный способ найти конечные точки логического условия в numpy?

Question

Кто-нибудь знает (в общем случае) более быстрый, чем линейный способ поиска конечных точек логического свойства массива.

Например, numpy.nonzero (a) [0] [- 1] - это индекс последнего ненулевого элемента (размерности = 0), и аналогично numpy.nonzero (a) [0] [0] - индекс первого ненулевого элемента.

Если мы знаем, что заботимся только о первом или последнем элементе, мы можем использовать меньше памяти и иметь лучшее время выполнения в общем случае, чем запускать "ненулевой", как описано выше. Например, если мы придерживаемся линейного поиска, мы можем по крайней мере начать с соответствующего конца (поиск в обратном направлении, чтобы найти последнее значение, соответствующее условию). Или мы могли бы использовать бинарный поиск (например, если средний элемент соответствует условию, нам не нужно проверять 1-ю половину, чтобы найти последний элемент, где он равен true). Это кажется достаточно распространенным, что может быть существующая реализация, но я не нашел ничего подобного.

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.В этом случае вы можете использовать сортировку поиска, чтобы найти границу между ложным и истинным:

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