Robert Sedgewick: Algorithmen

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


14. Elementare Suchmethoden



Binäre Suche

Wenn die Menge der Datensätze groß ist, kann die Gesamtdauer der Suche beträchtlich verringert werden, indem eine Suchprozedur verwendet wird, die auf der Anwendung des Schemas »Teile und Herrsche« beruht: Teile die Menge der Datensätze in zwei Hälften, bestimme, welchem der zwei Teile der gesuchte Schlüssel angehört, konzentriere dich dann auf diesen Teil. Ein sinnvoller Weg, um diese Mengen zu zerlegen, besteht darin, die Datensätze sortiert zu lassen und dann Feld-Indizes zu verwenden, um den Teil des Feldes zu begrenzen, der gerade bearbeitet wird. Um festzustellen, ob ein gegebener Schlüssel v in einer Tabelle enthalten ist, vergleiche ihn zuerst mit dem Element auf der mittleren Position der Tabelle. Wenn v kleiner ist, muß es sich in der ersten Hälfte der Tabelle befinden; wenn v größer ist, muß es in der zweiten Hälfte enthalten sein. Wende dann diese Methode rekursiv an. (Da nur ein rekursiver Aufruf erforderlich ist, ist es einfacher, die Methode iterativ zu formulieren.) Dies führt unmittelbar zu der folgenden Implementation, für die vorausgesetzt wird, daß das Feld a sortiert ist.

    function binarysearch(v: integer): integer;
      var x,l,r: integer;
      begin
      l:=1; r:=N;
      repeat
        x:=(l+r) div 2;
        if v<a[x].key then r:=x-1 else l:=x+1
      until (v=a[x].key) or (l>r);
      if v=a[x].key 
        then binarysearch:=x
        else binarysearch:=N+1
      end;

Wie bei Quicksort und bei Radix Exchange Sort werden auch bei diesem Verfahren die Zeiger l und r benutzt, um die Teildatei zu begrenzen, die gerade bearbeitet wird. Jedesmal wird die Variable x durch die Schleife so gesetzt, daß sie auf den Mittelpunkt des aktuellen Intervalls zeigt, und dann gibt es drei Möglichkeiten: Entweder bricht die Schleife erfolgreich ab, oder der linke Zeiger wird in x+1 geändert, oder der rechte Zeiger wird in x-1 geändert, je nachdem, ob der gesuchte Wert v gleich dem Wert des Schlüssels des in a[x] gespeicherten Datensatz ist, oder ob er kleiner oder größer als dieser Wert ist.

Abbildung 14.1 zeigt die Teildateien, die bei Anwendung dieser Methode gebildet werden, wenn in einer Tabelle, die durch das Einfügen der Schlüssel A S E A R C H I N G E X A M P L E aufgebaut wurde, das M gesucht wird. Die Intervallgröße wird bei jedem Schritt wenigstens halbiert, daher werden für diese Suche nur vier Vergleiche benötigt. Abbildung 14.2 zeigt ein umfangreicheres Beispiel mit 95 Datensätzen; hier sind für jede beliebige Suche nur sieben Vergleiche notwendig.

Abbildung 14.1
Abbildung 14.1 Binäre Suche.

Abbildung 14.2
Abbildung 14.2 Binäre Suche in einer umfangreicheren Datei.

Eigenschaft 14.3 Binäre Suche erfordert sowohl für erfolgreiche als auch für erfolglose Suche niemals mehr als lg N + 1 Vergleiche.

Diese Eigenschaft folgt unmittelbar aus der Tatsache, daß die Anzahl der Datensätze bei jedem Schritt wenigstens halbiert wird: Eine obere Schranke für die Anzahl der Vergleiche genügt der rekurrenten Beziehung CN = CN/2 + 1 mit C1 = 1, woraus die Behauptung folgt (Formel 2 in Kapitel 6). w.z.b.w.

Man darf nicht übersehen, daß die für das Einfügen neuer Datensätze benötigte Zeit beim binären Suchen groß ist: Es muß dafür gesorgt werden, daß das Feld sortiert bleibt, daher müssen für jeden neuen Datensatz einige Datensätze bewegt werden, um für ihn Platz zu machen. Wenn zum Beispiel ein neuer Datensatz einen kleineren Schlüssel hat als jeder andere Datensatz in der Tabelle, muß jede Eintragung um eine Position verschoben werden. Eine zufällige Einfügung erfordert im Durchschnitt das Bewegen von N/2 Datensätzen. Daher sollte dieses Verfahren nicht für Anwendungen benutzt werden, die viele Einfügungen erfordern. Es ist am besten für Situationen geeignet, in denen die Tabelle im voraus »aufgebaut« werden kann, vielleicht unter Verwendung von Shellsort oder Quicksort, und in denen sie dann für eine große Zahl von (sehr effizienten) Suchoperationen benutzt werden kann.

Bei diesem Algorithmus ist eine gewisse Sorgfalt erforderlich, um Datensätze mit gleichen Schlüsseln richtig zu behandeln: Der zurückgegebene Index könnte in die Mitte eines Blocks aus Datensätzen mit dem Schlüssel v fallen; daher müssen, um alle diese Datensätze zu erfassen, Schleifen verwendet werden, die von diesem Index ausgehend ein Durchsuchen in beide Richtungen vornehmen. Natürlich ist in diesem Fall die Laufzeit für die Suche proportional zu lg N plus der Anzahl der gefundenen Datensätze.

