Zeile aus Stringlist löschen, wie optimieren?

[p80286]

Hallo zusammen,

ich muß des öfteren aus recht größen Textdateien bestimmte Zeilen löschen. Dies mache ich z.Zt. so

{leerzeilen löschen}

Delphi-Quellcode:

Stringliste.loadfromfile('Testdatei');
..
for i:=Stringliste.count-1 downto 0 do
  if length(Stringliste[i])=0 then Stringliste.delete(i);

Hat man mehr als 1 Mio Zeilen, kann das schon dauern. Darum meine Frage, wie kann ich das optimieren?

Ein etwas besseres Laufzeitverhalten habe ich mit

Delphi-Quellcode:

for i:=Stringliste.count-1 downto 0 do begin
  if length(Stringliste[i])>0 then stringlist2.insert(0,stringlist[i]);
  Stringlist.delete(i);
end;

(das Verhältnis ist etwa 6:5)


Als untauglich hat sich erwiesen:

Delphi-Quellcode:

p:=pos(#13#10#13#10,string);
while p>0 do begin
  delete(string,p,2);
  p:=posex(#13#10#13#10,string,p-1);
end

Da beim TStringlist.Delete letztlich nur 3 Pointer verschoben werden erhoffe ich mir von einer Pointerliste auch keine große Verbesserung.

Habt Ihr noch eine Idee wie ich da etwas Tempo machen kann?

Gruß
K-H

[Uwe Raabe]

Deine for-Schleifen haben weder eine Richtung noch eine Ende-Bedingung und compilieren somit nicht. Beim Löschen von Einträgen ist aber die Laufrichtung der Schleife schon relevant.

Berücksichtigst du bei deinen Zeitmessungen auch das Laden und Speichern oder nur die Schleife?

[p80286]

Zitat:

Zitat von Uwe Raabe (Beitrag 1247854)

Berücksichtigst du bei deinen Zeitmessungen auch das Laden und Speichern oder nur die Schleife?

Es geht nur um die Schleife!
(die paar Sekunden für das Laden kann man ignorieren)
Beim letzten Lauf ging es um 20 Mio. Zeilen und ca 1,8 Gbyte.

Gruß
K-H

[Der schöne Günther]

Ich hätte gesagt, das liegt in der Natur von

Delphi-Quellcode:

TStringList

, oder? Ohne es genau zu wissen hätte ich doch gesagt, das es intern auf ein dynamisch wachsendes/schrumpfendes Array abgebildet wird. Löscht du mittendrin eins raus, rückt alles auf.

Nehme ich eine TStringList bzw eine TList<String> aus der RTL, brauche ich ca 22 Sekunden um auf 5 Mio. Strings ca 2. Mio zufällige herauszulöschen. Nehme ich als Container, nur als Beispiel, ein

Delphi-Quellcode:

Spring.Collections.ISet<String>

, sind es 1500ms.

Deshalb würde ich bei solchen Datenmengen nach einem anderen Container suchen - Falls meine Annahme den zutrifft, dass es intern ein großes Array ist. Wahrscheinlich wäre es ebenso schneller, wenigstens eine Kopie der TStringList zu bauen: Über alle Elemente drüberruschen und in die Kopie nur die aufnehmen, die nicht leer sind.

[user0815]

Delphi-Quellcode:

      i := 0;
      while i < Stringliste.Count do
      if trim(Stringliste[i]) = ''
       then Stringliste.Delete(i)
        else inc(i);

wobei ich keine Ahnung habe ob eine Prüfung auf trim oder length schneller ist...

[Der schöne Günther]

Aber der Flaschenhals ist doch

Delphi-Quellcode:

TStringList.Delete(..)

, oder?

[GPRSNerd]

Ich mache seit einiger Zeit Löschvorgänge/Überarbeitungen in großen Textdateien auch mit einer zweiten Stringliste, in die ich nicht zu löschende/überarbeitete Strings mit Stringliste2.Add() hinzufüge. Dabei hat sich eine Beschleunigung um den Faktor ~10 ergeben im Vergleich zum Löschen der Einträge mit Delete() in der Originalliste.
Die Dateien haben bei mir eine Größenordnung von 1-5 Mio. Zeilen (TTCN-Sourcecodes).

[jaenicke]

Wenn es nur darum geht ein paar Zeilen zu löschen und die Datei wieder wegzuschreiben, warum schreibst du nicht einfach die TStringList ohne die Zeilen wieder zeilenweise weg? Was anderes macht die doch intern logischerweise beim Speichern auch nicht.

Zudem wäre es denke ich sinnvoller per MMF zuzugreifen und die ganzen Inhalte gar nicht erst als Strings in den Speicher zu laden. Das zeilenweise Einlesen siehst du z.B. hier:
http://www.delphipraxis.net/151898-s...ei-reader.html

[sx2008]

Zur Info:

Delphi-Quellcode:

if length(Stringliste[i])=0 then   // ist langsamer als
if Stringliste[i] = '' then        // als der direkte Vergleich auf einen leeren String

Grund:
Der Aufruf der

Delphi-Quellcode:

Length()

-Funktion benötigt mehr CPU-Befehle als wenn nur der String (was ja nur ein Zeiger auf eine Datenstruktur ist) auf NIL überprüft wird.

[Mokus]

waru teilst du den Inhalt der Liste in verschiedene auf ?

so läuft du in deiner For schleife mehere Teile des Textes gleichzetig durch;

via Case länge ermitteln und daraufhin die anzahl der Listen anpassen.
fertiiiisch

[Popov]

Also löschen dauert wirklich lange, kopieren fast nichts. Ich hab ein Beispiel erstellt mit etwa 1 Mio Daten, davon 10% Leerzeilen. Erstellung etwa 150 ms, Löschung etwa 2 min, Kopiervorgang etwa 100 ms. Also statt löschen der Leerzeilen vielleicht besser kopieren der anderen Zeilen.

Hier das Beispiel mit dem ich gerechnet habe:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
const
  txt = 'qwertzuiopüasdfghjklöäyxcvbnm';
var
  sl, sl2: TStringList;
  i, t: Integer;
  t1, t2: TTime;
begin
  sl := TStringList.Create;
  sl2 := TStringList.Create;
  try
    //--- 1 Mio. Daten mit etw 10% Leerzeilen erstellen / Dauer etwa 150 ms

    t1 := Now;
    Cursor := crHourGlass;

    for i := 1 to 1000000 do
      if Random(10) = 1 then sl.Add('') else  sl.Add(txt);

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

    //--- 10% Daten (leerzeilen) entfernen / Dauer etwa 120000 ms

    { 
    t1 := Now;
    Cursor := crHourGlass;

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

    Cursor := crDefault;
    t2 := Now;
    t := MilliSecondsBetween(t1, t2);
    ShowMessage(Format('Count sl: %d | Dauert des Löschvorgangs: %d ms', [sl.Count, t]));
    }

    //--- 90% Daten (ohne leerzeilen) kopieren / Dauer etwa 300 ms 
    { }
    t1 := Now;
    Cursor := crHourGlass;

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

    sl.Assign(sl2);
    sl.Capacity := sl.Count; //Korrektur nach unten

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

  finally
    sl2.Free;
    sl.Free;
  end;

end;

//EDIT: sorry, habe beim optimieren in letzter for Schleife downto statt to geschrieben. Die Ergebnisse bleiben aber.

//EDIT2: Apropos Speicher, Capacity sollte am Ende wieder korrigiert werden.

[himitsu]

Zitat:

Zitat von p80286 (Beitrag 1247852)

{leerzeilen löschen}

Delphi-Quellcode:

Stringliste.loadfromfile('Testdatei');
..
for i:=Stringliste.count-1 downto 0 do
  if length(Stringliste[i])=0 then Stringliste.delete(i);

Hat man mehr als 1 Mio Zeilen, kann das schon dauern. Darum meine Frage, wie kann ich das optimieren?

Ein etwas besseres Laufzeitverhalten habe ich mit

Delphi-Quellcode:

for i:=Stringliste.count-1 downto 0 do begin
  if length(Stringliste[i])>0 then stringlist2.insert(0,stringlist[i]);
  Stringlist.delete(i);
end;

(das Verhältnis ist etwa 6:5)


Als untauglich hat sich erwiesen:

Delphi-Quellcode:

p:=pos(#13#10#13#10,string);
while p>0 do begin
  delete(string,p,2);
  p:=posex(#13#10#13#10,string,p-1);
end

Da beim TStringlist.Delete letztlich nur 3 Pointer verschoben werden erhoffe ich mir von einer Pointerliste auch keine große Verbesserung.

All zuviel kann man da eh nicht optimieren.

1. es wird ein Pointer aus der Liste entfernt UND die Pointer der nachfolgenden Strings werden verschoben
2. die Referenzen der zukopierenden Strings werden kopiert, und die Referenzzählung wird angesprochen (Stringinhalte werden nicht kopiert)
3. erst wird aus allen Strings/Zeilen EIN großer String gebastelt, dann wird via StringReplace "jeder" doppelte Zeilenumbruch einzeln entfernt (Achtung, bei 3 und mehr aufeinanderfolgenden Zeilenumbrüchen wird nur jeder Zweite entfernt), dabei werden alle nachfolgenden Zeichen jedesmal umkopiert, und dann wird der ganze String wieder in viele Einzelstrings zerlegt

Auslesen als TEXT geht nur bei einem Memo (TMemoStrings) schneller, da dort der Text zusammenhängend im RAM liegt. (aber das Löschen der Leerzeilen sollte auch da temporärn einer TStringList erfolgen, da das TMemo arschlangsam ist).




Wie kommen die Daten denn in die TStringList?
Was am Schnellsten ginge, wäre die Leerstrings garnicht erst aufzunehmen.
Also die Add-Methode überschreiben und bei dem ungewollten Leerstring abbrechen.

[p80286]

So chefe stört nicht mehr...
erst einmal vielen Dank für die vielen Rückmeldungen.

Zunächst, alle Zeilen müssen vorliegen und erst dann entscheidet sich welche Zeilen gelöscht werden. Sehr oft sind Leerzeilen betroffen und dafür hab ich dann eine Spezialbehandlung.
Die Lösung "nicht einlesen" entfällt daher.

Die Prüfung auf

Delphi-Quellcode:

Stringlist[i]=''

hab ich ausprobiert und gefühlt sind da ein paar Sekunden herum gekommen.

Die "Kopierlösung" ist auch auf andere Zeileninhalte anwendbar, zusammen mit dem "Auftrennen" scheint das interessant zu werden. Muß ich mal testen. Das wichtigste Problem was ich sehe ist hirbei der Speicherplatzbedarf.
Mal ausprobieren.

noch mal vielen Dank
K-H

P.S. z.Zt. arbeite ich mit ca 2,5 Mio Zeilen das fluppt so oder so

[Mokus]

Zitat:

Das wichtigste Problem was ich sehe ist hirbei der Speicherplatzbedarf.

WTF ?

wenn das dein Grö´tes Problem solltest du dir alg. Gedanken machen, ob man da nicht was anders Lösen könnte ...

[Furtbichler]

folgendes geht auch (ohne extra Liste)

Delphi-Quellcode:

Procedure RemoveEmptyLines (aList : TStringList);
Var
  i,j : Integer;

Begin
  j:=0;
  for i:=0 to aList.Length-1 do
    if aList[i]<>'' then begin
      aList[j] := aList[i];
      j := j + 1;
    end;
  
  SetLength(aList,j);
End;

(Ungetestet) Im Prinzip rennt man die Liste einmal durch und kopiert nur die nichtleeren Zeilen. Nach jedem Kopiervorgang erhöht man die Zielposition j um 1.

Braucht kaum/keinen extra Speicher :-)

[Blup]

Ah, da war jemand schneller, habs getestet, ist wirklich schnell.

Delphi-Quellcode:

    sl.BeginUpdate;
    try
      i2 := 0;
      for i := 0 to sl.Count - 1 do
      begin
        if sl[i] <> '' then
        begin
          sl[i2] := sl[i];
          Inc(i2);
        end;
      end;
      for i := sl.Count - 1 downto i2 do
        sl.Delete(i);
    finally
      sl.EndUpdate;
    end;

[OlafSt]

Und warum das ganze nicht Ultra-Oldschool ?

Delphi-Quellcode:

procedure bla;
var
  f: TEXTFILE;
  s: string;
  TSL: TStringList;
begin
  TSL:=TStringList.Create;
  AssignFile(f, 'BLA.TXT');
  Reset(f);
  while not eof(f) do
  begin
    ReadLn(f,s);
    if s <> '' then
      TSL.Add(s);
  end;
  CloseFile(f);
end;

Datei wird nur einmal komplett gelesen und der Speicherbedarf ist fürs Einlesen nahezu Null.

[Uwe Raabe]

Zitat:

Zitat von p80286 (Beitrag 1247882)

Das wichtigste Problem was ich sehe ist hirbei der Speicherplatzbedarf.

Das Problem ist kleiner als du vielleicht denkst. Wenn du den Inhalt einer Stringlist kopierts, werden nur die Pointer auf die Strings kopiert und nicht die Stringinhalte. Somit verbraucht die kopierte StringList kaum mehr als <Anzahl Zeilen>*<Sizeof(Pointer)> an zusätzlichem Speicher.

[p80286]

Zitat:

Zitat von Uwe Raabe (Beitrag 1247890)

Das Problem ist kleiner als du vielleicht denkst. Wenn du den Inhalt einer Stringlist kopierts, werden nur die Pointer auf die Strings kopiert und nicht die Stringinhalte. Somit verbraucht die kopierte StringList kaum mehr als <Anzahl Zeilen>*<Sizeof(Pointer)> an zusätzlichem Speicher.

Das ist ein Wort!
ich war mir nicht sicher ob nicht vielleicht doch die Inhalte kopiert werden!

Gruß
K-H

[Neutral General]

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

Delphi-Quellcode:

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

[jaenicke]

Zitat:

Zitat von Neutral General (Beitrag 1247897)

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

Delphi-Quellcode:

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:

Zitat von Neutral General (Beitrag 1247897)

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

Delphi-Quellcode:

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:

Delphi-Quellcode:

sl.Assign(slTmp);

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

[Harry Stahl]

Zitat:

Delphi-Quellcode:

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.:thumb:

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.