Vergleich von Suchverfahren mit Beispielen

[alzaimar]

Im Code der Testsuite hatte sich eine kleine Nachlässigkeit eingeschlichen, die mquadrat entdeckt hat. Eine überarbeitete Version ist im 1.Post zu finden.
Puh, für ein Tutorial über die Datenstrukturen fehlt mir im Augenblick die Zeit, da die Thematik, richtig aufbereitet, doch etwas umfangreich wird. Insbesondere eine Erklärung der Skiplists ist nicht einfach. Sie muss ja verständlich sein. Schaut Euch doch einfach mal die Arbeit von W.Pugh an. Da wird einem doch schwindelig.

[idealist]

@alzaimar: Danke, Super vergleich.

Oft ist der Schlüssel eindeutig, d.h man Braucht keinen AnsiUpperCase oder AnsiCompareText. Dann ändern sich die Ergebnisse im Bereich bis ca 30.000 Einträge. So wird sortierte Liste bis zu 2,5 schneller als Dictionary (Hashtable) und Dictionary wird schneller als Skiplist.

Wenn es möglich ist, zuerst alle Daten in die Liste zu speichen und danach zu sortieren. Dann geht auch Einfügen in die Liste deutlich schneller als in die Dictionary oder SkipListe.
http://img12.imageshack.us/img12/569...hot017y.th.png

[alzaimar]

Danke für das Kompliment.

Natürlich gibt es immer Möglichkeiten, die Datenstrukturen für eigene Bedürfnisse zu optimieren. Allgemeingültig sind sie damit jedoch nicht mehr.
Ein schönes Beispiel hierfür sind Listen, die zuerst befüllt und dann einmalig sortiert werden, um die anschließende Binärsuche zu ermöglichen.

Ich kann mir vorstellen, das alle Strukturen von der Vorgabe profitieren, Schlüssel nicht auf Eindeutigkeit prüfen zu müssen.

[Delphi-Laie]

Zitat von alzaimar:

In Anbetracht der häufig gestellten Fragen nach 'Suchen in einer Liste' und Ähnlichem hab ich mal vier Verfahren verglichen:
- Stringlist
- AVL-Baum
- Skiplist
- Hashlist

Das Testprogramm fügt zunächst Werte in die jeweilige Datenstruktur ein und sucht sie anschließend wieder. Beim Einfügen wird sichergestellt, das der Eintrag nicht schon in der Liste ist.

Hallo alzaimar, erst mal mein Kompliment für diese umfangreiche erfolgreiche Visualsierung!

Mal eine ganz dumme Frage, ich verstehe die Datenstrukturen nämlich nur ansatzweise: Gibt es in den Datenstrukturen eine - wie auch immer gestaltete - Ordnung in der Weise, daß man die Elemente als sortiert bezeichnen kann oder die sich wenigstens für eine Sortierung verwenden läßt? So etwas lese ich aus Deinen Sätzen sowohl hier als auch im Delphiform heraus. Auch mein Gefühl sagt mir, daß jede optimierte, rationelle Suche eine Ordnung in der Elementemenge voraussetzt. Daß ich das AVL-Sort dank externer Unterstützung umgesetzt bekam, weißt Du ja anhand meines Sortierkinos. Ich hatte mir interessehalber mal Deine Quelltexte der Skip- und der Hashlist zu Gemüte geführt und dort in erster Sichtung ein Unterprogramm gesucht, das in der Titelzeile (Beschreibung) die Zeichenkette "sort" enthält - leider Fehlanzeige.

Wo, also an welcher Stelle, kann man konkret bei den beiden letzten - vermutlich auch für die Sortierung geeignetsten - Suchalgorithmen die Sortierung "abgreifen" bzw. "gewinnen"?

Danke für Deine Aufmerksamkeit und Geduld!

Gruß

Delphi-Laie

[alzaimar]

Eine Hashmap ist unsortiert. Die Schlüssel werden anhand eines Hash-Wertes gefunden (zumindest fast).
Eine Skiplist ist eine etwas komplexere mehrfach verkettete Liste, bei der die Schlüssel sortiert vorliegen.

Ich glaube, ich habe bei beiden einen Enumerator implementiert, also sowas wie: Gehe zum 1.Element, Hole das nächste Element bis keine mehr da sind...

[Delphi-Laie]

Zitat von alzaimar:

Eine Hashmap ist unsortiert. Die Schlüssel werden anhand eines Hash-Wertes gefunden (zumindest fast).
Eine Skiplist ist eine etwas komplexere mehrfach verkettete Liste, bei der die Schlüssel sortiert vorliegen.

Ich glaube, ich habe bei beiden einen Enumerator implementiert, also sowas wie: Gehe zum 1.Element, Hole das nächste Element bis keine mehr da sind...

