Autor Beitrag
Quake User
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 159



BeitragVerfasst: So 27.08.06 17:02 
das löschen der Pointer in einer TList ist sehr langsam

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
  for i:= 0 to List.Count-1 do
  begin
    //if Löschbedingung
    begin
      List.Delete(i);

    end;
  end;


Ich muss bspw. jeden 2. Eintrag oder jeden 10. Eintrag löschen
Kennt jemand eine schnellere Methode?
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 27.08.06 17:18 
hallo Quake User,

wo gibst du denn den dyn. speicher resp. die instanzen (der pointer) wieder frei?

ich denke, du wirst nicht daran vorbeikommen, das alles einzeln aufzuräumen.

nur so langsam dürft das nicht sein. hast mal ein wenig mehr code...
Quake User Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 159



BeitragVerfasst: So 27.08.06 17:26 
Die TList ist eine Tlist von Pointern auf Records.
Die TList hat 1.000.000 Einträge.

Ich lösche so:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
var
  i: integer;
  Obj: ^TRecord;
begin
  Gauge1.MaxValue:= List.Count-1//damit ich was sehe

  for i:= 0 to List.Count-1 do
  begin
    //if Löschbedingung then
    begin
      Obj:= List.Items[i];
      Dispose(Obj); // Speicher der Records freigeben
      List.Delete(i); //Pointer löschen

      Gauge1.Progress:= i;
      Application.ProcessMessages; //für Gauge1
    end;
  end;
end;
Marco D.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2750

Windows Vista
Delphi 7, Delphi 2005 PE, PHP 4 + 5 (Notepad++), Java (Eclipse), XML, XML Schema, ABAP, ABAP OO
BeitragVerfasst: So 27.08.06 17:34 
Dann lass doch mal das Applicaton.ProcessMessages und das mit der Gauge weg.

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 27.08.06 17:34 
Das Problem ist, das TList eigentlich ein dynamisches Array ist. Wenn du bei 1 Million Einträgen das mittlere löschst, müssen 500.000 Elemente verschoben werden. Wenn du das mehrfach machst, weil mehrere Elemente entfernt werden sollen, dauert das halt etwas.

Leicht beschleunigen kann man das evtl. dadurch, dass man hinten anfängt zu löschen (also for i:= count-1 downto 0).
Desweiteren könnte man sich überlegen, ob es Sinn macht, jedesmal ein APM einzubauen - alle paarhundert oder -tausend Schritte sollten auch ausreichen.

Reicht der Geschwindigkeitszuwachs nicht aus, solltest du dir überlegen, deine Objekte in einer echten Liste zu verwalten.

_________________
We are, we were and will not be.
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 27.08.06 17:35 
Die Var Obj kannst du dir sparen

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
  
type 
 PRecord = ^tRecord; //neuer typ
var
  i: integer;
begin
  Gauge1.MaxValue:= List.Count-1//damit ich was sehe
  for i:= 0 to List.Count-1 do
  begin
    //if Löschbedingung then
    begin
      Dispose(pRecord(List.Items[i])); // Speicher der Records freigeben


bringt dir aber sicherlich nicht so viel, dass es eine vernünftige performance ergibt. das sequentielle durchlaufen von 1 Mio. einträgen braucht einfach seine zeit. ich würde mir hier überlegen einen geeigneten sekundärindex aufzubauen, damit du direkt auf die zu löschenden einträge zugreifen kannst. alternativ kannst du es dir überlegen, das löschen im hintergrund ggf. in einem eigenen thread ablaufen zu lassen. dann dauerts zwar noch länger, aber der nutzer merkt nichts mehr davon.
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 27.08.06 17:40 
@gausi: das verschieben hat er ja noch nicht mal drin "List.pack" vermute mal, dass er das viel später macht, sonst würd es richtig lang dauern. denke, der ganze zeitverzug kommt rein aus dem durchlauf der schleife... und hier müsst man mit applikationslogik ansetzen...
Keldorn
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 2266
Erhaltene Danke: 4

Vista
D6 Prof, D 2005 Pro, D2007 Pro, DelphiXE2 Pro
BeitragVerfasst: So 27.08.06 17:43 
user profile iconQuake User hat folgendes geschrieben:

Ich lösche so:

Das du hier keine AV siehst, wundert mich. das Ende der forschleife aktualisiert sich während des Duchlaufs nicht. Wenn deine Liste 1000 Einträge hat und du zwischendurch welche rauslöscht, läuft die Schleife trotzdem bis 1000 durch und dann gehen früher oder später die Aufrufe von Obj:= List.Items[i]; ins leere. Nimm while wenn du von vorn beginnen mußt oder laß die forschliefe rückwärts laufen, wie gausi es gesagt hat.

Mfg frank

_________________
Lükes Grundlage der Programmierung: Es wird nicht funktionieren.
(Murphy)
Quake User Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 159



