Robert Sedgewick: Algorithmen

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


14. Elementare Suchmethoden



Sequentielle Suche

Die einfachste Methode des Suchens besteht darin, die Datensätze einfach in einem Feld zu speichern. Wenn ein neuer Datensatz eingefügt werden soll, setzen wir ihn an das Ende des Feldes; wenn eine Suche ausgeführt werden soll, durchsuchen wir das Feld sequentiell. Das folgende Programm zeigt eine Implementation der grundlegenden Funktionen unter Verwendung dieser einfachen Organisation und veranschaulicht einige der Vereinbarungen, die wir bei der Implementation von Suchmethoden verwenden werden.

    type node= record key,info: integer end;
    var a: array[0..maxN] of node;
        N: integer;
    procedure initialize;
      begin N:=0 end;
    function seqsearch(v: integer; x: integer): integer;
      begin
      a[N+1].key:=v;
      if x<=N then
        repeat x:=x+1 until v=a[x].key;
      seqsearch:=x
      end;
    function seqinsert(v: integer): integer;
      begin
      N:=N+1; a[N].key:=v;
      seqinsert:=N;
      end;

Das obige Programmsegment verarbeitet Datensätze, die ganzzahlige Schlüssel (key) und »zugehörige Information« (info) beinhalten. Wie beim Sortieren wird es in vielen Anwendungen notwendig sein, die Programme so zu erweitern, daß sie kompliziertere Datensätze und Schlüssel behandeln können, doch wird dies keine grundsätzliche Änderung in den Algorithmen mit sich bringen. Zum Beispiel könnte info durch einen Zeiger ersetzt werden, der auf eine beliebig komplizierte Datensatz-Struktur weist. In einem solchen Fall kann dieses Feld des Datensatzes als die eindeutige Kennzeichnung des Datensatzes dienen, die zur Unterscheidung zwischen Datensätzen mit gleichen Schlüsseln benutzt wird.

Die Prozedur seqsearch besitzt in dieser Implementation zwei Argumente: den Wert des Schlüssels, der gesucht wird, und einen sich auf das Feld beziehenden Index (x). Der Index wurde mit aufgenommen, um den Fall zu behandeln, daß verschiedene Datensätze den gleichen Schlüsselwert haben: Indem wir, bei t=0 beginnend, nacheinander t: = seqsearch (v, t) ausführen, können wir nacheinander t auf den Index jedes Datensatzes mit dem Schlüsselwert v setzen.

Es wird ein Markierungs-Datensatz verwendet, der den gesuchten Wert des Schlüssels enthält; dadurch ist gewährleistet, daß die Suche immer beendet wird und aus diesem Grunde in der inneren Schleife nur eine Abbruchbedingung erfordert. Nachdem die innere Schleife beendet ist, kann durch einen Test, ob der zurückgegebene Index größer als N ist, festgestellt werden, ob die Suche die Marke oder einen Schlüssel aus der Tabelle gefunden hat. Dies geschieht analog zur Verwendung von Marken in den Kapiteln 8 bis 12, wo diese den kleinsten oder größten Schlüsselwert enthielten, um die Programmierung der inneren Schleife diverser Suchalgorithmen zu vereinfachen.

Eigenschaft 14.1 Die sequentielle Suche (Implementation mit einem Feld) benötigt (immer) N + 1 Vergleiche für eine erfolglose Suche und (durchschnittlich) ungefähr N/2 Vergleiche für eine erfolgreiche Suche.

Für eine erfolglose Suche folgt diese Eigenschaft unmittelbar aus dem Programm: Um festzustellen, daß ein Datensatz mit irgendeinem bestimmten Schlüssel nicht vorhanden ist, muß jeder Datensatz betrachtet werden. Für eine erfolgreiche Suche beträgt, wenn wir annehmen, daß jeder Datensatz mit der gleichen Wahrscheinlichkeit gesucht wird, die durchschnittliche Anzahl der Vergleiche

Formel

was genau der Hälfte der Kosten einer erfolglosen Suche entspricht. w.z.b.w.

