每行在 Numpy 中滚动 window 或出现 2D 矩阵？

Question

在矩阵的每一行上寻找模式的出现，我发现对于具有良好性能的非常大的矩阵，python 上没有明确的解决方案。

我有一个类似于

的矩阵

matrix = np.array([[0,1,1,0,1,0],
                         [0,1,1,0,1,0]])
print 'matrix: ', matrix

考虑到重叠，我想在每一行上检查模式 [0,0]、[0,1] [1,0] 和 [1,1] 的出现情况。对于给出的示例，如果两行相等，则每个模式的结果都相等：

模式[0,0] = [0,0]
模式[0,1] = [2,2]
模式[1,0] = [2,2]
模式[1,1] = [1,1]

这个例子中的矩阵很小，但我正在寻找性能，因为我有一个巨大的矩阵。例如，您可以使用 matrix = numpy.random.randint(2, size=(100000,10)) 或更大的值来测试矩阵以查看差异

首先，我虽然在一个可能的答案上将行转换为字符串并查找基于 this answer (string count with overlapping occurrences 的事件）：

def string_occurrences(matrix):
    print '\n===== String count with overlapping ====='
    numRow,numCol = np.shape(matrix)
    Ocur = np.zeros((numRow,4))
    for i in range(numRow):
        strList = ''.join(map(str,matrix[i,:]))
        Ocur[i,0] = occurrences(strList,'00')
        Ocur[i,1] = occurrences(strList,'01')
        Ocur[i,2] = occurrences(strList,'10')
        Ocur[i,3] = occurrences(strList,'11')
    return Ocur

使用答案的函数occurrences

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count+=1
        else:
            return count

但考虑到实际数组很大，这个解决方案非常非常慢，因为它使用循环、字符串、... 因此，为了寻找一个 numpy 解决方案，我使用了一个技巧来将值与模式进行比较，并在 axis=1 上滚动矩阵以检查所有出现的情况。我称它为 2D 上的伪滚动 window，因为 window 不是正方形，计算方式也不同。有 2 个选项，其中第二个（选项 2）更快，因为它避免了 numpy.roll

的额外计算

def pseudo_rolling_window_Opt12(matrix):
    print '\n===== pseudo_rolling_window ====='
    numRow,numCol = np.shape(matrix)
    Ocur = np.zeros((numRow,4))
    index = 0
    for i in np.arange(2):
        for j in np.arange(2):
            #pattern = -9*np.ones(numCol)   # Option 1
            pattern = -9*np.ones(numCol+1)  # Option 2
            pattern[0] = i
            pattern[1] = j
            for idCol in range(numCol-1):
                #Ocur[:,index] += np.sum(np.roll(matrix,-idCol, axis=1) == pattern, axis=1) == 2    # Option 1: 219.398691893 seconds (for my real matrix)
                Ocur[:,index] += np.sum(matrix[:,idCol:] == pattern[:-(idCol+1)], axis=1) == 2      # Option 2:  80.929688930 seconds (for my real matrix)
            index += 1
    return Ocur

寻找其他可能性，我发现 "rolling window" 这似乎是性能的神答案，因为它使用了 numpy 函数。查看 this answer (Rolling window for 1D arrays in Numpy?) 及其上的链接，我检查了以下功能。但实际上，我不理解输出结果，因为 window 的计算结果似乎与我预期的结果相符。

def rolling_window(a, size):
    shape = a.shape[:-1] + (a.shape[-1] - size + 1, size)
    strides = a.strides + (a.strides[-1],)
    return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)

用作：

a = rolling_window(matrix, 2)
print a == np.array([0,1])
print np.all(rolling_window(matrix, 2) == [0,1], axis=1)

有人知道最后一个案例出了什么问题吗？或者有没有可能有更好的表现？

Answer 1

您使用了错误的 numpy 数组轴。您应该将 np.all 中的轴从 1 更改为 2。使用以下代码：

a = rolling_window(matrix, 2)
print np.all(rolling_window(matrix, 2) == [0,1], axis=2)

你得到：

>>>[[ True False False  True False]
    [ True False False  True False]]

因此，为了获得您正在寻找的结果：

print np.sum(np.all(rolling_window(matrix, 2) == [0,1], axis=2),axis=1)

>>>[2 2]

每行在 Numpy 中滚动 window 或出现 2D 矩阵？

Rolling window or occurrences for 2D matrix in Numpy per row?

python

numpy

window

matrix

find-occurrences