大二维位矩阵中大小为 HxW 的最大子数组

Question

我有一个很大的 NxN 位数组，其中有 K 个（其他都是零）。所有非零点的坐标都是已知的 - 换句话说，这个 NxN 数组可以表示为 K 对数组，每个对包含非零点的 x 和 y 坐标。

给定一个 HxW 大小的子矩阵，我需要将它放在我原来的 NxN 数组上，使其覆盖最多的非零点。

输入：子矩阵

的高度H和宽度W

输出： x 和 y HxW 子数组中最多的坐标本身

之前回答过类似的问题：但我的问题有点复杂，因为 N 很大，就我而言： N=60000, K<15000, H,W<10000.

创建 60000x60000 数组会消耗大量内存，即使它是位数组也是如此。这就是为什么我想出了用所有非零点表示该数组的想法：K 对的一维数组。

我能想出的一切都是超级内存和时间效率低下，我正在寻找任何不会吃掉我所有 ram 的解决方案。它的意思是这样的：输出将是点 (4,3)，因为从这一点开始的 HxW 子数组包含最多的子数组。

Answer 1

这是一个算法，应该是 O(k<sup>2</sup>*h)（它可能被优化为 O(k*h*w) ) 并且在 space 要求 O(k) 上相当轻松。它的工作原理是任何具有最高非零和 的子矩阵必须 在其左边缘有一个点（否则，可能有一个子矩阵具有更高的和在右侧这个）。因此，为了找到最高和，我们遍历每个非零点并找到所有在其左边缘具有该点的子矩阵，将 W 内的所有非零点相加到当前点的右侧子矩阵中每一行的点。

下面是该算法的 python 实现。它首先创建每行中点的字典，然后按照所述遍历每个点，将非零点的总和存储到该行的右侧，然后计算基于该点的每个子矩阵的总和。如果总和大于当前最大值，则存储该值及其位置。请注意，这使用 0 索引列表，因此对于您的示例数据，最大值为 (2, 3).

from collections import defaultdict

def max_subarray(n, nzp, h, w):
    maxsum = 0
    maxloc = (0, 0)
    # create a dictionary of points in a row
    nzpd = defaultdict(list)
    for p in nzp:
        nzpd[p[0]].append(p[1])
    # iterate over each of the non-zero points, looking at all
    # submatrixes that have the point on the left side
    for p in nzp:
        y, x = p
        pointsright = [0] * n
        for r in range(max(y-(h-1), 0), min(y+h, n)):
            # points within w to the right of this column on this row
            pointsright[r] = len([p for p in nzpd[r] if x <= p <= x+(w-1)])
        # compute the sums for each of the possible submatrixes
        for i in range(-h+1, h):
            thissum = sum(pointsright[max(y+i, 0):min(y+i+h, n)])
            if thissum > maxsum:
                maxsum = thissum
                maxloc = (y, x)
    # adjust the position in case the submatrix would extend beyond the last row/column
    maxloc = (min(n-h, maxloc[0]), min(n-w, maxloc[1]))
    # print the max sum
    print(f'{maxsum} found at location {maxloc}')

示例用法：

nzp = [(0, 6), (1, 9), (2, 3), (2, 4), (2, 5), 
       (3, 1), (3, 4), (3, 6), (4, 3), (4, 3), 
       (4, 10), (5, 5), (6, 4), (6, 8), (7, 5), 
       (8, 3), (10, 2), (10, 8), (11, 4), (11, 10)
       ]
  
max_subarray(12, nzp, 2, 4)

输出：

5 found at location (2, 3)

Demo on rextester

大二维位矩阵中大小为 HxW 的最大子数组

Maximum subarray of size HxW within a big 2D bit matrix

arrays

algorithm

max

submatrix