Große Datei sortieren ohne komplett in den Speicher zu laden

[alzaimar]

Nach dem DRY-Prinzip ('Dont repeat yourself') solltest Du den Aufruf von GetStringLine so ändern, das die Zeilennummer (anstatt dem FileIndex) übergeben wird:

Delphi-Quellcode:

function GetStringLine(I : Integer; Upper : Boolean): string;
var
  CharStr : PAnsiChar;
  index : TIndex;

begin
  index := FileIndex[I];
  CharStr := StrAlloc(Index.size +1);
  FillChar(CharStr^, Index.size +1, #0);
  aSourceFileStream.Seek(Index.offset, soFromBeginning);
  aSourceFileStream.Read(CharStr^, Index.size);
  if Upper then 
    Result := AnsiUpperCase(CharStr) 
  else 
    Result := CharStr;
  StrDispose(CharStr);
end;

[Satty67]

Aha... für sowas muss man aber ein Auge haben.

Also in dem Fall: Anstatt mehrmals beim Procedure-Aufruf FileIndex[I] schreiben zu müssen, nur "I" schreiben und die Zuweisung innerhalb der Procedure.

Ich geb' mir ja schon Mühe, den Quelltext sauber und strukturiert zu halten. Für solche Dinge, die mir Schreibarbeit sparen, müsste ich wohl mal ein spezialisiertes Buch lesen. Hab' da kaum Ahnung worauf man achten muss bzw. woran man das schnell erkennt.

PS: Hab' es natürlich übernommen, auch ein Teil von himitsu's Variante mit ReadLn zu arbeiten (leider nicht alles, da D5 nicht alles unterstützt). Eine CallBack-Procedure für Progress-Anzeige ist drin... usw. Wenn die Version (mit variabler StringGröße im Index) fertig ist, poste ich das ganze nochmal... in ein paar Monaten.

[k6n]

Danke für die vielen super Vorschläge. Ich setz' mich mal dran und versuche es zu verstehen.

[nahpets]

Hallo,

am Wochenende habe ich mal versucht, ein Programm zu schreiben, das auch große Dateien sortieren kann, ohne dabei allzuviel Speicher zu belegen.

Das Programm ist schnell beschrieben:

Man wähle eine Eingabedatei und eine Ausgabedatei. Wähle die Anzahl der Zeilen aus, die in einem Durchgang sortiert werden sollen, wähle, ob Groß-/Kleinschreibung berücksichtigt werden soll, und starte die Sortierung.

Was passiert nun beim Sortieren?

Die Eingabedatei wird in Teile mit der angegebenen Zeilenzahl aufgeteilt, wobei jeder Teil sortiert wird. Ist die Eingabedatei nun aufgeteilt und die Teile sind sortiert, so werden anschließend die Teile zusammengeführt und dabei wird die Sortierung beachtet. Sofern mehr als 3 Teile erstellt werden, erfolgt die Zusammenführung für vier Teildateien gleichzeitig, andernfalls werden zwei Dateien zusammengeführt.

Die Zusammenführung erfolgt in der Form, dass bei jeder Zusammenführung ein neuer Teil erstellt wird. Dieser Vorgang wird solange wiederholt, bis nur noch ein Teil übrig ist. Die einzelnen Teile werden, sobald sie zusammengeführt wurden gelöscht, um Plattenplatz im Temporärverzeichnis zu sparen. Insgesamt wird hierdurch maximal der zweifache Plattenplatz der Eingabedatei benötigt.

Der Speicherverbrauch des Programmes ist abhängig von der Größe der einzelnen Teile. Je mehr Teile erstellt werden, um so länger ist die Laufzeit des Programmes (es sei denn, dass der Speicherverbrauch so hoch wird, dass Windows die Auslagerungsdatei benutzen muss, dann bricht die Laufzeit stark ein). Bei der Verwendung kleinerer Teile ist der Speicherverbrauch geringer. Allerdings steigt der Speicherverbrauch bei sehr großen Teilen stark an. Welche Größe der einzelnen Teile optimal ist, muss durch Versuch und Irrtum ermittelt werden.

Für die Speicherung der Teile wird das Temporärverzeichnis aus %TEMP% benutzt. Es muss daher sichergestellt sein, dass dort ausreichend Platz zu Verfügung steht. Das Programm prüft, ob der Speicherplatz voraussichtlich ausreicht.

Für die Sortierung wird eine Stringliste benutzt, die für die Sortierung AnsiCompareStr bzw. AnsiCompareText verwendet. Die Sortierung weicht daher von einer Sortierung mit einfachen Größer-/Kleinervergleichen ab.

Das Programm ist weder objektorientiert noch nach irgendwelchen ästhetischen Gesichtspunkten gestaltet, sondern einfach nur nach dem Motto: geht das?

Wer Änderungswünsche hat, realisiere sie bitte und stelle die Ergebnisse hier zur Verfügung

Code:

Laufzeittest mit einer Textdatei von 307.949.380 Byte mit fester Zeilenlänge von 326 Byte.

Rechner 1: Pentium 3 mit 750 MHz und 512 MB Speicher
getrennte Festplatten für Daten, temporäres Verzeichnis und Auslagerungsdatei (3 Festplatten)

Größe der Teile in Zeilen - Laufzeit - Speicherverbrauch - Dateigröße der Teile
     10.000                 00:09:09   ca.  10.720 kByte         3.260.000 Byte
     20.000                 00:08:20   ca.  15.384 kByte         6.520.000 Byte
     50.000                 00:06:48   ca.  35.324 kByte        16.300.000 Byte
    100.000                 00:06:23   ca.  69.708 kByte        32.600.000 Byte
    200.000                 00:06:22   ca. 134.132 kByte        65.200.000 Byte
  1.000.000                 00:36:47   ca. 416.000 kByte       307.949.380 Byte
-------------------------------------------------------------------------------

Rechner 2: Pentium 4 mit 2 GHz und 1024 MB Speicher
eine Festplatte für Daten, temporäres Verzeichnis und Auslagerungsdatei

Größe der Teile in Zeilen - Laufzeit - Speicherverbrauch - Dateigröße der Teile
     10.000                 00:08:57   ca.  13.376 kByte         3.260.000 Byte
     20.000                 00:08:38   ca.  19.000 kByte         6.520.000 Byte
     50.000                 00:07:20   ca.  38.820 kByte        16.300.000 Byte
    100.000                 00:06:35   ca.  71.828 kByte        32.600.000 Byte
    200.000                 00:07:37   ca. 137.780 kByte        65.200.000 Byte
  1.000.000                 00:20:38   ca. 539.144 kByte       307.949.380 Byte
-------------------------------------------------------------------------------

Was schließen wir hier nun aus den Ergebnissen dieser beiden Vergleiche?
Schneller Rechner und viel Speicher sind bei großen Dateien von Vorteil, wenn sie "am Stück" verglichen werden, andernfalls ist die Geschwindigkeit der Festplatten für die Laufzeit nicht unerheblich.

Der Rechner 1 hat deutlich schnellere Festplatten als Rechner 2. Beide Rechner sind nicht unbedingt die neuesten (Alter: Rechner 1: 9 Jahre, Rechner 2: 4 Jahre).

[Satty67]

In dem Thread gibt es auch fertigen Code und Klassen zum Problem.

alzaimar hat eine SkipList angepasst und in eine Klasse gesteckt. Das Teil ist höllisch schnell bei wenig Speicherverbrauch. Die derzeit beste Lösung, die ich gesehen hab' um große Dateien elegant zu sortieren.

PS: 600.000 Zeilen / 8,5 MByte in weniger als 3 Sekunden. (Speicherbedarf kann frei gewählt werden)

[himitsu]

hab mal das FileQuickSort von Satty67 aus Beitrag #27 von den alten Pascal-Funktionen befreit
und auf direkte WinAPI umgestellt (samt Angabe für Windows zur theoretisch "optiomaleren" Cacheverwaltung),

dann noch in der Callback-Prozedur die Statusstrings durch Enumeratoren ersetzt,

das "Cancel" in die Callback-Prozedur verlegt (Result = false = Abbruch)

und die einzelnen Fortschrittsanzeigen (Laden, Sortieren und Speichern) hintereinander gelegt.
(Laden 0% bis 25%, Sortieren 25% bis 75% und Speichern 75% bis 100%)

[add]
ich weiß jetzt nicht ob eventuell noch Fehler enthalten sind (nicht ausgibig getestet), aber hab hier grad mal eine 5 MB Datei in knapp 'ner Sekunde durchgejagt

[edit]
nicht das FileQuickSort hier auf Beitrag #27, sondern das aus Beitrag #1 im anderem Thread

[Satty67]

Freut mich, das es als Basis gedient hat. Die Routinen würde ich wegen der Vergleichbarkeit gerne mal über meine Testdatei jagen, aber unter D5 meckert er:

"[Fataler Fehler] UFileQuickSort2.pas(58 ): Interner Fehler: C3517
Diese Fehlermeldung sollten Sie niemals erhalten - sie bedeutet, daß ein Programmierungsfehler im Compiler vorliegt."

himitsu vs. D5 Compiler = 1:0

Der Compiler steht beim end; von "Function GetLine". Muss mal schauen was ich dezent verändere, damit man das auch mit D5 compiliert bekommt.

Ok, durch ausklammern, konnte ich die verantwortliche Code-Zeile ermitteln:

Delphi-Quellcode:

If (SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN) <> i64.LowPart)
  or (i64.HighPart <> LARGE_INTEGER(FileIndex[Idx].Offset).HighPart) Then Exit;