BeitragVerfasst: So 27.08.06 17:46 
Das verschieben der Pointer in der Liste beim löschen währe mein nächstes Problem.

Ich muss jeden 2. Eintrag löschen. Mit

For i:= 0 to List.Count-1

durchlaufe ich die Liste und lösche jeden 2. Eintrag.
Durch die Verschiebung beim löschen funktioniert das natürlich nicht.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 27.08.06 17:48 
Unter anderem deswegen löscht man von hinten nach vorne. Wenn man hinten was löscht, ändert sich vorne an den Indizes nichts ;-)

Edit: btw: Wenn du wirklich jeden zweiten Eintrag löschen musst, mach es so:

Kreiere eine neue Liste, und kopiere in diese Liste jeden zweiten Eintrag rein und lösche die anderen (ohne den Zeiger aus der Liste rauszunehmen). Anschließend löschst du die alte Liste einfach komplett und benutzt die neu erstellte weiter.

Noch ein Edit: Pack kannte ich bisher noch nicht - damit gehts natürlich auch, wenn man vorher nicht dauernd delete aufruft ;-)

_________________
We are, we were and will not be.


Zuletzt bearbeitet von Gausi am So 27.08.06 17:53, insgesamt 2-mal bearbeitet
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 27.08.06 17:50 
wenn du das verschieben der pointer am schluss legst, solltest du kein problem haben mit dem verschieben der pointer.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
  for i:= 0 to List.Count-1 do
  begin
    //if Löschbedingung
    begin
      List.Delete(i);

    end;
  end;
  list.pack; //erst ganz am schluss verschieben


Nachtrag: erst nach dem pack werden die indices verschoben. bis dahin ist es egal ob über while oder for schleife von hinten nach vorne oder von vorne nach hinten durchlaufen wird.
Marco D.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2750

Windows Vista
Delphi 7, Delphi 2005 PE, PHP 4 + 5 (Notepad++), Java (Eclipse), XML, XML Schema, ABAP, ABAP OO
BeitragVerfasst: So 27.08.06 18:04 
Wenn TList ein dynamisches Array ist, ist es doch keine verkettete Liste, oder doch?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 27.08.06 18:15 
user profile iconMarco D. hat folgendes geschrieben:
Wenn TList ein dynamisches Array ist, ist es doch keine verkettete Liste, oder doch?

Richtig. Man kann aber - wie ich gerade gelernt habe, einzelne Listeneinträge erstmal nur auf NIL setzen (und natürlich die Objekte dahinter erstmal freigeben), und dann mit Pack einmal aufräumen. Dann hat man nur einen Verschiebungs-Durchlauf, anstatt "count-halbe"-viele.

Ein List.Delete ist da aber kontraproduktiv, weil ein delete eben doch neu indiziert (mehr dazu in der OH).

_________________
We are, we were and will not be.
Marco D.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2750

Windows Vista
Delphi 7, Delphi 2005 PE, PHP 4 + 5 (Notepad++), Java (Eclipse), XML, XML Schema, ABAP, ABAP OO
BeitragVerfasst: So 27.08.06 18:21 
Warum baut TList denn nicht auf einer verketteten Liste auf. In einem anderen Topic hat man mir gesagt (auch user profile iconGausi]), dass diese schneller arbeiten als ein dynamisches Array.

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot
Quake User Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 159



BeitragVerfasst: So 27.08.06 18:24 
Das Verschieben in der Liste beim Löschen scheint das Problem zu sein. Das Löschen arbeitet im ersten Drittel sehr schnell und verlangsamt sich dann.

(Ich lösche jetzt von Hinten. Das ist schneller)

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
var
  i: integer;
  Obj: ^TRecord;
begin
  Gauge1.MaxValue:= List.Count-1;
  for i:= List.Count-1 downto 0 do
  begin
    if Odd(i) then
    begin
      Obj:= List.Items[i];
      Dispose(Obj);
      List.Delete(i);

      Gauge1.Progress:= i;
      Application.ProcessMessages;
    end;
  end;
  Label2.Caption:= IntToStr(List.Count);
end;


bei 1.000.000 Records dauert das ca. 3 min.
Ein Record besteht aus 6 Real Zahlen.
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: So 27.08.06 18:27 
@Marco: Weil eine Listenstruktur andere Nachteile hat. Z.B. kann man sie nicht so schön mit den üblichen Verfahren sortieren, weil mein keinen direkten Zugriff auf beliebige Elemente hat. Etwas wie Binärsuche klappt da auch nicht.

Ganz grob kann man sagen: In eine Liste kann man super einfügen und löschen, braucht aber länger, bis man es wieder gefunden hat (ich gehe jetzt von Standard-Listen aus, es gibt auch welche, die mehr Zeiger speichern, und somit den linearen(?) Geschwindigkeitsvorteil mit log(N) Speicher erkaufen).
In einem Array kann man super suchen, aber einfügen und löschen dauert länger.

