Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Nil-Einträge in TList entfernen sehr langsam


sahib - Mi 11.05.05 10:45
Titel: Nil-Einträge in TList entfernen sehr langsam
Moin.

Ich habe eine TList, mit der ich etwa 120.000 Records verwalte. Nun müssen davon einige gelöscht werden. Ich habe das zuerst im MachWasTeil gemacht:

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
 
for i := Pred(MainList.Count) downto 0 do begin
  [...]
  if MussDochNicht then
    MainList.Delete(i)
end;
MainList.Capacity := MainList.Count; // *edit* hinzugefügt


Ich dachte mir, das sei vielleicht etwas langsam und baute obiges Beispiel dann um:

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
 
for i := Pred(MainList.Count) downto 0 do begin
  [...]
  if MussDochNicht then
    MainList[i] := nil
end;

  [...]
  // (1)
  MainList.Pack;
  MainList.Capacity := MainList.Count;

  // (2)
  for i := Pred(MainList.Count) downto 0 do
    if MainList[i] = nil then MainList.Delete(i);
  MainList.Capacity := MainList.Count;


Methoden (1) und (2) sind in etwa gleichschnell bzw. langsam. Gibt es noch eine andere Möglichkeit, an die ich nicht gedacht habe? Es ist schon erstaunlich, dass die TList schneller gefüllt / bearbeitet wird, als Einträge gelöscht werden können.

Christian


Moderiert von user profile iconTino: Topic aus Sonstiges verschoben am Mi 11.05.2005 um 10:53


Asgar - Mi 11.05.05 10:49
wenn du alles löschen willst geht das glaub ich auch mit mainlist.clear


sahib - Mi 11.05.05 10:56
Nein, Asgar, es geht um gezieltes löschen einzelner Einträge.

Christian


BenBE - Mi 11.05.05 11:04
Um wieviele Einträge handelt es sich?

Update-Benachrichtigungen (BeginUpdate\EndUpdate) abgeschaltet?


sahib - Mi 11.05.05 11:18
Hallo Benny.

Ich habe über 100.000 Einträge, von denen rund 30.000 später gelöscht werden. Begin-/EndUpdate brauche ich nicht, da die Daten erst später angezeigt werden.

Christian


sahib - Mi 11.05.05 11:35
Ok, ich habe das löschen auf sieben Prozent der Zeit herunter. Dazu habe ich ein Dummy-Byte im Record benutzt, anhand dessen ich die Liste sortiere. Dann suche ich einfach am Ende zum Löschen die Position des bestimmten Werter heraus und setze die Kapazität der TList auf eben diesen Wert. Vorher 20 Sekunden, nun knapp über eine Sekunde!

Christian


sniper_w - Di 20.09.05 22:50
Wenn es sich um so viele Einträge handelt, dann lieber ein Binärbaum nehmen.


alzaimar - Mi 21.09.05 08:45
user profile iconsniper_w hat folgendes geschrieben:
Wenn es sich um so viele Einträge handelt, dann lieber ein Binärbaum nehmen.

Nein! Veraltet! Nimm eine Skiplist oder ein Dictionary (Hashlist) Beides gibts hier
http://www.delphipraxis.net/topic53649_skiplist.html und
http://www.delphipraxis.net/topic53653_hashtabellen.html

Ein Binärbaum sollte ausgeglichen (AVL-Baum, Red-Black etc.) sein. Das ist aufwändig. Die Suchzeit ist O(log n), der Aufwand zum einfügen und Löschen u.U. O(n) (er soll ja ausgeglichen sein).
Eine Skiplist ist da schon wesentlich effektiver, eine Hashlist (Dictionary) optimal (Aufwand = O(1)).

Ich würde auch zu einer DB à la Access oder Paradox raten.


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!