Skiplist

[alzaimar]

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.