// genauer der Teil:
SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN) <> i64.LowPart

[himitsu]

joar, ist wohl 'nen knuffier Fehler im Delphi/C++-Compiler,
welchen es im D7 nicht mehr gibt (hatte extra D7 genommen, um sowas möglichst zu vermeiden )


versuch es mal so:

Delphi-Quellcode:

Function GetLine(Idx: Integer; Var Line: AnsiString): Boolean;
  Var W: Cardinal;
    i64: LARGE_INTEGER;

  Begin
    Result := False;
    i64.QuadPart := FileIndex[Idx].Offset;
    i64.LowPart  := SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN);
    If i64.QuadPart <> FileIndex[Idx].Offset Then Exit;
    SetLength(Line, FileIndex[Idx].Size);
    If (FileIndex[Idx].Size > 0) and (not ReadFile(SourceFile, Line[1], FileIndex[Idx].Size, W, nil)
        or (Integer(W) <> FileIndex[Idx].Size)) Then Exit;
    Result := True;
  End;

[Satty67]

Hab' paralell selber gesucht und scheint das casten auf LARGE_INTEGER des Wertes aus einem Record zu sein.

Folgendes hat gereicht:

Delphi-Quellcode:

offset := FileIndex[Idx].Offset; // offset lokal als Int64 declariert
If (SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN) <> i64.LowPart)
    or (i64.HighPart <> LARGE_INTEGER(Offset).HighPart) Then Exit;

