Lesen in eine StringList "teilbar"?

Für Fragen von Einsteigern und Programmieranfängern...
Antworten
alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Lesen in eine StringList "teilbar"?

Beitrag von alfware17 »

Hallo,

vielleicht mache ich es mir wieder zu einfach, aber kann ich die TStringList "retten" wenn sie mir bei zu großen Dateien auseinanderfällt
(bei array of strings kam Runtime Error 203 also Heap, bei Stringlist wahlweise 217 oder "out of memory").

Ich stelle es mir so vor, daß man in Portionen lesen, verarbeiten und dann wieder ausgeben kann. Einen guten Mischalgorithmus hätte ich dann.
Die StringList sollte mir signalisieren, bevor sie platzt und dann müßte man sich eben merken, bei welcher "Portion" man gerade war und welche Sätze des
Gesamtbestandes man gerade ist.

Dieses Signalisieren der StringList bevor sie platzt, bzw eine gute Abschätzung ob es passen könnte (zB aufgrund von Filesize und/oder der Zeilenanzahl in der Datei)
würde mir auch schon mal reichen.

Wenn ich weiß, es geht nicht alles rein, dann wähle ich eben von vornherein ein Teile-und-Herrsche-Verfahren mit Mischen, das habe ich schon.

Mir geht es nur um den Fall, wenn ich sicher gehen könnte, es paßt alles in eine StringList und ich könnte die dann mit der Standardfunktion sortieren. Ob es schneller
wird als meine eigene Routine für diesen Spezialfall ("alles in einer Liste"), werde ich dann ja sehen.

Zur Erklärung, was ich eigentlich vorhaben bzw teste:

Ich möchte Textdateien sortieren, die können auch sehr groß werden. Derzeit lese ich sie per READLN und schreibe per WRITELN,
das Sortieren im Speicher (ich benutze statt eines Arrays eine Liste), das TEILE-UND-HERRSCHE und das Mischen anschließend habe ich gelöst und die scheinen auch effizient, nur sind eben das READLN und WRITELN der Flaschenhals.

Ich experimentiere derzeit mit Array, auch dynamisches Array, jetzt StringList und zum Einlesen habe ich auch schon BlockRead und BlockWrite benutzt, mit mäßigem Erfolg. Wenn das LoadFromFile in die StringList schneller sein würde und ich eine abfangbare Meldung bekomme. bevor die StringList platzt. würde ich dem noch mal eine Chance geben. Allerdings hatte ich nach meiner Erinnerung damals schon festgestellt, daß die Sortierungen der Collections in Pascal ebenso wie in Python nicht so wahnsinnig schneller wären als mein eigenes Listenquicksort, von C-Dialekten ganz zu schweigen, die waren am langsamsten. Und wie gesagt, ich habe ein TEILE-UND-HERRSCHE Verfahren, wo ich die StringList nur dann einbauen würde, wenn sie neben einfacher und übersichtlicher (natürlich) aber auch schneller als mein eigenes wird, sonst lasse ich den Aufwand sein
Gruß Bernd

Code: Alles auswählen

program sortieren_batch;

{$mode delphi}

uses
  Windows, Messages, SysUtils, Classes;

const eingabe : string = 'test.txt';
      ausgabe : string = 'sort.txt';

var
  datei : TStringList;

function myCompare(liste: TStringList; i1, i2: longint):longint;
var
  r, i, l, l1, l2: longint;
  c1, c2: byte;
  s1, s2: String;
begin
  s1:= liste[i1]; s2:= liste[i2];
  l1:= Length(s1); l2:= Length(s2);
  i:= 1; r:= 0;
  l:= l1; if l > l2 then l:= l2;
  while (r = 0) and (i <= l) do begin
    c1:= ORD(s1[i]); c2:= ORD(s2[i]);
    if c1 < c2 then r:= -1 else
    if c1 > c2 then r:= 1;
    inc(i);
  end;
  if r = 0 then begin
    if l1 < l2 then r:= -1 else
    if l1 > l2 then r:= 1;
  end;
  Result:= r;