Vielen Dank!

Natürlich hatte ich mich gestern schon mal dezent über die Datenstrukturen „angeschlaut“ und konnte zumindest bei der Skiplist einen Wissenszuwachs erlangen.

Im Prinzip ist mir jetzt schon klar, wie Deine Algorithmen auch für Sortierungen verwandt werden können. Ich werde mich versuchen. Vielleicht gelingt es mir, mein Sortierkino noch mit 1-2 „Turbo(s)“ zu veredeln.

[p80286]

Könntet Ihr mir bezüglich der Skiplist etwas auf die Sprünge helfen?
Die vorhandenen Beispiele und Erklärungen beschreiben die Skipliste ,Daten + 3..X Zeiger auf Nachfolger , wobei der "größte" Zeiger ,beim ersten Listenelement, direkt auf das letzte zeigt, der "zweitgrößte" 2,3 Elemente überspringt und schließlich der "kleinste" alle Elemente miteinander verbindet. OK da kann man beim Suchen "springen" aber ich seh die Logik in dieser Liste nicht. Bei einem Baum ist es ganz simpel rechts herum ist größer, links herum ist kleiner (gut gleich groß gibt es auch noch). Diesen einfach zu erkennenden Ansatz seh ich bei der Skipliste nicht.

Gruß
K-H

[acadam71]

Mein Test: der AVL Baum benötigt im Testprogramm bei 100.000 Inserts bereits 1 Sekunde. Mein Laptop: Duo Centrino mit 2 GHz.

Ich habe einen AVL Baum selbst programmiert, der schafft in 1 Sekunde aber fas 1 Mio Inserts. Wie kann das sein? Er hat weit weniger Quellcode (357 Zeilen) und benutzt keinen Assembler. Und trotzdem ist er 10 mal so schnell, und das obwohl ich sogar GUIDS (Jeweils 40 Zeichen) einfüge anstatt wie im Testprogramm Integer Werte. Offensichtlich ist der dort benutzte Quellcode nicht gerade optimal, so dass ich davon ausgehe, dass der AVL Baum die beste Datenstruktur ist. Abgesehen davon macht er alle Funktionen wie Insert, Delete, Update und Select(suche) in O(log(n)) und zwar im WORST CASE! So weit mir die Theorie vertraut ist, schafft das keine der anderen Strukturen.

Edit: Mein Quellcode für den AVL ist von Niklaus Wirth, aber auf Objekte angepasst (anstatt Zeiger).

[pertzschc]

Zitat von alzaimar:

Insbesondere eine Erklärung der Skiplists ist nicht einfach.

Hallo alzaimar,

ich denke, ich habe einen Fehler entdeckt:

Delphi-Quellcode:

  TcsStringSkipList = Class
...
  Public
..
    Function Find (aKey : String; Var aInfo : Pointer) : Boolean;
    Procedure CurrentData (Var aKey : String; aInfo : Pointer); // aInfo ist nicht als var deklariert
..
    End;

Damit kann man beim Iterieren keinen Pointer zurückbekommen. Beispiel:

Delphi-Quellcode:

      // setze auf 1. satz
      FSDBObjectList.First;
      // schleife bis ende der liste erreicht
      while (not (FSDBObjectList.EndOfList)) do begin
        // nimm aktuellen versicherten
        versicherter := nil;
        aPointer := nil;
        testStr := '';
        FSDBObjectList.CurrentData(testStr, aPointer); // ohne das var ist aPointer immer nil
        if (aPointer <> nil) then begin
          versicherter := TVersicherter(aPointer);
          ..
        end;
        FSDBObjectList.Next;
      end;

mit

Delphi-Quellcode:

..
    Function Find (aKey : String; Var aInfo : Pointer) : Boolean;
    Procedure CurrentData (Var aKey : String; var aInfo : Pointer); // analog zu Find()
..

funktioniert das Ganze.

Liege ich mit meiner Vermutung richtig?
Gruß,
Christoph

[webcss]

Hallo,

hab mal ein bisschen damit gespielt und mal einen Red-Black-Tree mit einbezogen.
Die Ergebnisse sind ernüchternd, der Red-Black Tree outperformt alles andere, auch die vielzitierte SkipList.
Im Anhang mal der verwendete RBTree Code.

Zum Wertevergleich diente TListSortCompare wie folgt

Delphi-Quellcode:

function rbTreeCompare(Item1, Item2: pointer): Integer;
begin
  if Integer(Item1) < Integer(Item2) then
    Result:= -1
  else if Integer(Item1) > Integer(Item2) then
    Result:= 1
  else
    Result:= 0;
end;