Maximales Subarray der Größe HxB innerhalb einer großen 2D-Bitmatrix

Question

Ich habe ein großes NxN-Bit-Array mit K Einsen (alles andere ist Null). Koordinaten aller Nicht-Nullpunkte sind bekannt - mit anderen Worten, dieses NxN-Array kann als Array von K Paaren dargestellt werden, die jeweils x- und y-Koordinaten eines Nicht-Nullpunkts enthalten.

Bei einer Submatrix von HxW-Größe muss ich sie so auf meinem ursprünglichen NxN-Array platzieren, dass sie die meisten Nicht-Null-Punkte abdeckt.

Eingabe: Höhe H und Breite W der Submatrix

Ausgabe: x- und y- Koordinaten des HxW-Subarrays, das die meisten in sich hat

Eine ähnliche Frage wurde bereits zuvor beantwortet: Maximales Subarray der Größe HxW innerhalb einer 2D-Matrix, aber in meinem Problem ist es etwas komplizierter, da N riesig ist, in meinem Fall: N = 60000, K <15000, H, W <10000.

Das Erstellen eines 60000x60000-Arrays wäre ein Speicherabbruch, selbst wenn es sich um ein Array von Bits handelt. Aus diesem Grund kam mir die Idee, dieses Array mit allen Nicht-Nullpunkten darzustellen: eindimensionales Array von K Paaren.

Alles, was ich mir einfallen lassen kann, ist sowohl in Bezug auf das Gedächtnis als auch in Bezug auf die Zeit ineffizient. Ich suche nach einer Lösung, die nicht meinen ganzen Widder frisst. So soll es aussehen: Die Ausgabe wäre Punkt (4,3), da das HxW-Subarray, das an diesem Punkt beginnt, die meisten enthält.

Answer 1

Hier ist ein Algorithmus, der sein sollte (er könnte möglicherweise optimiert werden ) und der den Platzbedarf recht gering hält . Es arbeitet auf der Theorie , dass jede Submatrix, die die höchste nicht-Null - Summe hat muss einen Punkt auf seinem linken Rand hat (sonst könnte es eine Submatrix mit einer höheren Summe rechts von diesem sein). Um die höchste Summe zu finden, iterieren wir über jeden der Nicht-Null-Punkte und finden alle Submatrizen, die diesen Punkt am linken Rand haben, wobei wir alle Nicht-Null-Punkte rechts vom aktuellen Punkt für jede Zeile in summieren die Submatrix.O(k2*h)O(k*h*w)O(k)W

Unten finden Sie eine Python-Implementierung dieses Algorithmus. Es wird zuerst ein Wörterbuch der Punkte in jeder Zeile erstellt, dann wie beschrieben über jeden Punkt iteriert, die Summe der Nicht-Null-Punkte rechts in dieser Zeile gespeichert und dann die Summen für jede Submatrix basierend auf diesem Punkt berechnet. Wenn die Summe größer als das aktuelle Maximum ist, werden der Wert und seine Position gespeichert. Beachten Sie, dass hier 0-indizierte Listen verwendet werden, sodass für Ihre Beispieldaten das Maximum bei liegt (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}')

Beispielnutzung:

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)

Ausgabe:

5 found at location (2, 3)

Demo auf Rextester