Generic List, große Liste, große Datenstruktur, Geschwindigkeit

[Dejan Vu]

Das ursprüngliche Problem ist ja, das in jedem Schleifendurchgang das kopierte Element aus der Liste entfernt wird. Damit wird die Operation vom Aufwand O(n*m) (n=Listenlänge, m=Anzahl der zu extrahierenden Elemente). Eine einfache Alternative ginge mit O(n) so:

1. Alle zu exrahierenden Elemente in eine zweite Liste kopieren und sich die Position in der Originalliste merken.
2. In einer zweiten Schleife die Elemente in der Originalliste umschichten, sodass kopierten Elemente verschwinden

Das Ganze wäre in O(n) zu machen.

Delphi-Quellcode:

for i:=0 to originalList.Count-1 do
  if OriginalList[i].First then begin
    ResultList.Add(OriginalList[i]);
    CopiedIndexes.Add(i);
  end;

j:=0;
for i:=0 to OriginalList.Count-1 do
  if i= CopiedIndexes[j] then 
    inc(j)
  else
    OriginalList[i-j] = OriginalList[i];

OriginalList.Count := OriginalList.Count - CopiedIndexes.Count;

(ungetestet)

Bzw. In einem Durchlauf:

Delphi-Quellcode:

extracted := 0;
i := 0;
while i< originalList.Count-1 do
  if OriginalList[i].First then begin
    ResultList.Add(OriginalList[i]);
    inc(j);
  end else
    OriginalList[i-extracted] := OriginalList[i];

OriginalList.Count := OriginalList.Count - extracted;

(Auch ungetestet)