Autor |
Beitrag |
Quake User
      
Beiträge: 159
|
Verfasst: So 27.08.06 17:02
das löschen der Pointer in einer TList ist sehr langsam
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| for i:= 0 to List.Count-1 do begin 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
|
Verfasst: 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 
      
Beiträge: 159
|
Verfasst: 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:
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:= 0 to List.Count-1 do begin begin Obj:= List.Items[i]; Dispose(Obj); List.Delete(i); Gauge1.Progress:= i; Application.ProcessMessages; end; end; end; |
|
|
Marco D.
      
Beiträge: 2750
Windows Vista
Delphi 7, Delphi 2005 PE, PHP 4 + 5 (Notepad++), Java (Eclipse), XML, XML Schema, ABAP, ABAP OO
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
|
Verfasst: So 27.08.06 17:35
Die Var Obj kannst du dir sparen
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| type PRecord = ^tRecord; var i: integer; begin Gauge1.MaxValue:= List.Count-1; for i:= 0 to List.Count-1 do begin begin Dispose(pRecord(List.Items[i])); |
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
|
Verfasst: 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
      
Beiträge: 2266
Erhaltene Danke: 4
Vista
D6 Prof, D 2005 Pro, D2007 Pro, DelphiXE2 Pro
|
Verfasst: So 27.08.06 17:43
Quake 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 
      
Beiträge: 159
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
|
Verfasst: 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.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| for i:= 0 to List.Count-1 do begin begin List.Delete(i);
end; end; list.pack; |
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.
      
Beiträge: 2750
Windows Vista
Delphi 7, Delphi 2005 PE, PHP 4 + 5 (Notepad++), Java (Eclipse), XML, XML Schema, ABAP, ABAP OO
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: So 27.08.06 18:15
Marco 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.
      
Beiträge: 2750
Windows Vista
Delphi 7, Delphi 2005 PE, PHP 4 + 5 (Notepad++), Java (Eclipse), XML, XML Schema, ABAP, ABAP OO
|
Verfasst: 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 Gausi]), 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 
      
Beiträge: 159
|
Verfasst: 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)
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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
|
Verfasst: 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).
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; TForm1 = class(TForm) Memo1: TMemo; Button1: TButton; Button2: TButton; procedure Button1Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure Button2Click(Sender: TObject); procedure FormDestroy(Sender: TObject); private tl: tList; public end;
var Form1: TForm1;
implementation
{$R *.DFM}
procedure TForm1.Button1Click(Sender: TObject); var ps: pString; i : integer; begin memo1.Clear; for i := 0 to tl.count -1 do begin dispose(pString(tl.items[i])); tl.items[i] := NIL; end; tl.pack; for i := 0 to 10 do begin new(ps); ps^ := inttostr(i); tl.add(ps); end; for i := 0 to tlist.count -1 do memo1.Lines.Add(pString(tl.items[i])^); end;
procedure TForm1.Button2Click(Sender: TObject); var i: integer; begin for i := 0 to tl.count - 1 do begin if (i mod 2) = 0 then begin dispose(pString(tl.items[i])); tl.items[i] := NIL; end; end; tl.pack; memo1.clear; for i := 0 to tl.count - 1 do 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 dispose(pString(tl.Items[i])); tl.free; end;
procedure TForm1.FormCreate(Sender: TObject); begin tl := tList.Create; end;
end. |
Nachtrag: muss mich berichtigen, tList.Delete verschiebt die items. wusste ich noch nicht, da ich dies immer wie oben mache.
|
|
Quake User 
      
Beiträge: 159
|
Verfasst: 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
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
|
Verfasst: 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 
      
Beiträge: 159
|
Verfasst: 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.
|
|