Einzelnen Beitrag anzeigen

alzaimar
(Moderator)

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

Vergleich von Suchverfahren mit Beispielen

  Alt 21. Okt 2005, 19:55
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]
Angehängte Dateien
Dateityp: zip testlists_126.zip (318,6 KB, 470x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat