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)

[Sir Rufo]

Das macht das zwar schneller aber nicht so schnell wie es gehen könnte, denn hier wird eben immer noch Unmengen an Speicher angefordert und wieder freigegeben.

Ungeachtet der Geschwindigkeit habe ich während des Kopiervorgangs auch noch alle zu kopierende Elemente doppelt im Speicher liegen. Ist in diesem Testszenario noch nicht kritisch, aber wir kennen nicht das Speicherprofil der gesamten Anwendung.

Die beste Option hinsichtlich Geschwindigkeit und Speicherbedarf ist und bleibt die Verwendung einer Transport-Klasse für den Record. Diese kann man auch generisch (wenn man hat) sowie als Interface designen und dieses wieder in einen Record packen.

[Dejan Vu]

Wo werden Unmengen an Speicher angefordert? Die Liste wächst, weil die Kapazität initial nicht gesetzt wird (23 mal in dem Beispiel). Das macht den Kohl aber nu auch nicht fett (einfach mal testen).
Aber falls Du mit 'Unmengen' die 23 meinst, dann hilft sowas:

Delphi-Quellcode:

ResultList.Capacity := OriginalList.Count;
//
// die Schleife
//
OriginalList.Count := OriginalList.Count - extracted;
ResultList.Capacity := extracted;

So ist das jedenfalls auch nicht mehr messbar (O(n) vs. O(n*m) bringt schon viel).

[Sir Rufo]

10.000 Elemente in der Startliste
+5.000 Elemente in der Zielliste
5.000 Elemente kopieren
-5.000 Elemente in der Startliste

Zwischenzeitlich brauche ich 5.000x SizeOf( TMyData ) mehr und am Ende werden 5.000x SizeOf( TMyData ) wieder freigegeben. Und es werden 5.000x SizeOf( TMyData ) kopiert.

Und das dein Vorschlag durchaus eine Verbesserung der Geschwindigkeit bringt habe ich schon geschrieben, trotz allem bleibt der erhöhte Speicherbedarf und die Kopiererei.