Array basierte Listen sind grundsätzlich besser als verkettete Listen, grund dafür is Cache lokalität. In Java sind selbst linked lists nicht listen bei denen jedes element gelinked wird, sondern sind so implementiert das man mehrere elemente zu einem array zusammenfasst und den dann linked.
TList im vergleich zu dynamischen Arrays hat einen entscheidenden vorteil, undzwar implementiert TList geometrisches wachstum, undzwar richtig.
Erstmal, geometrisches wachstum heist, eine Liste startet mit einer gewissen Kapazität, und immer wenn Count = Kapazität ist und was geadded wird, wird die Kapazität verdoppelt. Das heißt, für N insertions muss nur log(N) oft geresized werden. Für 1000 insertions sind also nur 10 resizes nötig. Bei einem Dynamischen Array würde das naiv implementiert 1000 resizes benötigen (für jeden insert einen).
Der Grund warum man das haben will ist, das das resizen eine der mit abstand teuersten operationen ist die man mit einem Array machen kann. Je nach Memory Manager und Fragmentation kann man massive performance einbußen haben.
Beispiel:
Code: Alles auswählen
program Project1;
{$mode objfpc}{$H+}
uses
classes, SysUtils;
var
arr: array of Pointer;
l: TList;
start: QWord;
i: Integer;
const
numElements = 10000000;
begin
Randomize;
l := TList.Create;
arr := nil;
start := GetTickCount64;
for i:=0 to numElements do
l.Add(Pointer(Random(Integer.MaxValue)));
WriteLn('List: ', GetTickCount64 - start);
start := GetTickCount64;
for i:=0 to numElements do
Insert(Pointer(Random(Integer.MaxValue)), arr, Length(arr));
WriteLn('Array: ', GetTickCount64 - start);
ReadLn
end.
Bei numElements = 10 Mio braucht TList c.a. 140 ms und Array c.a. 2,1 sekunden. Bei 1 mio ist es 15 zu 63 ms.
Vor allem wenn man regelmäßig elemente Löscht und wieder einfügt wird wenn die Liste einmal warm gelaufen ist keine einzige resize operation mehr benötigt.
Am anfang habe ich gesagt das TList dieses geometrische Wachstum vor allem richtig implementiert, was ich damit meine ist, im grunde kann man sowas auch auf Array basis implementieren, man benötigt nur eine separate Count variable. Das problem ist aber das Arrays management code ausführen, was im grunde heißt das bei einem Resize einmal auf allen neuen feldern des arrays Initialize aufgerufen wird, und auf allen feldern am ende auch einmal Finalize aufgerufen wird. Ist toll für Dynamische Arrays, für geometrisches Wachstum spuckt dir das aber ganz gewalltig in die Suppe, da es dafür sorgt das Memory bereiche die eventuell sonst nie angefasst werden einmal überschrieben werden. TList im gegensatz dazu benutzt rohe GetMem, ReallocMem und FreeMem calls um den speicher zu verwalten.
Das widerum macht dir den tollen vorteil von Virtuellem addressraum kaputt, mit dem du beliebig großen speicher alloziieren kannst, ohne das der je geladen werden muss. Beispiel:
Code: Alles auswählen
program Project1;
{$mode objfpc}{$H+}
uses
classes, SysUtils;
var
arr: Array of Byte;
p: PByte;
const
Size = 1024*1024*1024; // 1 GB
begin
SetLength(arr, Size);
WriteLn('Array allocated');
ReadLn;
arr := nil;
p := GetMem(Size);
WriteLn('Array freed, Pointer allocated');
ReadLn;
end.
Wenn ich jetzt in meinen Taskmanager schaue, wenn Array allocated geprinted wird, habe ich 1 GB ram verbrauch bei diesem program. Drücke ich enter und warte bis Array freed, Pointer allocated da steht, ist der ram verbrauch nur noch 7MB, obwohl auch 1 GB alloziiert wurde.
Der Grund dafür ist der virtuelle addressraum den das Betriebsystem zur verfügung stellt. So kann man beliebig große speicherblöcke alloziieren (bis 2^48 byte oder so), während allerdings immer nur die menge an speicher physisch belegt wird die auch tatsächlich angefasst wird. Eine TList belegt damit zwar theoretisch im worst case doppelt so viel virtuellen speicher wie ein Array, aber physisch ist maximal eine pagesize (4kb oder so) zu viel im Speicher, da das betriebsystem die anderen pages nie geladen hat.
Es gibt also praktisch nur ein szenario in dem ein Array besser ist als eine TList, und das ist wenn die benötigte größe von anfang an exakt bekannt ist, und im vorhinein alloziiert werden kann. In allen anderen fällen ist TList, TStringList, TFPGList (fgl unit) oder TVector (gvector unit) besser.