Ok und gleich die Werte mit meinem 8,5 MB Wörterbuch (das hat 600.000 Zeilen und ist anders sortiert, als gewünscht):

PrefetchSize=0 : 33313 ms
PrefetchSize=4 : 16187 ms
PrefetchSize=8 : 10860 ms
PrefetchSize=16 : 9281 ms
PrefetchSize=1024 : 9287 ms

Hätte das OpenSource Wörterbuch gerne als gleiche Test-Basis reingestellt, aber ohne OK eines Moderators mache ich das nicht. (Ich kann keine Quellangabe machen)

Wäre interessant, was ein neuerer Compiler aus den Code macht.

[himitsu]

Zitat:

PrefetchSize=1024 : 9287 ms <> PrefetchSize = 1024 : 3.765 ms

da sollte man wohl das "oftmals" so verdamte delphiinterne Caching bei diesen alten Funktionen nicht all zu sehr verdammen

eine Lesecache hab ich ja (in)direkt eingebaut ... mal sehn was passiert, wenn auch eine Schreibcache enthalten ist.


stimmt denn wenigstens die Sortierung?

ach ja, nicht wegen der eingebauten Funktion AnsiCompareText wundern ... wollte es morgen mal in D2009 testen und da ist AnsiCompareText nicht Ansi, sondern Unicode.


bezüglich deines Originalcodes:
bei [i]Offset := Offset + FileIndex.size + 2; mußt du aufpassen, denn es muß nicht immer #13#10 als Zeilentrennung vorhanden sein