큰 2D 비트 매트릭스 내에서 크기 HxW의 최대 하위 배열

Nov 13 2020

K 1을 가진 큰 NxN 비트 배열이 있습니다 (다른 모든 것은 0입니다). 0이 아닌 모든 점의 좌표가 알려져 있습니다. 즉,이 NxN 배열은 각각 0이 아닌 점의 x 및 y 좌표를 포함하는 K 쌍의 배열로 표현 될 수 있습니다.

HxW 크기의 부분 행렬이 주어지면 대부분의 0이 아닌 지점을 포함하도록 원래 NxN 배열에 배치해야합니다.

입력 : 부분 행렬의 높이 H 및 너비 W

출력 : 가장 많은 HxW 하위 배열의 xy 좌표

비슷한 질문이 전에 대답되었습니다 .2D 매트릭스 내에서 크기 HxW의 최대 하위 배열 이지만 내 문제에서는 N이 거대하기 때문에 조금 더 복잡합니다. 내 경우에는 N = 60000, K <15000, H, W <10000입니다.

60000x60000 배열을 만드는 것은 비트 배열이더라도 메모리를 죽일 것입니다. 이것이 제가 0이 아닌 모든 점, 즉 K 쌍의 1 차원 배열로 그 배열을 나타내는 아이디어를 생각 해낸 이유입니다.

내가 생각해 낼 수있는 모든 것은 메모리와 시간 모두 비효율적이며, 내 숫양을 모두 먹지 않을 솔루션을 찾고 있습니다. 의미는 다음과 같습니다.이 시점에서 시작하는 HxW 하위 배열에 가장 많은 항목이 포함되어 있으므로 출력은 점 (4,3)이됩니다.

답변

1 Nick Nov 13 2020 at 10:24

여기에 (잠재적으로 최적화 될 수 있는) 알고리즘이 있으며 공간 요구 사항에 대해 매우 가볍습니다 . 0이 아닌 합계 가장 높은 부분 행렬 은 왼쪽 가장자리에 점이 있어야 한다는 이론에 따라 작동 합니다 (그렇지 않으면 오른쪽에 합계가 더 높은 부분 행렬이있을 수 있음). 따라서 가장 높은 합계를 찾기 위해 0이 아닌 각 점을 반복하고 왼쪽 가장자리에 해당 점이있는 모든 부분 행렬을 찾아 각 행의 현재 점 오른쪽에있는 0이 아닌 모든 점을 합산합니다. 부분 행렬.O(k2*h)O(k*h*w)O(k)W

아래는 그 알고리즘의 파이썬 구현입니다. 먼저 각 행에있는 점의 사전을 만든 다음 설명 된대로 각 점에 대해 반복하여 해당 행의 오른쪽에 0이 아닌 점의 합계를 저장 한 다음 해당 점을 기준으로 각 부분 행렬의 합계를 계산합니다. 합계가 현재 최대 값보다 크면 값과 해당 위치가 저장됩니다. 여기에서는 색인이 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)

rextester 데모