python - 在 NumPy ndArray 中基于 bool 值查找最长序列的更有效解决方案

Question

我搜索 ndArray 以查找基于真实值的最长序列。是否可以选择在不循环数组的情况下查找最长的系列？

我已经用 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

这是一个 numpy 解决方案，它避免基于 this previous question. 的显式循环

我假设 bool 数组名为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 更改为 bool 数组。由于上面dA中的-1和1总是成对出现，所以我们可以找到start和结束如下。

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

请注意，您可以完全删除变量 start 和 end，因为实际上并不需要它们。