Die sequentielle Suche kann offensichtlich in natürlicher Weise an eine Darstellung der Datensätze in Form einer verketteten Liste angepaßt werden. Ein Vorteil dieser Vorgehensweise besteht darin, daß es einfach wird, dafür zu sorgen, daß die Liste sortiert bleibt, was zu einer schnelleren Suche führt:

    type link=^.node;
          node;= record key,info: integer; next: link end;
    var head,t,z: link;
        i: integer;
    procedure initialize;
      begin
      new(z); z^.next:=z;
      new(head); head^.next:=z;
      end;
    function listsearch(v: integer; t: link): link;
      begin
      z^.key:=v;
      repeat t:=^.next until v<=t^.key;
      if v=t^.key 
        then listsearch:=t
        else listsearch:=z
      end;

Bei Verwendung einer sortierten Liste kann eine Suche als erfolglos abgebrochen werden, wenn ein Datensatz mit einem Schlüssel gefunden wird, der größer als der gesuchte Schlüssel ist. Daher muß im Durchschnitt für eine erfolglose Suche nur ungefähr die Hälfte der Datensätze betrachtet werden (und nicht alle). Die sortierte Reihenfolge kann leicht aufrecht erhalten werden, da ein neuer Datensatz einfach an der Stelle in die Liste eingefügt werden kann, an der die erfolglose Suche abbricht:

    function listinsert(v: integer; t: link): link;
      var x: link;
      begin
      z^.key:=v;
      while t^.next^.key<v do t:=t^.next;
      new(x); x^.next:=t^.next; t^.next:=x;
      x^.key:=v;
      listinsert:=x;
      end;

Wie gewöhnlich bei verketteten Listen ermöglichen ein Pseudoknoten head am Kopf und ein Endknoten z eine erhebliche Vereinfachung des Programms. Demzufolge bewirkt der Aufruf listinsert (v, head) das Einsetzen eines neuen Knotens mit dem Schlüssel v in die Liste, auf die das Feld next von head zeigt, und listsearch funktioniert ähnlich. Wiederholte Aufrufe von listsearch unter Verwendung der zurückgegebenen Verkettungen bewirken das Zurückgeben von Datensätzen mit gleichen Schlüsseln. Der Endknoten z wird in der gleichen Weise wie oben als Marke benutzt. Wenn listsearch z zurückgibt, war die Suche erfolglos.

Eigenschaft 14.2 Die sequentielle Suche (Implementation mit einer sortierten Liste) benötigt (durchschnittlich) sowohl für eine erfolgreiche als auch für eine erfolglose Suche ungefähr N/2 Vergleiche.

Für eine erfolgreiche Suche ist die Situation die gleiche wie zuvor. Für eine erfolglose Suche gilt, wenn wir annehmen, daß die Suche mit gleicher Wahrscheinlichkeit beim Endknoten z oder bei jedem der Elemente in der Liste abgebrochen wird (was für eine Reihe von »zufälligen« Suchmodellen der Fall ist), daß die durchschnittliche Anzahl der Vergleiche

Formel

beträgt, also etwas mehr als die Hälfte der Kosten, die ohne Sortieren entstehen. w.z.b.w.

Falls etwas über die relative Häufigkeit des Zugriffs auf verschiedene Datensätze bekannt ist, können beträchtliche Einsparungen oft einfach dadurch erzielt werden, daß man die Datensätze günstig anordnet. Die »optimale« Anordnung besteht darin, den Datensatz, auf den am häufigsten ein Zugriff erfolgt, an den Anfang zu setzen, den Datensatz mit der zweitgrößten Häufigkeit des Zugriffs auf die zweite Position usw. Diese Methode kann sehr effizient sein, besonders dann, wenn nur auf eine kleine Menge von Datensätzen häufig ein Zugriff erfolgt.

Wenn keine Information über die Häufigkeit des Zugriffs verfügbar ist, kann mittels einer »selbstorganisierenden« Suche eine Annäherung an die optimale Anordnung realisiert werden: Jedesmal, wenn ein Zugriff auf einen Datensatz erfolgt, bewege man diesen an den Anfang der Liste. Diese Methode läßt sich günstiger implementieren, wenn eine Implementation mittels einer verketteten Liste verwendet wird. Natürlich hängt die Laufzeit der Methode von den Verteilungen des Zugriffs auf die Datensätze ab, so daß es sich schwer vorhersagen läßt, wie sie sich im allgemeinen Fall verhält. Sie eignet sich jedoch gut für den recht häufig auftretenden Fall, daß die meisten Zugriffe auf einen Datensatz eng aufeinander folgen.


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