Vergleich von Suchverfahren mit Beispielen

[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.

Ich würde mich freuen, wenn Jemand einen schnelleren Algorithmus/Datenstruktur findet oder die vorhandenen verbessert. Falls jemand andere schnelle Verfahren hat, dann kann er sie hier posten bzw. das Testprogramm erweitern.

[edit] Update: Auf Nachfrage wurde die THashedStringList aus IniFiles von Borland mit aufgenommen. Neu ist auch, das man angeben kann, ab welcher Dauer eine Reihe während des Messlaufes nicht weiter verfolgt werden soll. Das Laufzeitverhalten einiger Listen degeneriert bei grossen N. Wenn also die Messung des Einfügens einen bestimmten Wert, wird das Verfahren nicht weiter berücksichtigt: Damit man sich keinen Wolf wartet [/edit]

[edit] Update: THashedStringlist wurde mit 'Sorted := True' instantiiert und dadurch unnötig langsam[/edit]

[jfheins]

Nett .. wenn du jetzt nochmal die Verfahren kurz erklären würdest (Dictionary = Stringlist ???)

Was mir aufgefallen ist: Warum hat die blaue Kurve so Zacken, als wäre sie z.B. mit 500.000 langsamer als mit 1.000.000 ?

[alzaimar]

Stringlist= Delphi TStringlist mit Sorted := True und Duplicates := dupIgnore, Suchen per binary search
AVL - Tree: AVL-Baum (Binärer ausgeglichener Baum)
Skiplisten: Verkettete Listen mit zusätzlichen Pointern auf weiter entfernte Elemente (Skip list)
Directories : Hash tabellen (Nein. Nicht zum Rauchen)

Zitat von jfheins:

Was mir aufgefallen ist: Warum hat die blaue Kurve so Zacken, als wäre sie z.B. mit 500.000 langsamer als mit 1.000.000 ?

Wenn Hashtabellen voll sind, werden sie erweitert. Due Größe der vergrößerten Tabelle eine Primzahl, die ungefähr doppelt so gross ist, wie die ursprüngliche Tabelle. Es scheinen 'gute' und 'schlechte' Größen zu geben. Einige sind 'mies'. Warum das so ist, weiss ich nicht.

[Der_Unwissende]

Hey,
was ich ein wenig vermisse ist die gute THashedStringlist. Gab es da einen guten Grund sie nicht mit zu berücksichtigen? Also sonst würde mich die auch noch in deinem Test interessieren, zumal die echt gut schneller ist als die TStringlist und ich würde mal denken, dass da Borland für sorgt, dass immer gute Werte für's Hashen benutzt werden.
Ansonsten nettes Programm!

Gruß Der Unwissende

[alzaimar]

Hi,
Danke für den Tip. Ich hab sie mal eingebaut Im 1.Posting kann man die neue Version laden. Sie misst nun auch nur das Suchen.

[stoxx]

zu den Skiplisten ... hier eine richtig geile Seite mit Vorlesungs Videos !
wow .. da tut sich was an den Unis

http://electures.informatik.uni-frei...2004&chapter=7

[mschaefer]

Moin, moin,

Das ist eine schöne Gegenüberstellung, die einem
viel Arbeit in die falsche Richtung ersparen kann.

Grüße nach Berlin

[hathor]

Hi,

Dictionary ist deutlich am Besten!

Kennt jemand die Media Library von WINAMP?
Da gibt es MAIN.IDX und MAIN.DAT (und einige andere) - gibt es einen DELPHI-Sourcecode, mit dem man auf die Datenbank zugreifen kann?
Mit welchem Datenbankmodell ist sie vergleichbar?

Danke für jede Hilfe!

[abrosda]

Der AVL Tree wird erheblich schneller, wenn nicht jedesmal vor dem einfügen geprüft wird, ob der Key schon im Baum vorhanden ist.
Das setzt natürlich eindeutige Werte voraus.

[Dezipaitor]

wo ist der B(*/+)-Baum ?