Suche in einem Array mit hohen Dimensionen mit bestimmten Eigenschaften

Es gibt Omega (n ^ 2) -Punkte, deren Koordinaten sich zu n - 1 addieren. Über die Vergleichbarkeit der Werte dieser Punkte untereinander ist nichts a priori bekannt. Im schlimmsten Fall müssen alle Punkte überprüft werden . Eine Obergrenze, die mit konstanten Faktoren übereinstimmt, wird durch Ausführen des 2D-Algorithmus in jedem Konstanten-z-Segment bereitgestellt.

Führen Sie für jeden Wert (z. B. v1 ) die folgenden Schritte aus:

1. Führen Sie den 2D-Algorithmus für die vier Würfelflächen aus, die tangential zur X-Achse liegen (Y = 0, Y = n-1, Z = 0, Z = n-1). Indexieren Sie den resultierenden Satz übereinstimmender Zellen (X, Y, Z) für den nächsten Schritt mit der X-Koordinate.
2. Führen Sie den 2D-Algorithmus für alle n Schnitte entlang der X-Achse (X = 0..n-1) aus und verwenden Sie das Ergebnis von Schritt 1, um den ersten Grenzpunkt für den 2D-Algorithmus zu initialisieren. Wenn für die angegebene x-Koordinate keine übereinstimmenden Zellen vorhanden sind, fahren Sie fortlaufend mit dem nächsten Segment fort.

Im schlimmsten Fall wird die Komplexität O (O (2D-Algorithmus) * n) sein.

Halten Sie für mehrere Werte ( v2 usw.) einen Cache mit Funktionsauswertungen und führen Sie den Algorithmus für jeden Wert erneut aus. Für 100 ^ 3 würde ein dichtes Array ausreichen.

Es könnte nützlich sein, dies als einen Isoflächen-Extraktionsalgorithmus zu betrachten, obwohl Ihre Monotonitätseinschränkung dies vereinfacht.

Wenn das 3D-Array in jeder Dimension monoton nicht abnimmt, wissen wir, dass

dann kann kein Element des Unterarrays f(x0...x1, y0...y1, z0...z1) einen interessanten Punkt enthalten. Um dies zu sehen, betrachten Sie zum Beispiel das

gilt für jedes (x, y, z) des Unterarrays und eine ähnliche Beziehung gilt (mit umgekehrter Richtung) für (x1, y1, z1) . Somit sind f(x0, y0, z0) und f(x1, y1, z1) jeweils der Minimal- und Maximalwert des Sub-Arrays.

Ein einfacher Suchansatz kann dann unter Verwendung eines rekursiven Unterteilungsschemas implementiert werden:

Der Code akzeptiert grundsätzlich ein Sub-Array und überspringt die Suche einfach, wenn das unterste Element zu groß oder das oberste Element zu klein ist, und teilt das Array ansonsten in 8 Sub-Cubes auf. Die Rekursion endet, wenn das Sub-Array klein ist (2x2x2 oder weniger) und in diesem Fall ein vollständiger Scan ausgeführt wird.

Experimentell fand ich heraus, dass mit diesem recht einfachen Ansatz ein Array mit 100x200x300 Elementen, das durch das Element f(i,j,k) bis max(f(i-1,j,k), f(i,j-1,k), f(i,j,k-1)) + random(100) erzeugt wurde, nach dem mittleren Wert und t = 1 gesucht werden kann und nur etwa 3% der Elemente (25 Elemente) überprüft werden überprüft für jedes Element im Bereich gefunden).

Da die Funktion nicht abnimmt, denke ich, dass Sie etwas mit binären Suchen machen können.
Innerhalb eines Vektors (x, 1, 1) (Spalte) können Sie eine binäre Suche durchführen, um den Bereich zu finden, der Ihrer Anforderung entspricht, die O(log(n)) wäre.
Um herauszufinden, in welche Spaltenvektoren Sie hineinschauen können, können Sie eine binäre Suche über (x, y, 1) (slices) -Vektoren durchführen, indem Sie nur den ersten und letzten Punkt prüfen, um zu wissen, ob der Wert in ihnen fallen kann.% Co_de%.
Um zu wissen, in welchen Slices Sie suchen müssen, können Sie den gesamten Cube nach den 4 Punkten durchsuchen ( O(log(n)) ), die (0, 0), (x, 0), (x, y), (0, y) benötigen.
Insgesamt wird also der Algorithmus O(log(n)) annehmen, wobei log(z) + a * log(y) + b * log(x) die Anzahl der übereinstimmenden Schichten und a die Anzahl der übereinstimmenden Spalten ist.
Naiv berechnet den schlimmsten Fall ist b .