Vergleich von Suchverfahren mit Beispielen

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