Более эффективное решение для поиска самой длинной серии на основе логических значений в NumPy ndArray

Question

Я ищу свой ndArray, чтобы найти самые длинные ряды, основанные на значениях True.Есть ли возможность найти самую длинную серию без циклического перебора массива?

Я уже написал свое собственное решение для numpy.nonzero, но, возможно, есть и лучшее.

import numpy as np
arr = np.array([[[1,2,3,4,5],
                [6,7,8,9,10],
                [11,12,13,14,15],
                [16,17,18,19,20],
                [21,22,23,24,25]],
                [[True,True,True,False,True],
                [True,True,True,True,False],
                [True,True,False,True,True],
                [True,True,True,False,True],
                [True,True,True,False,True]]])

def getIndices(arr):
    arr_to_search = np.nonzero(arr)
    arrs = []
    prev_el0 = 0
    prev_el1 = -1
    activ_long = []
    for i in range(len(arr_to_search[0])):
        if arr_to_search[0][i] == prev_el0:
            if arr_to_search[1][i] != prev_el1 + 1:
                arrs.append(activ_long)
                activ_long = []
        else:
            arrs.append(activ_long)
            activ_long = []
        activ_long.append((arr_to_search[0][i],arr_to_search[1][i]))
        prev_el0 = arr_to_search[0][i]
        prev_el1 = arr_to_search[1][i]

    max_len = len(max(arrs,key=len))
    longest_arr_list = [a for a in arrs if len(a) == max_len]
    return longest_arr_list

print(getIndices(arr[1,:,:]))
print(getIndices(arr[1,:,:].T))


[[(1, 0), (1, 1), (1, 2), (1, 3)]]
[[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)], [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4)]]

Answer 1

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

Я предполагаю, что логический массив имеет имя a.По сути, мы находим индексы для того, где строки изменяются с 0 на 1 или с 1 на 0, и смотрим на разницу между ними.Заполняя 0 на фронте и обратно, мы обеспечиваем, чтобы для каждого перехода от 0 до 1 был другой переход от 1 к 0.

Для удобства я обрабатываю a и a.Tв то же время, но вы можете сделать их отдельно, если хотите.

m,n = a.shape
A = np.zeros((2*m,n+2))
A[:m,1:-1] = a
A[m:,1:-1] = a.T

dA = np.diff(A)

start = np.where(dA>0)
end = np.where(dA<0)

argmax_run = np.argmax(end[1]-start[1])

row = start[0][argmax_run]
col_start = start[1][argmax_run]
col_end= end[1][argmax_run]-1

max_len = col_end - col_start + 1

print('max run of length {}'.format(max_len))
print('in '+('row' if row<m else'col')+' {}'.format(row%m)+' from '+('col' if row<m else'row')+' {} to {}'.format(col_start,col_end))

Для повышения производительности и хранения мы можем изменить A на логический массив.Поскольку -1 и 1 в dA выше всегда идут парами, мы можем найти start и end, как показано ниже.

nz = np.nonzero(dA)
start = (nz[0][::2], nz[1][::2])
end = (nz[0][1::2], nz[1][1::2])

Обратите внимание, что затем вы можете удалить переменные start и end полностью, поскольку они на самом деле не нужны.