Drastische Performanceeinbuße bei Linked List mit Objects

[alzaimar]

cruiser: Unterm Strich ist so eine Liste schneller als eine Linked List, vor allen Dingen, wenn Du in der Liste suchen willst. Eine MRU-Struktur interessiert sich nur für 'Vorne' und 'Hinten'. Eine Liste hingegen willst Du auch mal durchsuchen: Dann gibt es weitaus bessere Strukturen als die verkettete Liste. Für Dich als Performancefreak wäre die Skip List genau das Richtige: Sie ist auch verkettet, aber nicht nur mit dem nächsten Element, sondern auch mit den übernächsten, überübernächsten etc. Eine erstaunliche Struktur, die ein nahezu optimales Laufzeitverhalten (O(1) für alle Operationen) an den Tag legt. Ich hab hier irgendwo eine Implementierung gepostet (oder in der Codelibrary, oder im Delphi-Forum)...

Das Vergrößern kannst Du übrigens steuern, indem Du die Grow-Methode überschreibst. Sie ist aber schon ganz nett implementiert. Wirklich gute Ergebnisse erzielt man, wenn man die Listengröße einfach verdoppelt. Das passiert ja nicht so oft: Bis 2^32 Elemente drin sind, ganze 31 Mal...

Und wirklich Zeit fressen eh die Suchoperationen...