Wenn Sie 2 Matrizen der Dimensionen N * M haben. Was ist der beste Weg, um den Unterschied Rect zu bekommen?
Beispiel:
%Vor%Das Beste, was ich mir vorstellen kann, ist, von oben nach links zu scannen, wo der Unterschied ist. Dann scannen Sie von unten rechts und treffen Sie den Punkt, wo es einen Unterschied gibt.
Aber im schlimmsten Fall ist das O (N * M). Gibt es einen besseren effizienten Algorithmus? Oder kann ich etwas damit machen, wie ich sie repräsentiere, damit Sie einen effizienteren Algorithmus anwenden können? Und beachten Sie, diese Matrix kann sehr groß sein.
"Aber im schlimmsten Fall ist das O (N M). Gibt es einen besseren effizienten Algorithmus?" Wahrscheinlich nicht aufgrund der Dimension der Daten, die O (N M) ist. Viele Matrixoperationen wie diese sind von der Ordnung M N, weil im schlimmsten Fall M
Wenn man den Durchschnittswert betrachtet, ist interessanter, wenn die Differenzbox notwendigerweise ein einzelnes Rechteck innerhalb der gesamten Matrix ist, dann nehme ich an, dass man weniger scannen kann als alle Elemente im Durchschnitt.
Hier ist eine schnelle, obwohl ich hatte: Verfolge das aktuelle Element, rufe dieses XY
aufBeginnen Sie oben links, also ist XY jetzt die obere Ecke
Überprüfen Sie, ob die Elemente XY in beiden gleich sind, wenn nicht gleich gehen Sie zu 3, sonst gehen Sie zu 4
Wenn die Elemente nicht sind, dann haben Sie ein Element der Differenzmatrix. Zeichnen Sie dieses Element auf und suchen Sie dann diese Zeile und Spalte nach den anderen Elementen (vielleicht ist die binäre Suche am schnellsten). Nachdem die Zeile / Spalte durchsucht wurde, haben Sie die Koordinaten der Kanten. Wenn die Elemente nicht gleich sind, gehe zu 4.
Nächster Schritt XY diagonal um ein Element nach unten und ein Element nach rechts verschieben, dann erneut zu 2 gehen
Sobald eine Diagonale abgedeckt ist, müssen Sie die nächste Diagonale testen (ich vermute, dass die Wahl einer neuen Diagonale, die am weitesten von der aktuellen Diagonale entfernt ist, die beste ist, obwohl ich keinen Beweis dafür habe ist die beste Wahl), bis alle Elemente abgedeckt sind. Im schlimmsten Fall ist dies immer noch O (N * M), aber es kann im Durchschnitt schneller sein.
Im Wesentlichen versuchen Sie ein anderes Element so schnell wie möglich zu verwenden. Das Ziel besteht also darin, das erste Element so zu wählen, dass der erwartete Wert der Anzahl der Suchen minimiert wird, um das erste Element zu finden.
Ich möchte nur hinzufügen, dass Sie beim Speichern Ihrer Matrix das Speicherlayout berücksichtigen sollten. Wenn die Matrix in Reihen angeordnet ist, ist es am besten horizontal zu scannen. Wenn es in Spalten angeordnet ist, scannen Sie besser vertikal. Dies führt zu einem ziemlich optimalen Caching-Verhalten.
Das setzt natürlich voraus, dass der fragliche Unterschied tatsächlich in Form eines Rechtecks vorliegt. Wenn es sich um eine andere Form handelt und Sie das umgebende Rechteck wünschen, müssen Sie sowohl Zeilen als auch Spalten scannen, egal was passiert.
Ich denke, der vorgeschlagene Algorithmus ist ein optimaler. Allerdings schlage ich vor, dass Sie die BLAS -Bibliothek ausprobieren, die sehr effizient ist, und vergleichen Sie die Leistung. Es gibt auch eine Bibliothek Boost uBlas , die C ++ - Schnittstelle und