Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


26. Bereichssuche



Elementare Verfahren

Im zweidimensionalen Fall ist unser »Bereich« eine Fläche in der Ebene. Der Einfachheit halber betrachten wir das Problem der Bestimmung aller Punkte, deren x-Koordinaten innerhalb eines gegebenen x-Intervalls und deren y-Koordinaten innerhalb eines gegebenen y-Intervalls liegen, das heißt, wir suchen alle Punkte, die innerhalb eines gegebenen Rechtecks liegen. Demzufolge setzen wir einen Typ rectangle voraus, der einen aus vier ganzen Zahlen bestehenden record darstellt, bei denen es sich um die Endpunkte des horizontalen und vertikalen Intervalls handelt. Unsere grundlegende Operation besteht darin zu testen, ob ein Punkt innerhalb eines gegebenen Rechtecks liegt, so daß wir eine Funktion insiderect(p: point; rect: rectangle) einführen, die dies in der offensichtlichen Weise überprüft und true zurückgibt, falls p in rect liegt. Unser Ziel ist es, alle Punkte zu finden, die innerhalb eines gegebenen Rechtecks liegen, und dafür so wenige Aufrufe von insiderect wie möglich zu verwenden.

Der einfachste Weg zur Lösung dieses Problems ist sequentielles Suchen: Durchsuche alle Punkte und prüfe jeden, um festzustellen, ob er innerhalb des vorgegebenen Bereichs liegt (durch Aufrufen von insiderect für jeden Punkt). Dieses Verfahren wird tatsächlich in vielen Datenbanken angewandt, da es sich leicht verbessern läßt, indem man die Anfragen »bündelt« und bei einem Durchsuchen der Punkte gleichzeitig die Prüfung betreffs vieler verschiedener Anfragen vornimmt. Für eine sehr umfangreiche Datenbank, bei der sich die Daten auf einem externen Gerät befinden und die zum Einlesen benötigte Zeit der bei weitem dominierende Kostenfaktor ist, kann dies eine sehr sinnvolle Methode sein: Man sammle so viele Anfragen, wie in den internen Speicher passen, und führe in einem Durchlauf der umfangreichen externen Datei die Prüfung betreffs aller dieser Anfragen durch. Falls jedoch diese Bündelung unzweckmäßig oder die Datenbank etwas kleiner ist, stehen weit bessere Verfahren zur Verfügung.

Eine einfache erste Verbesserung der sequentiellen Suche ist die direkte Anwendung eines bekannten eindimensionalen Verfahrens längs einer oder mehrerer der Dimensionen, in denen zu suchen ist. Abbildung 26.2 zeigt ein Beispiel eines den Suchbereich darstellenden Rechtecks für unsere Beispiel-Punktmengen.

Abbildung 26.2
Abbildung 26.2 Zweidimensionales Bereichssuchen.

Eine Vorgehensweise besteht darin, die Punkte zu bestimmen, deren x-Koordinaten innerhalb des durch das Rechteck vorgegebenen x-Bereichs liegen, und dann die y-Koordinaten dieser Punkte zu prüfen, um zu ermitteln, ob die Punkte im Rechteck liegen oder nicht. Demzufolge werden Punkte, die nicht im Rechteck liegen können, da ihre x-Koordinaten außerhalb des vorgegebenen Bereichs liegen, niemals betrachtet. Diese Methode wird Projektion genannt; offenbar könnten wir auch auf y projizieren. Für unser Beispiel würden wir E, C, H, F und I bei einer Projektion auf x in der oben beschriebenen Weise prüfen, und wir würden O, E, F, K, P, N und L bei einer Projektion auf y prüfen. Beachten Sie, daß die gesuchte Punktmenge (E und F) genau aus denjenigen Punkten besteht, die in beiden Projektionen erscheinen.

Falls die Punkte gleichmäßig in einem rechteckigen Bereich verteilt sind, ist es sehr einfach, die durchschnittliche Anzahl der geprüften Punkte zu berechnen. Der Anteil der Punkte, der in einem gegebenen Rechteck zu erwarten wäre, ist einfach gleich dem Verhältnis der Fläche dieses Rechtecks zur Fläche des gesamten Gebiets; der zu erwartende Anteil der Punkte, die bei einer Projektion auf x geprüft werden, ist gleich dem Verhältnis der Breite des Rechtecks zur Breite des Bereichs; analoges gilt für eine Projektion auf y. Für unser Beispiel bedeutet die Verwendung eines 4x6-Rechtecks in einem 16x16-Gebiet, daß 3/32 der Punkte im Rechteck, 1/4 der Punkte in einer Projektion auf x und 3/8 der Punkte in einer Projektion auf y zu erwarten wären. Offensichtlich ist es unter solchen Umständen am besten, auf diejenige Achse zu projizieren, die dem kleineren der beiden Maße des Rechtecks entspricht. Andererseits ist es leicht, Situationen zu konstruieren, in denen die Methode der Projektion ein dürftiges Ergebnis liefert: Wenn zum Beispiel die Punktmenge die Form eines »L« besitzt und die Suche einen Bereich betrifft, der nur den Punkt an der Ecke des »L« umfaßt, wird bei der Projektion auf jede der Achsen nur die Hälfte der Punkte eliminiert.

Auf den ersten Blick scheint es, daß die Methode der Projektion dahingehend verbessert werden könnte, daß man die Punkte, die innerhalb des x-Bereichs liegen, und die Punkte, die innerhalb des y-Bereichs liegen, irgendwie schneidet. Versuche, das zu tun, ohne im ungünstigsten Fall entweder alle Punkte im x-Bereich oder alle Punkte im y-Bereich zu prüfen, führen vor allem dazu, daß man die raffinierteren Verfahren zu schätzen weiß, denen wir uns nun zuwenden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]