Datenstruktur, die eine bestimmte Abfrage auf eine Reihe von 2D-Punkten

Question

Ich habe eine Reihe von 2D-Punkten zu unterstützen, und ich möchte in der Lage sein die folgende Abfrage mit Argumenten zu machen x_min und n: Was sind die n Punkte mit dem größten y die haben x > x_min?

in Ruby umformulieren:

class PointsThing 
    def initialize(points) 
    @points = points 
    end 

    def query(x_min, n) 
    @points.select { |point| point.x > x_min }.sort_by { |point| point.y }.take(n) 
    end 
end 

meine Klasse Im Idealfall würde auch einen Einsatz unterstützen und den Betrieb löschen.

Ich kann mir nicht eine Datenstruktur dafür vorstellen, die die Abfrage in weniger als O (| @points |) Zeit ausführen würde. Kennt jemand einen?

Answer 1

Die Punkte nach x absteigend sortieren. Fügen Sie sie für jeden Punkt in Reihenfolge in einen purely functional rot-schwarzen Baum ein, geordnet nach y absteigend. Bewahren Sie alle Zwischenbäume in einem Array auf.

Um ein bestimmtes x_min nachzuschlagen, verwenden Sie die binäre Suche, um den Zwischenbaum zu finden, in dem genau die Punkte mit x> x_min eingefügt wurden. Durchquere diesen Baum, um die ersten n Punkte zu finden.

Die Kosten für die Vorverarbeitung sind O (p log p) in Zeit und Raum, wobei p die Anzahl der Punkte ist. Die Abfragezeit ist O (log p + n), wobei n die Anzahl der Punkte ist, die in der Abfrage zurückgegeben werden sollen.

Answer 2

Wenn Ihre Daten nicht sortiert sind, haben Sie keine andere Wahl als jeden Punkt zu überprüfen, da Sie nicht wissen können, ob es einen anderen Punkt gibt, für den y größer ist als der aller anderen Punkte und für welchen x > x_min. Kurz gesagt: Sie können nicht wissen, ob ein anderer Punkt enthalten sein sollte, wenn Sie sie nicht alle überprüfen.

In diesem Fall würde ich annehmen, dass es unmöglich wäre, sub lineare Zeit nachzuschlagen, wie Sie verlangen, da Sie sie alle überprüfen müssen. Der beste Fall für die Suche wäre linear.

Wenn Ihre Daten sortiert werden, dann Ihre beste Fall konstante Zeit sein wird (alle n Punkte sind diejenigen mit dem größten y) und schlimmsten Fall wäre linear (alle n Punkte sind solche mit mindestens y). Der durchschnittliche Fall wäre näher an der Konstante Ich denke, wenn Ihre x und x_min beide in einem bestimmten Bereich grob zufällig sind.

Wenn Sie möchten, dass dies skaliert wird (dh Sie könnten große Werte von n haben), sollten Sie auch den resultierenden Satz sortiert halten, da Sie neue potenzielle Punkte überprüfen und den niedrigsten Wert löschen müssen Wert beim Einfügen (wenn Größe> n). Mit einem Baum kann dies Log-Zeit sein.

Also, um die ganze Sache zu tun, ist der schlimmste Fall für unsortierte Punkte, in welchem ​​Fall Sie auf nlog (n) Zeit suchen. Sortierte Punkte sind besser, in diesem Fall betrachtest du den durchschnittlichen Fall der log (n) -Zeit (wiederum unter der Annahme grob zufällig verteilter Werte für x und x_min), was ja sublinear ist.

---

Falls es nicht auf den ersten offensichtlich, warum sortierten Punkte haben konstante Zeit zu durchsuchen, werde ich schnell, dass hier gehen.

Wenn die n Punkte mit den größten y Werten alle x > x_min (der beste Fall) hatten, dann greifen Sie nur was Sie brauchen, von oben, so dass der Fall offensichtlich ist.

Für den durchschnittlichen Fall, angenommen grob zufällig verteilt x und x_min, sind die Chancen, dass x > x_min im Grunde die Hälfte. Für beliebige zwei Zufallszahlen a und b gilt a > b ebenso wahrscheinlich wie b > a. Das Gleiche gilt für x und x_min; x > x_min ist ebenso wahrscheinlich wahr wie x_min > x, was 0,5 Wahrscheinlichkeit bedeutet. Dies bedeutet, dass für Ihre Punkte im Durchschnitt jeder zweite geprüfte Punkt Ihrer Anforderung x > x_min entspricht. Im Durchschnitt werden Sie also 2n Punkte prüfen, um die n höchsten Punkte zu finden, die Ihren Kriterien entsprechen. Also der beste Fall war c Zeit, Durchschnitt ist 2c, die immer noch konstant ist.

Beachten Sie jedoch, dass bei Werten von n, die sich der Größe des Sets annähern, dies die Tatsache verdeckt, dass Sie das gesamte Set durchgehen und es im Wesentlichen wieder in die lineare Zeit bringen.Daher gilt meine Behauptung, dass es sich um eine konstante Zeit handelt, nicht, wenn Sie zufällige Werte von n im Bereich der Größe Ihrer Menge annehmen.

Wenn dies keine rein akademische Frage ist und durch ein konkretes Bedürfnis ausgelöst wird, dann kommt es auf die Situation an.

(bearbeiten) Ich habe gerade festgestellt, dass meine Constant-Time-Assertions eine Datenstruktur angenommen haben, wo Sie direkten Zugriff auf den höchsten Wert haben und sequenziell zu niedrigeren Werten gehen können. Wenn die Datenstruktur, die Ihnen zur Verfügung gestellt wird, nicht zu dieser Beschreibung passt, ist das natürlich nicht der Fall.

Answer 3

Einige Vorberechnung würde in diesem Fall helfen.

Erste Partition der Satz von Punkten unter x_min als Pivot-Element.

dann zum Satz von Punkten auf der rechten Seite von x_min build a max_heap basierend auf Y-Koordinaten liegen.

Führen Sie nun Ihre Abfrage wie folgt aus: Führen Sie n extract_max-Operationen auf dem integrierten max_heap aus.

Die Laufzeit der Anfrage log X + log (X-1) + ..... log (X (n-1))

log X wäre: Für die Zuerst extrahiere max Operation.

log X-1: Für den zweiten Extrakt max Operation und so weiter.

X: Größe des ursprünglichen Max Heap.

Selbst im schlimmsten Fall, wenn Ihr n < < X, Es wäre genommen O (n X log).

Answer 4

Notation

Let P die Menge der Punkte sein.

Lassen Sie top_y (n, x_min) beschreiben Sie die Abfrage zum Sammeln der n Punkte von P mit den größten y-Koordinaten unter denen mit x-Koordinate größer als oder gleich `x_min '.

Lassen Sie x_0 das Minimum von x-Koordinaten in Ihrem Punktsatz sein. Teilen Sie die x-Achse rechts von x_0 in einen Satz von links geschlossenen, rechten offenen Intervallen I_i durch die Menge x-Koordinaten des Punktsatzes P so ein, dass min(I_i) die i -te aber kleinste x-Koordinate von P ist. Definieren Sie den Koordinatenrang r(x) von x als Index des Intervalls x ist ein Element von oder 0 wenn x < x_0.

Beachten Sie, dass r(x) in O(log #({I_i})) mithilfe eines binären Suchbaums berechnet werden kann.

einfache Lösung

1. Sortieren Sie Punkt eingestellt durch Y-Koordinaten abnimmt und speichern dieses Array A in Zeit und Raum O(#P log #P)O(#P).

2. Prozess Jede Abfrage top_y (n, x_min) durch diese Anordnung in Reihenfolge durchquert, überspringt Artikel A_i: A_i.x < x_0, alle anderen Einträge zu zählen, bis der Zähler erreicht n oder Sie sind am Ende der A. Diese Verarbeitung dauert O(n) Zeit und O(1) Raum.

Beachten Sie, dass dies bereits ausreichend sein kann: Abfragen top_y (n_0, a_0); a_0 < min { p.x | p \in P }, n_0 = c * #P, c = const Schritt erfordern 1 sowieso und für n << #P und ‚selten‘ fragt alle weiteren Optimierungen waren nicht die Mühe wert.

Observation

1. Betrachten wir die Sequenzen s_i, s_ (i + 1) of points with x-coordinates greater than or equal to min (I_I), min (I_ (i + 1)) , ordered by decreasing y-coordinate. s_ (i + 1) is a strict subsequence of s_i`.

2. Wenn p_1 \in s_(i+1) und p_2.x >= p_1.x dann p_2 \in s_(i+1).

Raffinierte Lösung

Eine verfeinerte Datenstruktur ermöglicht O(n) + O(log #P) Abfrage Verarbeitungszeit.

Kommentieren Sie das Array A aus der einfachen Lösung mit einem 'Nachfolger-Versand' für genau diese Elemente A_i mit A_(i+1).x < A_i.x; Diese Versanddaten würden aus einem Array disp:[r(A_(i+1).x) + 1 .. r(A_i.x)] von A -Indexes des nächsten Elements in A bestehen, dessen x-Koordinate mindestens so hoch wie der Index in disp rangiert. Die angegebenen Versandindizes genügen für die Verarbeitung der Abfrage, da ...

• ... disp[j] = disp[r(A_(i+1).x) + 1] für jede j <= r(A_(i+1).x).
• ... für jede x_min mit r(x_min) > r(A_i.x) würde der Algorithmus nicht hier

Der richtige Index disp ist r(x_min) zuzugreifen, die während einer Abfrage konstant bleibt und nimmt somit O(log #P) einmal pro Abfrage zu berechnen, während die Index-Auswahl selbst ist O(1) bei jedem A Element.

disp kann vorberechnet werden. No 2 disp Einträge über alle disp Arrays sind identisch (Proof übersprungen, aber es ist einfach [;-)] zu sehen, die Konstruktion gegeben). Daher kann die Konstruktion von disp Arrays stack-based in einem einzigen Sweep durch den in A sortierten Punktsatz durchgeführt werden.Da es #P Einträge gibt, dauert die disp Struktur O(#P) Raum und O(#P) Zeit zu konstruieren, wird von Raum und Zeit Anforderungen für Y-Sortierung dominiert. In gewissem Sinne ist diese Struktur also kostenlos.

Zeitaufwand für die Suche nach top_y(n,x_min)

• Computing r(x_min): O(log #P);
• Durchgang durch A: O(n);