Die Folge der Vergleiche, die beim Algorithmus der binären Suche vorgenommen werden, ist vorherbestimmt: Die verwendete spezielle Folge hängt vom Wert des Schlüssels, der gesucht wird, sowie vom Wert von N ab. Die Struktur der Vergleiche kann mit Hilfe einer binären Baumstruktur einfach beschrieben werden. Abbildung 14.3 zeigt die Struktur der Vergleiche für unser Beispiel einer Menge von Schlüsseln. Zum Beispiel wird beim Suchen nach einem Datensatz mit dem Schlüssel M zuerst ein Vergleich mit H vorgenommen. Da M größer ist, wird es danach mit N verglichen (andernfalls wäre es mit C verglichen worden), dann wird es mit L verglichen, und beim vierten Vergleich wird die Suche dann erfolgreich abgebrochen. Weiter unten betrachten wir Algorithmen, die eine speziell konstruierte binäre Baumstruktur zur Steuerung der Suche benutzen.

Abbildung 14.3
Abbildung 14.3 Vergleichsbaum für die binäre Suche.

Eine mögliche Verbesserung bei der binären Suche besteht in dem Versuch, genauer zu erraten, wo sich der gesuchte Schlüssel innerhalb des aktuellen interessierenden Intervalls befinden könnte (anstatt bei jedem Schritt blindlings das mittlere Element zu verwenden). Dies erinnert an die Art und Weise, wie man eine Nummer in einem Telefonverzeichnis sucht: Falls der gesuchte Name mit B beginnt, schlägt man weiter vorn nach, falls er dagegen mit Y beginnt, sucht man näher beim Ende. Diese Methode, die Interpolationssuche (interpolation search) genannt wird, erfordert lediglich eine einfache Modifikation des obigen Programms. Im obigen Programm wurde die neue Position für die Suche (der Mittelpunkt des Intervalls) mit Hilfe der Anweisung x:=(l+r) div 2 berechnet, welche aus der Beziehung

Formel

abgeleitet wurde. Die Mitte des Intervalls wird berechnet, indem die Hälfte der Länge des Intervalls zum linken Endpunkt addiert wird. Die Interpolationssuche läuft einfach darauf hinaus, daß der Wert 1/2 in dieser Formel durch eine Schätzung ersetzt wird, die angibt, wo sich der Schlüssel innerhalb der verfügbaren Werte befinden könnte: 1/2 wäre geeignet, wenn v in der Mitte des Intervalls von a[l].key bis a[r].key liegen würde, doch ist x:=l+(v-a[l].key)*(r-l) div (a[r].key-a[l].key) eine bessere Wahl. Natürlich setzt dies eine Gleichverteilung der Schlüsselwerte voraus.

Abbildung 14.4
Abbildung 14.4 Interpolationssuche.

Nehmen wir in unserem Beispiel an, daß der i-te Buchstabe des Alphabets durch die Zahl i dargestellt wird. Dann wäre bei der Suche nach M die erste betrachtete Position der Tabelle 9, da 1 + (13 - 1)*(17 - 1)/(24 - 1) = 9,3... Diese Suche wird in nur drei Schritten vollendet, wie Abbildung 14.4 zeigt. Andere Suchschlüssel werden sogar noch effizienter gefunden: Zum Beispiel werden das erste und das letzte Element im ersten Schritt gefunden. Abbildung 14.5 zeigt die Interpolationssuche für die aus 95 Elementen bestehende Datei von Abbildung 14.2; es verwendet nur vier Vergleiche, während bei der binären Suche sieben erforderlich waren.

Abbildung 14.5
Abbildung 14.5 Interpolationssuche in einer umfangreicheren Datei.

Eigenschaft 14.4 Interpolationssuche erfordert sowohl für eine erfolgreiche als auch für eine erfolglose Suche in Dateien mit zufälligen Schlüsseln weniger als lg lg N + 1 Vergleiche.

Der Beweis dieser Tatsache würde weit über den Rahmen dieses Buches hinausgehen. Diese Funktion ist eine sehr langsam wachsende Funktion, die für praktische Zwecke als Konstante betrachtet werden kann: Falls N eine Milliarde beträgt, ist lg lg N < 5. Somit kann jeder Datensatz unter Verwendung von (im Durchschnitt) nur wenigen Zugriffen gefunden werden, was eine wesentliche Verbesserung gegenüber der herkömmlichen Methode der binären Suche ist. w.z.b.w.

Die Interpolationssuche ist jedoch sehr stark von der Voraussetzung abhängig, daß die Schlüssel sehr gut über das Intervall verteilt sind. Durch Schlüssel mit einer sehr ungleichmäßigen Verteilung, die in der Praxis gewöhnlich auftreten, kann es »hereingelegt« werden. Hinzu kommt, daß die Methode einige Berechnungen erfordert: Für kleines N kommen die sich wie lg N verhaltenden Kosten der einfachen binären Suche lg lg N recht nahe, so daß sich der Aufwand des Interpolierens wahrscheinlich nicht lohnen dürfte. Andererseits sollte die Interpolationssuche für große Dateien sicherlich in Betracht gezogen werden, für Anwendungen, wo Vergleiche besonders kostspielig sind, oder für externe Methoden, wo hohe Zugriffskosten auftreten.


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