end;

begin
  if paramstr(1)<>'' then eingabe:=paramstr(1);
  if paramstr(2)<>'' then ausgabe:=paramstr(2);
  datei:=TStringList.Create;
  datei.LoadFromFile(eingabe);
  datei.Customsort(myCompare);
  datei.SaveToFile(ausgabe);
end.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 168
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Lesen in eine StringList "teilbar"?

Beitrag von Jorg3000 »

Wie groß ist die Textdatei denn?
Und an welcher Stelle passiert ein Speicherüberlauf? Bei LoadFromFile, bei Customsort oder bei SaveToFile?
Einer 32-Bit-Anwendung stehen, wenn ich mich recht erinnere, in der Praxis bis ungefähr 1,7 GB Speicher zur Verfügung, einer 64-Bit-Anwendung theretisch der ganze freie Hauptspeicher.

alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Re: Lesen in eine StringList "teilbar"?

Beitrag von alfware17 »

Die LoadFromFile bricht ab.

Bereits bei einer 680 MB Datei (32bit-EXE, die 64bit-EXE schafft das noch, brach dann aber beim Doppelten ca. 1,3 GB Datei ab).
Meine Idee war so bei/bis 1 GB die Stringlist zu nutzen wäre schön


Wenn ich es "normal" lese, schafft die 32bit-EXE noch die 680 MB, mit größeren muß ich noch mal testen... Also ist nicht genau die StringList schuld sondern die Methode
LoadFromFile bzw vermutlich deren Puffer?

Hier der Code für das "manuelle EInlesen")

Code: Alles auswählen

program sortieren_batch;

{$mode delphi}

uses
  Windows, Messages, SysUtils, Classes;

const eingabe : string = 'test.txt';
      ausgabe : string = 'sort.txt';

var
  datei : TStringList;
  ein, aus: Text;
  zeile: string;

procedure Einlesen;
begin
  assign (ein, eingabe); reset(ein);
  readln (ein, zeile);
  while not eof(ein) do begin
    datei.add (zeile);
    readln(ein, zeile);
  end;
  datei.add (zeile);
  close (ein);
end;

procedure Sichern;
var i: integer;
begin
  assign (aus, ausgabe); rewrite (aus);
  for i:=0 to datei.Count-1 do
    writeln(aus, datei[i]);
  close (aus);
end;

function myCompare(liste: TStringList; i1, i2: longint):longint;
var
  r, i, l, l1, l2: longint;
  c1, c2: byte;
  s1, s2: String;
begin
  s1:= liste[i1]; s2:= liste[i2];
  l1:= Length(s1); l2:= Length(s2);
  i:= 1; r:= 0;
  l:= l1; if l > l2 then l:= l2;
  while (r = 0) and (i <= l) do begin
    c1:= ORD(s1[i]); c2:= ORD(s2[i]);
    if c1 < c2 then r:= -1 else
    if c1 > c2 then r:= 1;
    inc(i);
  end;
  if r = 0 then begin
    if l1 < l2 then r:= -1 else
    if l1 > l2 then r:= 1;
  end;
  Result:= r;
end;

begin
  if paramstr(1)<>'' then eingabe:=paramstr(1);
  if paramstr(2)<>'' then ausgabe:=paramstr(2);
Writeln('Create');
  datei:=TStringList.Create;
Writeln('Einlesen');
  Einlesen;
Writeln('Sort');
  datei.Customsort(myCompare);
Writeln('Sichern');
  Sichern;
end.

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6200
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Lesen in eine StringList "teilbar"?

Beitrag von af0815 »

Ich würde so große Dateien in Teildateien aufspalten, diese dann sortieren und dann erst wieder eine sortierte daraus machen.
Oder das ganze gleich über eine Datenbank lösen.
Wenn man alles in den Speicher lesen will, so würde ich klassische Ansätze nehmen, oder nur das Keyword in eine sortierte Stringlist stecken, die eingelesen Zeile selbst in einen Record und den getrennt verwalten. Das ist dann so ähnlich wie es eine DB mit Indizes macht.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 168
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Lesen in eine StringList "teilbar"?

Beitrag von Jorg3000 »

Wenn deine Einlesen-Procedure funktioniert, nimm die einfach.
Gegen die Langsamkeit solltest du ihr allerdings einen Lese-/Schreib-Buffer geben.
Grüße, Jörg

Code: Alles auswählen

procedure Einlesen;
type TBuf = packed Array[0..63*1024-1] of Byte;  // mit z.B. 63 kb hatte ich gute Erfahrungen
var Buf: ^TBuf;   
begin
  assign (ein, eingabe); reset(ein);
  
  New(Buf);
  System.SetTextBuf(ein,Buf^,SizeOf(TBuf));
  
  readln (ein, zeile);
  while not eof(ein) do begin
    datei.add (zeile);
    readln(ein, zeile);
  end;
  datei.add (zeile);
  close (ein);
  
  Dispose(Buf); 
end;

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Lesen in eine StringList "teilbar"?

Beitrag von wp_xyz »

Ähnlich wie af0815 schon geschrieben hat, würde ich die Datei Zeile für Zeile lesen und mir jeweils den Byte-Offset zu jeder Zeile merken. Dann würde ich ein sortiertes Array für die Byte-Offsets aufbauen. Dafür müsste die Datei erneut gelesen werden und jeweils an die zu vergleichenden Offsets gesprungen werden. Am Ende hast du ein Integer-Array, in dem der Zeilenanfang jeder Zeile in der richtig sortierten Reihenfolge vermerkt ist. Zum Schluss liest du die Datei ein drittes Mal, holst dir die Strings in der richtigen Reihenfolge und schreibst sie in die Zieldatei, die dann natürlich sortiert ist.

Damit das ganze nicht zu langsam wird, würde ich der Textdatei vor dem Öffnen einen größeren Buffer zuweisen (SetTextBuf) oder einen gepufferten Stream verwenden, so dass die gesuchte Zeile mit einiger Wahrscheinlichkeit schon im Speicher ist.

Auf diese Art und Weise ist die Speicherbelastung minimal; das ganze müsste funktionieren, solange die Integerliste in den Speicher passt.
Zuletzt geändert von wp_xyz am Mo 15. Aug 2022, 00:59, insgesamt 1-mal geändert.

alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Re: Lesen in eine StringList "teilbar"?

Beitrag von alfware17 »

Hallo zusammen,

nunja Textbuffer habe ich schon drinne gehabt, für alle Eingabe-, Ausgabe- und auch alle Zwischendateien und sogar für input und ouput. So einen richtigen Effekt sah ich dabei nicht,
allerdings ist mein Buffer bisher auch 32 KB, ich kann es gerne mal mit 63 KB probieren.

Und ja, wie gesagt, eine Teile- und Herrsche Strategie habe ich schon drin - sogar mit 4 verschiedenen Mischstrategien, da meine Dateien doch arg unterschiedlich groß sein können und es dann eben auch schon mal 16 oder 100 Zwischenbestände gibt. Ich schätze am Anfang die Dateigröße ab und entscheide mich dann für eines der 4 Mischstrategien oder probiere halt komplett im RAM, wenn es unerwartet abbricht, startet er noch mal mit Mischen. Natürlich ist da neben dem Praktischen auch das Sportliche zu sehen. Bis zu 1 GB sortiert er ohne Probleme und auch schnell im RAM, wie gesagt nur an den READLN und WRITELN wollte ich noch was feilen. Auch das Mischen bei den Zwischendateien kann ja davon profitieren, wenn die READLN und WRITELN schneller werden.

Ich wollte, bevor ich noch etwas verändere, erstmal schauen, ob es wirklich (k)ein Verfahren gibt, wie ich die max 1 GB schneller in den RAM kriege und dann wieder zurück. Und auf die StringList kam ich, weil ich neben meinem eigenen Sortieralgorithmus, der eine Liste benutzt, auch mal einen fremden testen wollte, der aber auf einem Array bzw StringList beruht und natürlich soll es auch noch schneller sein als der eingebaute Sort der StringList.

Den Laufzeittest für diesen kleinsten Baustein (ob nun 1 GB Datei oder etwas weniger) kann ich für die verschiedenen Möglichkeiten an die ich denke (LoadfromfIle, ReadLN. BlockRead)
auch nur ohne Sort machen, jetzt kann ich auch noch mal mit unterschiedlichen Buffer-Größen für das ReadLN und WriteLN experimentieren.

P.S. Warum den Buffer über Pointer und New? Ich habe die als normale Variablen deklariert gehabt, ok da könnte ich eventuell noch optimieren bezüglich Speichernutzung aber die paar Mal 32 KB fielen bisher nicht ins Gewicht.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 168
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Lesen in eine StringList "teilbar"?

Beitrag von Jorg3000 »

alfware17 hat geschrieben:
So 14. Aug 2022, 23:00
P.S. Warum den Buffer über Pointer und New? Ich habe die als normale Variablen deklariert gehabt, ok da könnte ich eventuell noch optimieren bezüglich Speichernutzung aber die paar Mal 32 KB fielen bisher nicht ins Gewicht.
Wenn man den Buffer als lokale Variable deklariert, wird er im Stack abgelegt, welcher aber nur eine begrenzte Größe hat und ggf. überlaufen kann (Stack Overflow).
Nutzt man hingegen New() oder GetMem(), wird der Heap verwendet.
Da man nicht weiß, wie sehr andere aufrufende Prozeduren den Stack schon beanspruchen, halte ich den Heap bei relativ großen Speicheranforderungen für die bessere Wahl.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 168
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Lesen in eine StringList "teilbar"?

Beitrag von Jorg3000 »

Nochmal zur StringList, falls das noch aktuell ist ...
Falls du vorausahnen kannst, dass eine zu lesende Textdatei zehntausende oder sogar hunderttausend Zeilen haben wird, kann man die vorbelegte Kapazität der StringList vorab manuell hochsetzen.
Denn wenn bei einem .Add() der neue String-Pointer nicht mehr in die Pointer-Liste der StringList passt, muss der Pointerlisten-Speicher immer wieder vergrößert und kopiert werden, was immer mehr Zeit frisst.

Eine zweite Sache ist TStringList.BeginUpdate() und .EndUpdate(). Vielleicht bringt das auch ein bisschen.

Code: Alles auswählen

datei.Clear;
datei.Capacity:=100000;

datei.BeginUpdate;
// ... hier die ReadLn-While-Schleife
datei.EndUpdate;
Zuletzt geändert von Jorg3000 am Mo 15. Aug 2022, 07:56, insgesamt 1-mal geändert.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 168
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Lesen in eine StringList "teilbar"?

Beitrag von Jorg3000 »

alfware17 hat geschrieben:
So 14. Aug 2022, 23:00
allerdings ist mein Buffer bisher auch 32 KB
In deinem Beispiel-Code sehe ich keinen Buffer.
Wenn du den Buffer außerhalb deiner Einlesen-Procedure zugewiesen hast, funktioniert er nicht,
denn in der Einlesen-Procedure wird Assign und Reset durchgeführt - und ich befürchte, dass dadurch ein zuvor zugewiesener Buffer nicht mehr zugewiesen ist.

In der Dokumentation wird SetTextBuf immer erst direkt nach Assign+Reset aufgerufen, also so wie in meinem oben geposteten SetTextBuf-Beispiel zu deiner Einlesen-Procedure.

alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Re: Lesen in eine StringList "teilbar"?

Beitrag von alfware17 »

Mein TextBuffer ist nicht in dem Code oben sondern in meinem etwas größeren Sortierprogramm mit den Mischstrategien, das würde hier ein bißchen zu weit führen.

Ich habe dieses Programm aber gerade durchforstet und festgestellt, daß mein SetTextBuf jeweils zwischen dem Assign und dem Reset/Rewrite erfolgt. Das ist normal, da das Reset/Rewrite manchmal in anderen Proceduren erfolgt und weil ich das SetTextBuf erst vor ein paar Jahren nachträglich eingebaut habe. Ich dachte aber es wäre gut und richtig schon vor dem Reset/Rewrite.

Die 63 KB Puffer und verbunden mit dem Umstellen auf Pointer/New kann ich aber auch machen.

Zu Deiner Anmerkung mit der StringList - also 100000 ist weit zu wenig und das BeginUpdate und EndUpdate kann ich natürlich einfügen. Mein Problem war aber anscheinend das LoadFromFile, d.h. ich habe gar keine eigene While-Schleife sondern diese gekapselte Procedur bricht ab. Wenn ich eine eigene While-Schleife nehme, passiert das in der Tat später - das wollte ich aber alles noch untersuchen.

Danke erstmal für Deine Tips. Es ist immer wieder erstaunlich und erfreulich, wie schnell und gut man hier Hilfe bekommen kann,

Epcop
Beiträge: 140
Registriert: Di 29. Mai 2012, 09:36

Re: Lesen in eine StringList "teilbar"?

Beitrag von Epcop »

datei.Capacity:=100000;
Kannte ich noch gar nicht. Aber die Grenze sollte dann trotzdem der verfügbare Arbeitsspeicher sein oder?!

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6200
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Lesen in eine StringList "teilbar"?

Beitrag von af0815 »

Was ist verfügbarer Arbeitsspeicher :D Ich nehme an, du meinst real verfügbaren Speicher. Bei Win 32 ist das max. ca. 1.9GB wenn man die richtigen Flags im PE Header hat dann ca. 3.2GB wenn man mehr als 4GB im Rechner hat. Egal was man als Auslagerung hat.
Bei Win 64 ist es nach oben normalerweise nur durch den Speicher begrenzt, aber wenn man extremen Leistungsvelust in Kauf nimmt eine Mischung aus Speicher und Auslagerungsdatei. Bei mir ist getesterterweise bei ca. 31GB Schluss mit lustig. Wenn der reale Speicher aus ist, so friert der Rechner quasi ein, weil alles so langsam wird. Wir haben das mal aus einem Anlass im englischen Forum unter den verschiedenen Plattformen getestet.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 168
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Lesen in eine StringList "teilbar"?

Beitrag von Jorg3000 »

TStringList.Capacity ist die Anzahl an Zeilen (nicht Bytes), die mindestens vorreserviert werden, aber durch .Add auch überschritten werden dürfen.
Jede Zeile besteht aus einer String-Referenz (Pointer) und einem TObject, somit braucht jeder Zeileneintrag auf einem 32-Bit-System 8 Bytes und auf einem 64-Bit-System 16 Bytes.

Reserviert man mittels .Capacity z.B. vorab 1.000 Zeilen, braucht die StringList z.B. 16 kb, auch dann wenn noch keine einzige Zeile vorhanden ist.
Der Vorteil ist aber, dass dieser Speicher ggf. nur einmal zugewiesen braucht, während ein zeilenweises Auffüllen ohne .Capacity immer mal wieder neuen, größeren Speicherplatz braucht und die alten Einträge kopiert werden müssen. Das braucht viel Zeit.

Wenn man bei einer großen Textdatei vorab 100.000 Zeilen reserviert, werden dadurch zwar 1,6 MB blockiert, aber der Geschwindigkeitsvorteil dürfte nennenswert sein.
Grüße, Jörg

Antworten