AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Vergleich von Suchverfahren mit Beispielen

Vergleich von Suchverfahren mit Beispielen

Ein Thema von alzaimar · begonnen am 21. Okt 2005 · letzter Beitrag vom 18. Mär 2010
Antwort Antwort
Seite 3 von 5     123 45   
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#21

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 17. Jan 2009, 09:18
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
idealist

Registriert seit: 3. Jul 2008
8 Beiträge
 
#22

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 14. Aug 2009, 09:25
@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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#23

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 14. Aug 2009, 11:11
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.427 Beiträge
 
Delphi 10.1 Berlin Starter
 
#24

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 9. Nov 2009, 11:34
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#25

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 9. Nov 2009, 18:33
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...
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.427 Beiträge
 
Delphi 10.1 Berlin Starter
 
#26

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 9. Nov 2009, 19:14
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.
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.390 Beiträge
 
Delphi 7 Personal
 
#27

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 10. Nov 2009, 10:07
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
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
acadam71

Registriert seit: 3. Jan 2006
8 Beiträge
 
#28

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 21. Nov 2009, 15:58
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).
  Mit Zitat antworten Zitat
pertzschc

Registriert seit: 29. Jul 2005
Ort: Leipzig
293 Beiträge
 
Delphi 2010 Professional
 
#29

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 23. Nov 2009, 19:25
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
  Mit Zitat antworten Zitat
webcss

Registriert seit: 10. Feb 2006
255 Beiträge
 
Delphi XE2 Professional
 
#30

Re: Vergleich von Suchverfahren mit Beispielen

  Alt 16. Mär 2010, 10:57
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;
Angehängte Dateien
Dateityp: pas rbtree_850.pas (13,6 KB, 46x aufgerufen)
"Wer seinem Computer Mist erzählt, muss immer damit rechnen..." (unbekannt)
"Der Computer rechnet damit, dass der Mensch denkt..." (auch unbekannt)
mein blog
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:42 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf