Ich brauchte mal eine schnelle sortierte Liste. AVL-Bäume waren zu komplex und wegen des Overheads beim ausbalancieren nicht geeignet. Eine Hash-Tabelle kam auch nicht in Frage, weil die Elemente sortiert ausgegeben werden mussten. Und eine Liste erstellen, um sie zu sortieren, kam auch nicht in Frage, weil es ja *schnell* gehen muss.
Ich stiess auf die SkipList, eine echte Höllenmaschine. Die Theorie hinter dem Verfahren ist pervers, das Teil selbst einfach genial.
Hier eine Version, die zu Int64-Schlüsseln einen Pointer abspeichert.
Über
List.Insert (Key, Data) fügt man ein Element ein, mit
List.Delete (Key) wird es wieder gelöscht, mit
List.Find (Key, Info): Boolean sucht man einen Eintrag. Wem das noch zu komplex ist, der kann es auch mit
List.Contains (Key) : Boolean noch einfacher bekommen. Weiterhin kann man mit
List.First zum ersten und mit
List.Next zum nächsten Element springen, mit
CurrentData(Key, Data) die aktuellen Daten auslesen, bis die Funktion
List.EndOfList den Wert
True liefert.
Der optionale Parameter aMaxLevel im Konstruktor dient Testzwecken und kann weggelassen werden.
Vergleicht doch mal die Performance. Den Code habe ich vom
Originalmanuskript des Verfassers in Delphi übersetzt. Man kann ihn natürlich noch verbessern. Interessant ist der Randomgenerator, der die Zufallszahlen genau in der Verteilung liefert, die das Verfahren benötigt.
Viel Spass.