Zeile aus Stringlist löschen, wie optimieren?

[jaenicke]

Zitat von Neutral General:

Wie siehts mit StringReplace aus? Schonmal probiert wie das abschneidet?

StringReplace(Stringlist.Text,#13#10,'',[rfReplaceAll])

Sehr schlecht, denn dabei werden erst alle Strings aus der Liste zu einem einzelnen verkettet (sprich mindestens doppelter Speicherverbrauch, vom Zusatzaufwand ganz abgesehen) und dann darin die Zeilenumbrüche gesucht, die vorher schon so schön bekannt waren, und dann ein weiterer String mit dem Ergebnis angelegt (sprich noch einmal Speicher verballert).

Insgesamt verstehe ich das ganze so:
Eine Datei wird geladen, nach mehreren Kriterien sollen dann Zeilen gelöscht werden und am Ende soll das Ergebnis wieder gespeichert werden. Richtig?
Wenn ja, befürworte ich immer noch die Variante, die ich schon früher genannt hatte:
Einfach alles unverändert lassen und nur die zu löschenden Zeilen beim Speichern auslassen. Dafür kann man sich einfach ein Array of Boolean anlegen und darin markieren welche Zeilen gelöscht sind. Solange die Kriterien zur Löschung nicht indexabhängig sind und die Anzahl der Zeilen prozentual nicht sehr hoch ist, sollte das die schnellste Variante sein.

[Harry Stahl]

Wie wäre es mit einer Lösung, die Dein Problem von 2 Minuten
auf 599 Millisekunden reduziert?

Auf meinem (wohl etwas schwachen Rechner) hat Deine ursprüngliche Variante sogar 200527 MS benötigt (statt die von Dir angegebenen 120000 MS).

Manchmal kommt man nur über Umwege zum Ziel:

Delphi-Quellcode:

  //for i := (sl.Count - 1) downto 0 do
    //if sl[i] = '' then sl.Delete(i);

   slTmp := TSTringList.Create;

   for i := 0 to sl.Count - 1 do
     if sl[i] <> '' then slTmp.Add (sl[i]);

   sl.Assign(slTmp);
   slTmp.Free;

Der Trick ist also, eine temporäre Stringliste zu nutzen und dieser Strings aus der eigentlichen Liste hinzuzufügen, wenn diese nicht leer sind.

Anschließend weist Du der alten Liste die neue Liste zu und das wars.
Gründe liegen in der Speicherverwaltung (Referenzen auf Strings und Anordnung im Speicher, usw).

[himitsu]

Zitat von Neutral General:

Wie siehts mit StringReplace aus? Schonmal probiert wie das abschneidet?

StringReplace(Stringlist.Text,#13#10,'',[rfReplaceAll])

sLineBreak, sonst macht das Ding nur noch in Windows seine Arbeit. (Linux, Mac, Android ....)

Und es sollten ja nicht die Zeilenumbrüche raus, sondern nur Leerzeilen, also #13#10#13#10 (sLineBreak + sLineBreak),
aber wie "gut" das funktioniert hatte ich schon beschrieben.

In der Liste umkopieren oder in andere Liste umkopieren braucht kaum mehr Speicher.
Jedenfalls nicht für die Strings. (nur bissl für Objektinstanz und dann bissl mehr, für die Zeigerliste auf die Strings)

Vor dem Umkopieren der Liste kann man aber auch noch die Länge der Liste vorreservieren. TStringList.Capacity

Und in der Liste umkopieren .. TStringList.Exchange?

Zitat:

sl.Assign(slTmp);

Das kopiert aber auch nochmal die Liste. (notfalls könnte man aber auch einfach die beiden Objekte austauschen)

[Harry Stahl]

Zitat:

sl.Assign(slTmp); Das kopiert aber auch nochmal die Liste. (notfalls könnte man aber auch einfach die beiden Objekte austauschen)

OK, diese Vorschläge aufgegriffen, bringt der Einbau in die von mir vorgeschlagene Variante es dann auf 299 Millisekungen:
Sollte jetzt reichen, oder?

Delphi-Quellcode:

var
  slDummy: TSTringList;
begin

  slTmp := TSTringlist.Create;
  slTmp.Capacity := sl.Count;

  for i := 0 to sl.Count - 1 do
   if sl[i] <> '' then slTmp.Add (sl[i]);

  slDummy := sl;
  sl := slTmp;

  slDummy.Free;

[Furtbichler]

Also das ist kürzer und schneller (20% bei mir):

Delphi-Quellcode:

var
   i,j : Integer;

begin
   j:=0;
   for i := 0 to sl.Count - 1 do
    if sl[i] <> '' then begin
      sl[j] := sl[i];
      inc(j);
    end
End;

[Harry Stahl]

Deine (Furtbichler) Lösung braucht bei mir 275 MS, allerdings erfüllt Dein Vorschlag leider die Aufgabe nicht, es bleiben 1 Mio Einträge in der Liste.

Nachtrag: Gerade habe ich gesehen, dass Du in Deinem Beitrag etwas früher hier noch eine weitere Zeile am Ende hattest:

SetLength(sl,j);

Da streikt der Compiler mit dem Hinweis "Inkompatible Typen".

Hey, vielleicht sollten wir einen Preis verleihen an den, der unter 100 MS kommt?

[Popov]

@himitsu

Ach verflixt, die Idee mit Exchange hatte ich gleich am Anfang, nur was habe ich gemacht? Ich vertue mich und nehme stattdessen Move. Und das hat natürlich zwei Minuten gedauert, also habe ich es nicht weiter verfolgt. Mit Exchange dauert das nur 80 ms und der Speicher wird nicht vergrößert, es wird nur neu sortiert. Und das Delete was folgt schneidet nur von hinten ab.

Delphi-Quellcode:

  ...
    //---
    t1 := Now;
    Cursor := crHourGlass;

    k := 0;
    for i := (sl.Count - 1) downto 0 do
      if sl[i] = '' then
      begin
        sl.Exchange(i, sl.Count - 1 - k);
        Inc(k);
      end;

    for i := (sl.Count - 1) downto sl.Count - k do
      sl.Delete(i);


    Cursor := crDefault;
    t2 := Now;
    t := MilliSecondsBetween(t1, t2);
    ShowMessage(Format('Count sl: %d | Dauer des Verschiebevorgangs: %d ms', [sl.Count, t]));
  ...

@Harry Stahl

Das mit dem Kopieren habe ich schon im Beitrag #11 behandelt und es dauerte nur 150 ms. Ich denke diese Werte sind von dem Computer abhängig, da es im Grunde genommen in Grün ist.

[Harry Stahl]

Bei mir hier dauert Deine Lösung 119 MS.

Dennoch würde ich mal sagen, Du hast den Preis gewonnen.

Cooler Thread.

Ich finde es jedenfalls echt faszinierend, wie man immer noch ein wenig mehr Leistung durch Optimierung aus den Routinen raus holen kann.

[p80286]

Kaum ist man ein WE nicht da überschlägt sich alles.

Code:

sl.Exchange(i, sl.Count - 1 - k);

Hierbei verschwinden die zu löschenden Zeilen werden aber durch Zeilen vom Listenende ersetzt.
Oder hab ich da etwas falsch verstanden?

ich hab es jetzt erst einmal mit

Delphi-Quellcode:

for i:=0 to Liste.Count-1 do
  if Liste[i]<>'' then        // oder anderer Inhalt
    TempListe.add:=Liste[i];

Das ist hinreichend schnell, und der Hauptspeicher hat bisher auch gereicht!

Vielen Dank!

K-H

[Popov]

@p80286

Stimmt, das mit dem Ersetzen könnte sein. Aber ich denke mir das ist nur eine Frage des Algorithmus. Man muss es nur etwas raffinierter damit es passt.