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]