Получить индекс последнего отрицательного значения в массиве 2d на столбец

Я пытаюсь получить индекс последнего отрицательного значения массива за столбец (чтобы его отрезать после него). простой рабочий пример для 1d-вектора:

import numpy as np

A = np.arange(10) - 5
A[2] = 2
print A # [-5 -4  2 -2 -1  0  1  2  3  4]

idx = np.max(np.where(A <= 0)[0])
print idx # 5

A[:idx] = 0
print A # [0 0 0 0 0 0 1 2 3 4]

Теперь я хочу сделать то же самое в каждом столбце 2D-массива:

A = np.arange(10) - 5
A[2] = 2
A2 = np.tile(A, 3).reshape((3, 10)) - np.array([0, 2, -1]).reshape((3, 1))
print A2
# [[-5 -4  2 -2 -1  0  1  2  3  4]
#  [-7 -6  0 -4 -3 -2 -1  0  1  2]
#  [-4 -3  3 -1  0  1  2  3  4  5]]

И я хотел бы получить:

print A2
# [[0 0 0 0 0 0 1 2 3 4]
#  [0 0 0 0 0 0 0 0 1 2]
#  [0 0 0 0 0 1 2 3 4 5]]

но я не могу понять, как перевести оператор max/where в этот 2d-массив...

Ответ 1

У вас уже есть хорошие ответы, но я хотел бы предложить потенциально более быстрое изменение, используя функцию np.maximum.accumulate. Поскольку ваш метод для массива 1D использует max/where, вы также можете найти этот подход достаточно интуитивно понятным. (Изменить: более быстрая реализация Cython добавлена ниже).

Общий подход очень похож на других; маска создается с помощью:

np.maximum.accumulate((A2 < 0)[:, ::-1], axis=1)[:, ::-1]

Эта строка кода выполняет следующие действия:

(A2 < 0) создает логический массив, указывающий, является ли значение отрицательным или нет. Индекс [:, ::-1] переворачивает это влево-вправо.
np.maximum.accumulate используется для возврата кумулятивного максимума вдоль каждой строки (т.е. axis=1). Например, [False, True, False] станет [False, True, True].
Конечная операция индексирования [:, ::-1] переворачивает новый Boolean массив слева направо.

Тогда все, что осталось сделать, это использовать Boolean массив в качестве маски, чтобы установить значения True равными нулю.

Заимствуя методологию синхронизации и две функции из @Divakar answer, здесь приведены критерии для моего предложенного метода:

# method using np.maximum.accumulate
def accumulate_based(A2):
    A2[np.maximum.accumulate((A2 < 0)[:, ::-1], axis=1)[:, ::-1]] = 0
    return A2

# large sample array
A2 = np.random.randint(-4, 10, size=(100000, 100))
A2c = A2.copy()
A2c2 = A2.copy()

Сроки:

In [47]: %timeit broadcasting_based(A2)
10 loops, best of 3: 61.7 ms per loop

In [48]: %timeit cumsum_based(A2c)
10 loops, best of 3: 127 ms per loop

In [49]: %timeit accumulate_based(A2c2) # quickest
10 loops, best of 3: 43.2 ms per loop

Таким образом, использование np.maximum.accumulate может быть на 30% быстрее, чем следующее быстрое решение для массивов такого размера и формы.

Как @tom10 указывает, каждая операция NumPy обрабатывает массивы полностью, что может быть неэффективным, когда для получения результата требуются несколько операций. Итеративный подход, который работает через массив только один раз, может быть лучше.

Ниже представлена наивная функция, написанная в Cython, которая может быть более чем в два раза быстрее, чем чистый подход NumPy.

Эта функция может быть ускорена, используя виды памяти.

cimport cython
import numpy as np
cimport numpy as np

@cython.boundscheck(False)
@cython.wraparound(False)
@cython.nonecheck(False)
def cython_based(np.ndarray[long, ndim=2, mode="c"] array):
    cdef int rows, cols, i, j, seen_neg
    rows = array.shape[0]
    cols = array.shape[1]
    for i in range(rows):
        seen_neg = 0
        for j in range(cols-1, -1, -1):
            if seen_neg or array[i, j] < 0:
                seen_neg = 1
                array[i, j] = 0
    return array

Эта функция работает в обратном порядке через каждую строку и начинает устанавливать значения в ноль после того, как она увидела отрицательное значение.

Тестирование работает:

A2 = np.random.randint(-4, 10, size=(100000, 100))
A2c = A2.copy()

np.array_equal(accumulate_based(A2), cython_based(A2c))
# True

Сравнение производительности функции:

In [52]: %timeit accumulate_based(A2)
10 loops, best of 3: 49.8 ms per loop

In [53]: %timeit cython_based(A2c)
100 loops, best of 3: 18.6 ms per loop

Ответ 2

Предполагая, что вы хотите установить все элементы для каждой строки до тех пор, пока последний отрицательный элемент не будет установлен на ноль (в соответствии с ожидаемым выходом, указанным в вопросе для примера), здесь могут быть предложены два подхода.

Подход № 1

Этот метод основан на np.cumsum, чтобы сгенерировать маску элементов, которые должны быть установлены в нули, как указано ниже -

# Get boolean mask with TRUEs for each row starting at the first element and 
# ending at the last negative element
mask = (np.cumsum(A2[:,::-1]<0,1)>0)[:,::-1]

# Use mask to set all such al TRUEs to zeros as per the expected output in OP 
A2[mask] = 0

Пример прогона -

In [280]: A2 = np.random.randint(-4,10,(6,7)) # Random input 2D array

In [281]: A2
Out[281]: 
array([[-2,  9,  8, -3,  2,  0,  5],
       [-1,  9,  5,  1, -3, -3, -2],
       [ 3, -3,  3,  5,  5,  2,  9],
       [ 4,  6, -1,  6,  1,  2,  2],
       [ 4,  4,  6, -3,  7, -3, -3],
       [ 0,  2, -2, -3,  9,  4,  3]])

In [282]: A2[(np.cumsum(A2[:,::-1]<0,1)>0)[:,::-1]] = 0 # Use mask to set zeros

In [283]: A2
Out[283]: 
array([[0, 0, 0, 0, 2, 0, 5],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 3, 5, 5, 2, 9],
       [0, 0, 0, 6, 1, 2, 2],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 9, 4, 3]])

Подход # 2

Это начинается с идеи найти последние отрицательные индексы элементов из @tom10 answer и развивается в метод поиска маски с помощью broadcasting, чтобы получить желаемый результат, аналогичный approach #1.

# Find last negative index for each row
last_idx = A2.shape[1] - 1 - np.argmax(A2[:,::-1]<0, axis=1)

# Find the invalid indices (rows with no negative indices)
invalid_idx = A2[np.arange(A2.shape[0]),last_idx]>=0

# Set the indices for invalid ones to "-1"
last_idx[invalid_idx] = -1

# Boolean mask with each row starting with TRUE as the first element 
# and ending at the last negative element
mask = np.arange(A2.shape[1]) < (last_idx[:,None] + 1)

# Set masked elements to zeros, for the desired output
A2[mask] = 0

Тесты времени выполнения -

Дефекты функций:

def broadcasting_based(A2):
    last_idx = A2.shape[1] - 1 - np.argmax(A2[:,::-1]<0, axis=1)
    last_idx[A2[np.arange(A2.shape[0]),last_idx]>=0] = -1
    A2[np.arange(A2.shape[1]) < (last_idx[:,None] + 1)] = 0
    return A2

def cumsum_based(A2):    
    A2[(np.cumsum(A2[:,::-1]<0,1)>0)[:,::-1]] = 0    
    return A2

Runtimes:

In [379]: A2 = np.random.randint(-4,10,(100000,100))
     ...: A2c = A2.copy()
     ...: 

In [380]: %timeit broadcasting_based(A2)
10 loops, best of 3: 106 ms per loop

In [381]: %timeit cumsum_based(A2c)
1 loops, best of 3: 167 ms per loop

Подтвердить результаты -

In [384]: A2 = np.random.randint(-4,10,(100000,100))
     ...: A2c = A2.copy()
     ...: 

In [385]: np.array_equal(broadcasting_based(A2),cumsum_based(A2c))
Out[385]: True

Ответ 3

Поиск первого обычно проще и быстрее, чем поиск последнего, поэтому здесь я отменяю массив, а затем нахожу первый отрицательный (используя версию OP A2):

im = A2.shape[1] - 1 - np.argmax(A2[:,::-1]<0, axis=1)

# [4 6 3]      # which are the indices of the last negative in A2

Кроме того, обратите внимание, что если у вас есть большие массивы со многими отрицательными номерами, возможно, быстрее будет использовать не-numpy-подход, чтобы вы могли коротко закоротить поиск. То есть numpy будет выполнять вычисления по всему массиву, поэтому, если у вас есть 10000 элементов в строке, но обычно они будут попадать в отрицательное число в первых 10 элементах (обратного поиска), чистый подход Python может оказаться быстрее,

В целом, повторение строк может быть более быстрым и для последующих операций. Например, если ваш следующий шаг - умножение, скорее всего, можно просто умножить срезы на концах, которые не являются нулями, или, может быть, найти этот самый длинный ненулевой раздел и просто иметь дело с усеченным массивом.

В основном это сводится к количеству отрицаний в строке. Если у вас есть 1000 негативов на строку, вы в среднем будете иметь сегменты без нуля, которые составляют 1/1000-й длины вашей полной строки, поэтому вы можете получить 1000-кратное ускорение, просто глядя на концы. Короткий пример, приведенный в вопросе, отлично подходит для понимания и ответа на основной вопрос, но я бы не стал слишком серьезно относиться к срочным испытаниям, когда ваше конечное приложение представляет собой совершенно другой вариант использования; тем более, что сэкономить время на сбережения с помощью итерации будет пропорционально размеру массива (при условии постоянного отношения и случайного распределения отрицательных чисел).

Ответ 4

Вы можете получить доступ к отдельным строкам:

A2[0] == array([-5, -4,  2, -2, -1,  0,  1,  2,  3,  4])