@Quake User: Was hier zum Thema delete, Nil und pack gesagt wurde, hast du gelesen?

_________________
We are, we were and will not be.
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 27.08.06 18:39 
hallo Quake User,

anbei ein kleines beispiel, zum löschen von jedem zweiten element aus einer tList. hier verschiebt sich nix. es liegt also nicht am löschen deiner items aus der tList. ich würde mir daher überlegen, die zugriffe zu optimieren und ggf. alternativen überlegen (z. b. im hintergrund).


ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  pString = ^String//zeiger auf string
  TForm1 = class(TForm)
    Memo1: TMemo; //memo zur anzeige
    Button1: TButton; //ziffern 1 bis 10 setzen
    Button2: TButton; //jede zweite ziffer löschen
    procedure Button1Click(Sender: TObject); //ziffern 1 bis 10 setzen
    procedure FormCreate(Sender: TObject);
    procedure Button2Click(Sender: TObject); //jede zweite ziffer löschen
    procedure FormDestroy(Sender: TObject);
  private
    { Private-Deklarationen }
    tl: tList;
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);  //liste mit 1 bis 10 füllen
var 
 ps: pString; //zeiger auf string
 i : integer; //laufvariable
begin
 memo1.Clear;                      //memo aufräumen
 for i := 0 to tl.count -1 do      //liste druchgehn
 begin
  dispose(pString(tl.items[i]));   //alle items löschen
  tl.items[i] := NIL;              //markieren
 end;
 tl.pack;                          //und entfernen
 for i := 0 to 10 do               //1 bis 10 gehen
 begin
  new(ps);                         //neuen zeiger auf string
  ps^ := inttostr(i);              //ziffer zuweisen
  tl.add(ps);                      //an liste hinzufügen
 end;
 for i := 0 to tlist.count -1 do   //liste durchgehen
  memo1.Lines.Add(pString(tl.items[i])^); //in memo aufnehmen zur anzeige
end;

procedure TForm1.Button2Click(Sender: TObject);   //jeden zweiten satz löschen
var
 i: integer;
begin
 for i := 0 to tl.count - 1 do //die liste durchgehen
 begin
  if (i mod 2) = 0 then //wenn gerade
  begin
   dispose(pString(tl.items[i])); //lösche eintrag
   tl.items[i] := NIL;            //markiere diesen
  end;
 end;
 tl.pack;                       //entferne gelöschte einträge
 memo1.clear;                   //memo säubern
 for i := 0 to tl.count - 1 do  //items in memo anzeigen
  memo1.Lines.add(pString(tl.items[i])^);
end;

procedure TForm1.FormDestroy(Sender: TObject);
var
 i: integer;
begin
 for i := 0 to tl.Count -1 do    //speicher für alle items freigeben
  dispose(pString(tl.Items[i])); 
 tl.free;                        //liste freigeben
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
 tl := tList.Create; //Liste erstellen
end;

end.


Nachtrag: muss mich berichtigen, tList.Delete verschiebt die items. wusste ich noch nicht, da ich dies immer wie oben mache.
Quake User Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 159



BeitragVerfasst: So 27.08.06 19:04 
Ich habe die delete mit der Pack Variante verglichen.

Die Delete Variante dauert jetzt 2 min 40 sek.

Bei der pack Variante verschiebt sich der Zeitaufwand nur.
Das Löschen mit List.Items[i] := NIL ist natürlich sehr schnell
dafür dauert das List.Pack dann aber 2 min 35 sek.

Pack ist also (erstaunlicher weise) nicht schneller.
Zudem kann ich bei Pack den Fortschritt nicht darstellen.

Ohne
ausblenden Delphi-Quelltext
1:
2:
      Gauge1.Progress:= i;
      Application.ProcessMessages;


spare ich auch nur wenige Sekunden.


Zuletzt bearbeitet von Quake User am So 27.08.06 19:11, insgesamt 1-mal bearbeitet
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 27.08.06 19:09 
hallo Quake,

wie gesagt, schau dir doch mal 'n thread an. ob du es im hintergrund abarbeiten kannst. dann interessierts den user nicht mehr.

Alternativ kannst du es dir überlegen, in der zwischenzeit auf pack zu verzichten, musst halt bei jeden item überprüfen ob es <> NIL ist.

ggf. kannst du hier noch deine liste sortieren, alle NIL einträge ans ende der liste und dann erst die lücke freigeben, anstatt von vielen lücken.
Quake User Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 159



BeitragVerfasst: So 27.08.06 19:45 
Da die Einträge der Liste vom Nutzer verwendet werden
kann ich das Löschen nicht im Hintergrund erledigen.

Auf NIL zu prüfen scheint das Mittel der Wahl zu sein.
(genaugenommen ist das genial)
Ich überlege nun noch wann ich das TList.Pack erledige.
ggf. lässt sich das parallel in einem weiteren Thread
erledigen.