FileQuickSort (Dateien mit wenig Speicherlast sortieren)

[Satty67]

http://www.delphipraxis.net/internal...t.php?t=153933

In diesem Thread gab es die Frage, wie man am Besten sehr große Textdateien sortieren könnte, ohne den Arbeits-Speicher zu sehr zu belasten. Im Thread wurde die Methode entwickelt und erste kleine Code-Beispiele gepostet. Für kleinere Dateien ist wohl TStringList eleganter, aber eben auch nicht immer geeignet.

Hier ist nun meine fertige Version, die die Vorschläge zum größten Teil umsetzt. Auszug aus dem Interface:

Delphi-Quellcode:

const
  CancelFileQuickSort : Boolean = False;

type
  TFileQuickSortCallBack = procedure(Status : String; PercentDone : Integer);

procedure FileQuickSort(const SourceFileName, TargetFileName: AnsiString;
                        PrefetchSize : Word;
                        CallBackProcedure : TFileQuickSortCallBack = NIL);

Das meiste ist selbsterklärend:

CancelFileQuickSort auf True, bricht die Routine (leicht verzögert) ab.

TFileQuickSortCallBack kann zum Anzeigen des Fortschitts und für Application.ProcessMessages verwendet werden. (Wird alle 0,1% aufgerufen)

SourceFileName & TargetFileName sollte klar sein. Textdateien bevorzugt ;-)

PrefetchSize ist der interessanteste Wert. Hier wird festgelegt, wieviel einer Zeile zum Vergleich beim sortieren im Arbeitsspeicher abgelegt wird. Bei PrefetchSize = 0 werden die Textzeilen jedesmal komplett aus der Quell-Datei geladen. Bei PrefetchSize > 0 wird nur dann beim Sortieren wieder auf die Quell-Datei zugegriffen, wenn der Ausschnitt nicht eindeutig zu vergleichen ist. Je kleiner die zu sortierenden Dateien, desto größer sollte man PrefetchSize wählen (max. 1024 Zeichen/Zeile). Als ausreichender Kompromiss war bei meinen Tests aber schon ein Wert von 16.

Probleme:

Die Zieldatei-Größe kann um zwei Zeichen abweichen, da das letzte CR/LF unterschiedlich behandelt wird. Sollte aber kein großes Problem sein.

Umlaute werden nicht Normgerecht behandelt. Umlaute werden nach "Z" einsortiert. ich weis schon wie und wo ich ansetzen müsste, aber das kommt evtl. in einer späteren Version.

Ziel-Datei schreiben wird nicht in den Fortschritts-Wert einbezogen. Bei kleinen Prefetch-Werten bleibt es etwas länger auf 99% stehen.

Benchmark Ergebnisse:

Core2Duo E8200, 7200 SATA Harddisk,
Wörterbuchdatei 8,5 MB (teilsortiert: Nomen vor Verben/Adjektive statt alphanumerisch)

PrefetchSize = 0 : 40.500 ms
PrefetchSize = 4 : 17.400 ms
PrefetchSize = 8 : 8.460 ms
PrefetchSize = 16 : 3.950 ms
PrefetchSize = 1024 : 3.765 ms


Hier die komplette Unit zum analysieren:

Delphi-Quellcode:

(******************************************************************************
  Text-Datei sortieren (ganz oder zum Teil im Arbeitsspeicher)
******************************************************************************)
unit UFileQuickSort;

interface

uses SysUtils, Classes, Dialogs;

resourcestring
  txt_SourceFileError = 'Quell-Datei kann nicht geöffnet werden!';
  txt_TargetFileError = 'Ziel-Datei kann nicht geöffnet werden!';
  txt_StatusIndex     = 'Index wird aufgebaut...';
  txt_StatusSort      = 'Sortiere Datei (%d%%)';
  txt_StatusWrite     = 'Schreibe Ziel-Datei...';
  txt_StatusDone      = 'Fertig.';

const
  CancelFileQuickSort : Boolean = False;

type
  TFileQuickSortCallBack = procedure(Status : String; PercentDone : Integer);

procedure FileQuickSort(const SourceFileName, TargetFileName: AnsiString;
                        PrefetchSize : Word;
                        CallBackProcedure : TFileQuickSortCallBack = NIL);

implementation

procedure FileQuickSort(const SourceFileName, TargetFileName: AnsiString;
                        PrefetchSize : Word;
                        CallBackProcedure : TFileQuickSortCallBack = NIL);
const
  FileIndexBlock = 100000;
type
  TGetLineTyp = (glt_File, glt_FileUpper, glt_Prefetch);
  TLineIndex = record
    offset,
    size     : Integer;
    prefetch : AnsiString;
  end;
  TFileIndex = array of TLineIndex;
var
  Promille, LastPromille : Integer;
  FileIndex : TFileIndex;
  SourceFStream : TFileStream;

  {<--- Index aufbauen --->}
  procedure LoadFileIndex;
  var
    i, Offset, Reserved : Integer;
    InFile : TextFile;
    TmpStr : AnsiString;
  begin
    i := 0;
    Offset := 0;
    Reserved := FileIndexBlock;
    SetLength(FileIndex, Reserved);
    if PrefetchSize > 1024 then PrefetchSize := 1024;

    AssignFile(InFile, SourceFileName);
    {$I-}
    Reset(InFile);
    {$I+}
    if IOResult = 0 then begin
      while not eof(InFile) do begin
        ReadLN(InFile, TmpStr);

        FileIndex[i].offset := Offset;
        FileIndex[i].size := Length(TmpStr);
        FileIndex[i].prefetch := AnsiUpperCase(Copy(TmpStr,1,PrefetchSize));
        Offset := Offset + FileIndex[i].size + 2;
        inc(i);

        // Mehr Index-Speicher reservieren
        if i >= Reserved then begin
          Reserved := Reserved + FileIndexBlock;
          SetLength(FileIndex, Reserved);
        end;
      end;
      CloseFile(InFile);

    end else ShowMessage(txt_SourceFileError);

    SetLength(FileIndex, i);
  end;

  {<--- Holt eine Textzeile via Index --->}
  function GetLine(Idx : Integer; LineTyp : TGetLineTyp): AnsiString;

    function LineFromFile: AnsiString;
    var
      CharStr : PAnsiChar;
      index : TLineIndex;
    begin
      index := FileIndex[Idx];
      CharStr := StrAlloc(Index.size +1);
      FillChar(CharStr^, Index.size +1, #0);
      SourceFStream.Seek(Index.offset, soFromBeginning);
      SourceFStream.Read(CharStr^, Index.size);
      Result := CharStr;
      StrDispose(CharStr);
    end;

  begin
    case LineTyp of
      glt_File      : Result := LineFromFile;
      glt_FileUpper : Result := AnsiUpperCase(LineFromFile);
      glt_Prefetch  : Result := FileIndex[Idx].prefetch;
    end;
  end;

  {<--- Index Sortieren --->}
  procedure QuickSort(LoIndex, HiIndex: Integer; LineTyp : TGetLineTyp);
  var
    LoIdx, HiIdx: Integer;
    Pivot: String;
    Swap : TLineIndex;
  begin
    if CancelFileQuickSort then Exit;

    // Lokalen Indexbereich bilden
    LoIdx := LoIndex;
    HiIdx := HiIndex;
    // Mittelwert muss noch optimiert werden
    Pivot := GetLine((LoIndex + HiIndex) div 2, LineTyp);

    repeat
      while GetLine(LoIdx, LineTyp) < Pivot do Inc(LoIdx);
      while Pivot < GetLine(HiIdx, LineTyp) do Dec(HiIdx);

      if LoIdx <= HiIdx then begin
        if LoIdx < HiIdx then begin
          Swap := FileIndex[LoIdx];
          FileIndex[LoIdx] := FileIndex[HiIdx];
          FileIndex[HiIdx] := Swap;
        end;
        Inc(LoIdx);
        Dec(HiIdx);
      end;

    until LoIdx > HiIdx;

    // CallBack nur alle 0,1% aufrufen
    if Assigned(CallBackProcedure) then begin
      Promille := (LoIndex * 1000) div Length(FileIndex);
      if Promille > LastPromille then begin
        LastPromille := Promille;
        CallBackProcedure(Format(txt_StatusSort,[Promille div 10]), Promille div 10);
      end;
    end;

    if LoIndex < HiIdx then QuickSort(LoIndex, HiIdx, LineTyp);
    if LoIdx < HiIndex then QuickSort(LoIdx, HiIndex, LineTyp);
  end;

  {<--- Zieldatei schreiben --->}
  procedure WriteTargetFile;
  var
    OutFile : TextFile;
    i,i2, LoIdx, HiIdx : Integer;
  begin
    AssignFile(OutFile, TargetFileName);
    {$I-}
    Rewrite(OutFile);
    {$I+}
    if IOResult = 0 then begin

      // An Index ein zum Letzten ungleichen Prefetch anhängen
      i := Length(FileIndex);
      SetLength(FileIndex, i+1);
      FileIndex[i].prefetch := FileIndex[i-1].prefetch + 'X';

      i := 0;
      repeat

        // Wenn Index[n] <> Index[n+1] dann schreiben
        if (PrefetchSize = 0)
        or (FileIndex[i].prefetch <> FileIndex[i+1].prefetch) then begin

          WriteLN(OutFile, GetLine(i, glt_File));
          inc(i);

        // Ansonsten erstes gleiches merken und erstes ungleiches suchen
        end else begin
          LoIdx := i;
          HiIdx := i+1;
          while FileIndex[LoIdx].prefetch = FileIndex[HiIdx].prefetch do Inc(HiIdx);
          // Nachsortieren, diesmal mit ganzer Zeile
          QuickSort(LoIdx,HiIdx, glt_FileUpper);
          // Schreiben
          for i2 := LoIdx to HiIdx do
            WriteLN(OutFile, GetLine(i2, glt_File));

          i := HiIdx +1;
        end;

        if CancelFileQuickSort then i := Length(FileIndex);

      until i > Length(FileIndex)-2;
      CloseFile(OutFile);

    end else ShowMessage(txt_SourceFileError);
  end;

{<--- Haupt Routine --->}
begin
  CancelFileQuickSort := False;

  // Index aufbauen
  if Assigned(CallBackProcedure) then CallBackProcedure(txt_StatusIndex, 0);
  LoadFileIndex;

  try
    // Quelldatei exclusiv öffnen, wir wollen ja keine verfälschten Ergebnisse
    SourceFStream := TFileStream.Create(SourceFileName,fmOpenRead or fmShareExclusive);
    try

      If (Length(FileIndex) > 0) and not CancelFileQuickSort then begin

        // Index (Vor-)Sortieren
        LastPromille := 0;
        // Wenn PrefetchSize > 0 muss bei schreiben evtl. nachsortiert werden!
        if PrefetchSize > 0 then QuickSort(0, Length(FileIndex)-1, glt_Prefetch)
          else QuickSort(0, Length(FileIndex)-1, glt_FileUpper);

        // Zieldatei schreiben
        if Assigned(CallBackProcedure) then CallBackProcedure(txt_StatusWrite, 99);
        if not CancelFileQuickSort then WriteTargetFile;

      end;

    finally
      SourceFStream.Free;
    end;
  // Quelldatei Fehler
  except
    on EFOpenError do ShowMessage(txt_SourceFileError);
  end;

  // Wer hätte das im Vorfeld erwartet? Fertig!
  if Assigned(CallBackProcedure) then CallBackProcedure(txt_StatusDone, 100);
end;

end.

In der Anlage ist das komplette Projekt mit kleinem Frontend zum Testen (incl. EXE-Datei).

Die Wörterbuch-Datei (zum Testen) ist nicht dabei, da ich mir nicht 100% sicher bin, ob ich hier als Anlage weitergeben darf. Ist ein Wörterbuch aus einem freien PlugIn von Firefox. Ein Moderator kann sich ja dazu äußern, dann liefere ich die nach (sind 1,8 MByte gepackt).

[Apollonius]

Ich finde, dass die Abbruchmöglichkeit eher durch den Callback gegeben werden sollte. Beschreibbare Konstanten sind nicht gut (hier entsteht auch kein Vorteil gegenüber globalen Variablen - sieht man davon ab, dass es geeignet ist, die OOP-Fetischisten so zu verwirren, dass sie nicht gleich mit dem Geschrei anfangen :mrgreen:). Hier entstehen Probleme bei mehreren Threads.

[Satty67]

Ja, die Pseudo-Konstanten nehme ich auch immer dann, wenn einer Variablen sowieso im Code ein Defaultwert zugewiesen wird. Ist mehr eine Hilfe für mich, das gleich im Interface zu sehen.

Aber ich probiere aus, wie ich es mit einer rein lokalen Variable via Callback-Funktion hin bekomme. Klingt für mich auch eleganter, bin halt nur nicht auf die Idee gekommen :stupid:

[alzaimar]

Du kannst Dir das Nachsortieren komplett sparen, indem Du Die Vergleichsroutine mit einem optionalen Nachladen ausstattest, etwa so:

Delphi-Quellcode:

Function CompareTextlines (aIdx1, aIdx2 : TLineIndex) : Shortint; // -1: aIdx1<aIdx2, 0: beide gleich
Begin
  Result := CompareString (aIdx1.prefetch, aIdx2.prefetch);
  If Result = 0 Then  // prefetch-Strings sind identisch, also nachladen, um sicher zu sein
     Result := CompareString (ReadLine (aIdx1), ReadLine (aIdx2));
End;

Damit genügt es, Quicksort einmalig aufzurufen. Du müsstest Nur die Vergleiche '<' durch einen Aufruf von 'CompareTextLines' ersetzen. In dieser Funktion könntest Du auch eine andere Vergleichsroutine implementieren, die z.B. Umlaute so einsortiert, wie Du es für richtig hältst.

Um das nochmals zu optimieren, kannst Du einen Cache in die Funktion 'ReadLine' packen.

Zu der Callbackroutine: Verpasse der Parameterliste einfach einen Var-Parameter 'Cancel', den man einfach auf True setzt. Den Status würde ich als Enum-Wert (stStart, stRunning, stDone usw.) übergeben, dann kann das auch ein Finne verwenden.

Was mich ein wenig an der Vorgehensweise stört, ist die Tatsache, das sie bei einer wirklich großen Datei wegen Speicherüberlauf einfach nicht funktioniert.

[sx2008]

Du könntest aus der Funktion eine Klasse machen.
Funktionen, deren Code mehrere Bildschirmseiten bedecken und ausserdem eingeschachtelte Unterfunktionen haben, sind ein klares Indiz dafür, dass hier eigentlich eine Klasse hingehört.
Auf neudeutsch wäre das ein "Code smell".

[Apollonius]

Ich sehe keinen Block, der länger als eine Bildschirmseite ist. Was wäre hier der Vorteil einer Klasse?

[Satty67]

Zitat:

Zitat von alzaimar

Du kannst Dir das Nachsortieren komplett sparen

Top Vorschlag, löst dann auch mein Problem mit dem u.U. langsameren Speichern. Da hatte ich einen Denkfehler beim Entwurf, aber es wird ja so auch nicht mehr Speicher belastet und die Dateizugriffe bleiben gleich.

Abbruch im Callback ist jetzt klar und leicht umzusetzen.

Zitat:

Zitat von alzaimar

Was mich ein wenig an der Vorgehensweise stört, ist die Tatsache, das sie bei einer wirklich großen Datei wegen Speicherüberlauf einfach nicht funktioniert.

Über die Grenzen bin ich mir nicht 100% klar. bei einer Datei unter 2 GByte kann es auch zu Problemen kommen?
(die Grenze von 2 GByte sollte ich natürlich abfangen)

[sx2008]

Zitat:

Zitat von Apollonius

Ich sehe keinen Block, der länger als eine Bildschirmseite ist. Was wäre hier der Vorteil einer Klasse?

Ich weiss ja nicht wie gross dein Bildschirm ist, aber die Hauptfunktion (inkl. geschachtelten Unterfunktionen) hat über 210 Zeilen.
Der Code ist sozusagen "verklumpt" und schwer zu testen.
Man kann nicht einfach ein Teilstück (z.B. Aufbau des Index) rausnehmen und für sich testen.

Die Vorteile einer Klasse sind (unter anderem):
* man kann Teilaufgaben übersichtlich in Methoden verpacken
* man kann Teilaufgaben an anderen Klassen deligieren
* Klassen können abgeleitet und so erweitert werden
Zum Beispiel könnte man die Klasse so schreiben, dass Ein- und Ausgabe TStream-Objekte sind.
Das wäre flexibler als nur über Dateien zu sortieren.

[Luckie]

Zitat:

Zitat von sx2008

Du könntest aus der Funktion eine Klasse machen.
Funktionen, deren Code mehrere Bildschirmseiten bedecken und ausserdem eingeschachtelte Unterfunktionen haben, sind ein klares Indiz dafür, dass hier eigentlich eine Klasse hingehört.
Auf neudeutsch wäre das ein "Code smell".

Hhe, da hat schon jemand sein Buch gelesen. Auch ich würde eine Klasse raus machen und mit Ereignissen arbeieten anstatt mit Callbacks. Dann hast du auch das Problem mit deiner Abbruchvariablen gelöst.

[Satty67]

Den Smiley's fehlt eines, das wie ein gerupftes Hühnchen aussieht. :wink:

Das ganze in eine Klasse zu packen, das dauert bei mir dann aber etwas länger. Die ganzen Mechanismen sitzen bei mir noch nicht (ohne OH). Werde es aber wohl dann als Übung nehmen, das ganze besser zu verstehen.

Danke für die konstruktive Kritik. Perfekten Code, mit all den neuen Möglichkeiten von Delphi, werde ich aber wohl nicht hinbekommen.

[Luckie]

Zitat:

Zitat von Satty67

Den Smiley's fehlt eines, das wie ein gerupftes Hühnchen aussieht. :wink:

Oh, dann möchte ich aber auch einen getterten und gefederten Smily. :mrgreen:

Zitat:

Das ganze in eine Klasse zu packen, das dauert bei mir dann aber etwas länger.

Wir sind jung, wir haben Zeit.

Zitat:

Die ganzen Mechanismen sitzen bei mir noch nicht (ohne OH). Werde es aber wohl dann als Übung nehmen, das ganze besser zu verstehen.

Na bitte, geht doch. :mrgreen:

Zitat:

Danke für die konstruktive Kritik. Perfekten Code, mit all den neuen Möglichkeiten von Delphi, werde ich aber wohl nicht hinbekommen.

OOP beherrscht Delphi schön länger. ;)

[alzaimar]

Satty67, kein Problem. Irgendwann hat Jeder mal angefangen. Poste deine Versuche hier rein, wenn du magst. Du siehst, das man hier gerne hilft. Vielleicht fängst Du mit der Schnittstelle deiner FileSorter-Klasse an. Vielleicht so:

Delphi-Quellcode:

Type
  TTextFileSorterStatus = (tfsInitialiting, tfsSorting, tfsDone, tfsAbort);
  TTextFileSortNotifyEvent = Procedure (Sender : TObject; aStatus : TTextFileSorterStatus; aProgressPercentDone : double; Var aCancel : Boolean) of Object;
  TTextFileSorter = Class
  Public
    Constructor Create (aSourceFile, aDestFile : String);
    Destructor Destroy; Override;
    Procedure Sort;
    Property SourceFilename : String;
    Property DestinationFilename : String;
    Property OnSorting : TSortNotifyEvent;
   End;

[Satty67]

Zitat:

Zitat von Luckie

OOP beherrscht Delphi schön länger. ;)

Ok, dann hab' ich mich 15 Jahre erfolgreich davor gedrückt. :lol: Gab es auch schon in meinem TuboPascal 6.0. Aber richtig wichtig wurde (meinem Gefühl nach) erst in Delphi.

@alzaimar:
Danke für die Klassen-Deklaration, darauf kann ich aufbauen.

[Namenloser]

Könnte man die Klasse dann nicht auch gleich von TThread ableiten? Damit müsste man dochz.B. das "Abbrechen" recht elegant lösen können. Außerdem ist asynchroner Code cool :mrgreen:. Die Callbacks müsste man natürlich synchronisieren...

[Luckie]

Überforder ihn erstmal nicht. Eins nach dem anderen. ;)

[Satty67]

Zum Glück bin ich kein IT-Schüler oder Berufs-Programmierer, kann mir also die Aufgaben aussuchen bzw. auch auslassen. Ich kann mich in dem Bereich also nur selbst fordern :wink:

Nachdem ich nun etwas weiter bin, aber noch lange nicht fertig, bin ich am Zweifeln.

Mal ganz abgesehen von Anfängerfehlern im Ausgangscode (Cancle-Variante) und Code-Logik. Abgesehen von der fehlenden Unabhängigkeit der Module (die man mit Parameter-Übergabe herstellen könnte). Wenn man von keiner Basisklasse ableiten will und eine Vererbung auch nicht zu erwarten ist, ist dann die Erstellung einer eigenen Klasse wirklich so sinnvoll?

Den FileIndex typisiere ich außerhalb der Klasse und der Code wird wohl erheblich umfangreicher. Die einzelnen Module bleiben zwar schön übersichtlich, aber der Überblick über das Ganze, geht mir doch schon recht früh verloren. Dann scheint es mir auch so, das Module, die Property-Werte benötigen auch nicht einzeln zu Testen sind. Zumindest nicht einfacher als eine Funktion, die auf eine globale Variable zugreift.

Mal zusammengefasst ausgedrückt: je weiter ich mit dem schreiben der Klasse komme, desto mehr hab' ich das Gefühl, das es weder für die hier gestellte Aufgabe noch für den Programmieraufwand ein Vorteil ist, eine Klasse zu verwenden.

Aber vielleicht mache ich noch zuviel falsch... wenn die Klasse fertig ist wird man sehen. Weitermachen werde ich, weil es mir an anderer Stelle sicher Vorteile bringen wird.

[alzaimar]

Die OOP ist einfach ein anderes Paradigma für die gleiche Sache. Während in der prozeduralen Programmierung die Funktionalität im Vordergrund steht, sind es in OOP die Daten/Objekte.

Es ist fundamental das Gleiche, ob man nun:

Delphi-Quellcode:

Tuwas(Daten);
//oder
Daten.Tuwas();

schreibt, nur verlagert man im 2.Fall die 'Intelligenz' bzw. das Wissen, was man mit diesen Daten anstellen kann an die Stelle, wo auch die Daten definiert sind. Wenn man eine Klasse TKunde hat, steht in der Klassendefinition Alles, was ein Kunde so mit sich anstellen kann.

Das ist im Grunde genommen schon Alles. Die Vererbung ist dann eine logische und zwingende Konsequenz aus diesem Paradigmenwechsel: Wenn ich ein Programm schon aus der Sich der Daten aufbaue, kann ich ja auch die Gemeinsamkeiten der Daten untereinander modellieren.

[Satty67]

@alzaimar

Leider hat der Vorschlag, das Nachsortieren zu vermeiden, nicht den erhofften Erfolg gebracht. Der zusätzliche Vergleich und Funktionsaufruf kostet mehr Zeit. Das frisst den Vorteil bei allen Prefetch-Werten auf!

mit Nachsortieren vs. ohne Nachsortieren

PrefetchSize = 0 : 40.500 ms vs. 53450 ms
PrefetchSize = 4 : 17.400 ms vs. 21730 ms
PrefetchSize = 8 : 8.460 ms vs. 11390 ms
PrefetchSize = 16 : 3.950 ms vs. 7400 ms
PrefetchSize = 1024 : 3.765 ms vs. 7320 ms

man sieht an den Werten, das der zusätzliche Aufwand mindestens ~3500 ms kostet.

In der Klasse (die gleich folgt) hab' ich es aber drin gelassen, das mache ich später wieder raus oder schaue ob sich da was verbessern lässt.

[Satty67]

So also hier mal mein Versuch, das in eine Klasse zu packen:

Interface Teil:

Delphi-Quellcode:

uses SysUtils, Classes;

resourcestring
  txt_SourceFileError = 'Quell-Datei kann nicht geöffnet werden!';
  txt_TargetFileError = 'Ziel-Datei kann nicht geöffnet werden!';

type
  EFileSorterOpenError = class(Exception);

  TLineIndex = record
    offset,
    size     : Integer;
    prefetch : AnsiString;
  end;
  TFileIndex = array of TLineIndex;

  TTextFileSorterStatus = (tfsIndexing, tfsSorting, tfsWriting, tfsDone);
  TGetLineTyp = (glt_File, glt_FileUpper, glt_Prefetch);

  TSortNotifyEvent = procedure (Sender : TObject; Status : TTextFileSorterStatus;
                                PercentDone : Integer; var Cancel : Boolean) of object;

  TTextFileSorter = class
  private
    FInFileStream : TFileStream;
    FLastPromille : Integer;
    FCancelSort : Boolean;
    FFileIndex : TFileIndex;
    FFileIndexBlock : Integer;
    FPrefetchSize : Integer;
    FSourceFilename: String;
    FDestinationFilename: String;
    FOnSorting: TSortNotifyEvent;
    procedure SetPrefetchSize(const Value : Integer);
    procedure SetDestinationFilename(const Value: String);
    procedure SetOnSorting(const Value: TSortNotifyEvent);
    procedure SetSourceFilename(const Value: String);
  protected
    procedure LoadIndex;
    function LineFromFile(Row : Integer): AnsiString;
    function GetIndexLine(Row : Integer; LineTyp : TGetLineTyp): AnsiString;
    function CompareLinesExact(Row1, Row2 : Integer) : Integer;
    procedure SortIndex(LoIndex, HiIndex: Integer);
    procedure WriteTargetFile;
  public
    constructor Create(aSourceFile, aDestFile : String);
    destructor Destroy; override;
    procedure Sort;
    property PrefetchSize : Integer read FPrefetchSize write SetPrefetchSize;
    property SourceFilename : String read FSourceFilename write SetSourceFilename;
    property DestinationFilename : String read FDestinationFilename write SetDestinationFilename;
    property OnSorting : TSortNotifyEvent read FOnSorting write SetOnSorting;
  end;

...und ein Beispiel für die Nutzung:

Delphi-Quellcode:

procedure TFormFileSort.SortNotifyEvent(Sender : TObject; Status : TTextFileSorterStatus;
                                        PercentDone : Integer; var Cancel : Boolean);
resourcestring
  txt_StatusIndex     = 'Index wird aufgebaut...';
  txt_StatusSort      = 'Sortiere Datei (%d%%)';
  txt_StatusWrite     = 'Schreibe Ziel-Datei...';
  txt_StatusDone      = 'Fertig.';
begin
  ProgressBar1.Position := PercentDone;
  case Status of
    tfsIndexing : GroupBoxWork.Caption := txt_StatusIndex;
    tfsSorting  : GroupBoxWork.Caption := Format(txt_StatusSort,[PercentDone]);
    tfsWriting  : GroupBoxWork.Caption := txt_StatusWrite;
    tfsDone     : GroupBoxWork.Caption := txt_StatusDone;
  end;
  Application.ProcessMessages;
end;

procedure TFormFileSort.Button1Click(Sender: TObject);
var
  TextFileSorter : TTextFileSorter;
begin
  TextFileSorter := TTextFileSorter.Create(EditSource.Text,EditTarget.Text);
  try
    TextFileSorter.OnSorting := SortNotifyEvent;
    TextFileSorter.PrefetchSize := SpinEditPrefetch.Value;
    TextFileSorter.Sort;
  finally
    TextFileSorter.Free;
  end;
end;

Die komplette Unit mit der Klasse liegt in der Anlage.

Wahrscheinlich sind noch Anfänger-Fehler drin, da ich mit der Verwendung von Klassen nur wenig bis gar keine Ahnung hab'. Mir sind auch ein paar Fragen gekommen:

Die Verteilung der Variablen und Methoden ist so richtig (private, protected)?
Methoden greifen auf Variablen innerhalb der Klasse zu, damit nicht unabhängig, trotzdem OK?
Class TList (Delphi Source) lagert QuickSort in eine lokale Funktion der Unit aus, warum?
Eigene Exeption sinnvoll, wenn FileOpen ein Standard-Fehler ist?

***

Es ist wohl sinnvoll es aus der Code-Library raus zu nehmen und passend zu verschieben. Ich ändere den Titel dann in etwa wie folgt um. "Von Standard-Code zu einer Klasse" (<- oder bitte vom verschiebenden Moderator gleich passen zu ändern). Danke!

[alzaimar]

Ich verstehe nicht, wieso das bei prefex=0 langsamer sein soll... [edit]Doch: Das Pivot-Element wird nicht gecached. Aber trotzdem müssen komplette Zeilen häufiger gelesen werden.[/edit]

Dein Lösungsansatz widerspricht zudem deiner Eingangs gemachten Vorgabe ('Dateien mit wenig speicherlast sortieren'). Bei hohen Prefex-Größen liest du eh die ganze Datei (und mehr) in den Speicher. Versuche es mit der sehr viel einfachereren Methode:

Delphi-Quellcode:

Class Procedure TFileSorter.ExternSort (aSourceFileName, aDestFileName : String);
Var
  sText : TStringList;

Begin
  sText := TStringlist.Create;
  Try
    sText.LoadFromFile (aSourceFileName);
    sText.Sort;
    sText.SaveToFile (aDestFileName);
  Finally
    sText.Free
  End
End;

[Satty67]

Hatte ich erst auch nicht verstanden, bei PrefetchSize = 0 sollte ja der Zeitaufwand gleich sein. Aber ist es nicht. Test-Datei und Sortier-Routine ist ja bis auf die andere Behandlung der Zeilen identisch.

da ich mich aber auch gleichzeitig noch mit der Klasse an sich beschäftigt hatte, ist da möglicherweise noch ein Fehler drin:

Delphi-Quellcode:

{<--- Holt eine Textzeile aus der Quell-Datei --->}
function TTextFileSorter.LineFromFile(Row : Integer): AnsiString;
var
  CharStr : PAnsiChar;
  index : TLineIndex;
begin
  index := FFileIndex[Row];
  CharStr := StrAlloc(Index.size +1);
  FillChar(CharStr^, Index.size +1, #0);
  FInFileStream.Seek(Index.offset, soFromBeginning);
  FInFileStream.Read(CharStr^, Index.size);
  Result := CharStr;
  StrDispose(CharStr);
end;

{<--- Holt eine Textzeile via Index-Werte --->}
function TTextFileSorter.GetIndexLine(Row: Integer; LineTyp: TGetLineTyp): AnsiString;
begin
  case LineTyp of
    glt_File      : Result := LineFromFile(Row);
    glt_FileUpper : Result := AnsiUpperCase(LineFromFile(Row));
    glt_Prefetch  : Result := FFileIndex[Row].prefetch;
  end;
end;

{<--- Vergleicht Strings genau, also bei Bedarf nachladen --->}
function TTextFileSorter.CompareLinesExact(Row1, Row2 : Integer) : Integer;
begin
  Result := CompareStr(GetIndexLine(Row1, glt_Prefetch),GetIndexLine(Row2, glt_Prefetch));
  // Prefetch gleich, dann aus Quell-Datei vergleichen
  if Result = 0 then
    Result := CompareStr(GetIndexLine(Row1, glt_FileUpper),GetIndexLine(Row2, glt_FileUpper));
end;

{<--- Quicksort des Index mit Nachladen einer Zeile bei Bedarf --->}
procedure TTextFileSorter.SortIndex(LoIndex, HiIndex: Integer);
var
  LoIdx, HiIdx, PivotIdx: Integer;
  Swap : TLineIndex;
  Promille : Integer;
begin
  if FCancelSort then Exit;

  // Lokalen Indexbereich bilden
  LoIdx := LoIndex;
  HiIdx := HiIndex;
  PivotIdx := (LoIndex + HiIndex) div 2;

  repeat
    while CompareLinesExact(LoIdx, PivotIdx) < 0 do Inc(LoIdx);
    while CompareLinesExact(PivotIdx, HiIdx) < 0 do Dec(HiIdx);
    //while GetLine(LoIdx, LineTyp) < Pivot do Inc(LoIdx);
    //while Pivot < GetLine(HiIdx, LineTyp) do Dec(HiIdx);

    if LoIdx <= HiIdx then begin
      if LoIdx < HiIdx then begin
        Swap := FFileIndex[LoIdx];
        FFileIndex[LoIdx] := FFileIndex[HiIdx];
        FFileIndex[HiIdx] := Swap;
      end;
      Inc(LoIdx);
      Dec(HiIdx);
    end;

  until LoIdx > HiIdx;

  // NotifyEvent nur alle 0,1% aufrufen
  if Assigned(FOnSorting) then begin
    Promille := (LoIndex * 1000) div Length(FFileIndex);
    if Promille > FLastPromille then begin
      FLastPromille := Promille;
      FOnSorting(self, tfsSorting , Promille div 10, FCancelSort);
    end;
  end;

  if LoIndex < HiIdx then SortIndex(LoIndex, HiIdx);
  if LoIdx < HiIndex then SortIndex(LoIdx, HiIndex);
end;

Beim Anlegen der Ziel-Datei wird jetzt nur noch Zeile gelesen -> geschrieben

Evtl. könnte man hier

Delphi-Quellcode:

  while CompareLinesExact(LoIdx, PivotIdx) < 0 do Inc(LoIdx);
  while CompareLinesExact(PivotIdx, HiIdx) < 0 do Dec(HiIdx);

Auf Prefetch=0 prüfen und direkt die Dateizeilen (ohne Aufruf von CompareLinesExact) laden.

[Satty67]

Zitat:

Zitat von alzaimar

Dein Lösungsansatz widerspricht zudem deiner Eingangs gemachten Vorgabe ('Dateien mit wenig speicherlast sortieren').

TStringList liest die Datei komplett ein und ist auch bei genug Speicher die richtige Variante.

Im Ausgangs-Thread (siehe Post#1) ging es um Textdateien ab 300 MB, die eben nicht komplett in den Speicher sollen.

Folgende ungünstige Ausgangs-Situation (ungünstig, da kurze Zeilen):

Wörterbuch mit Zeilen bis 20 Buchstaben Länge.
Prefetch ist auf 5
Dann wird nur ca 25% in den Speicher eingelesen (etwas Overhead durch den Index)
Die ganzen Zeilen werden ja nur zum Vergleichen gelesen und danach wieder verworfen.

Je größer die durchschnittliche Länge einer Zeile, desto geringer der prozentuale Speicherbedarf.

[Satty67]

@alzaimar

Den zusätzlichen Funktionsaufruf bei Prefetch=0 ausklammern hat was gebracht, aber nur bei Prefetch=0;

Delphi-Quellcode:

PivotIdx := (LoIndex + HiIndex) div 2;
PivotFullText := LineFromFile(PivotIdx);

repeat
  if FPrefetchSize = 0 then begin
    while LineFromFile(LoIdx) < PivotFullText do Inc(LoIdx);
    while PivotFullText < LineFromFile(HiIdx) do Dec(HiIdx);
  end else begin
    while CompareLinesExact(LoIdx, PivotIdx) < 0 do Inc(LoIdx);
    while CompareLinesExact(PivotIdx, HiIdx) < 0 do Dec(HiIdx);
  end;

Prefetch=0 ist jetzt so schnell wie Prefetch=5 (1-4 sind langsamer). Also erst ab Prefetch=5 wird der zusätzliche Vergleich durch den genaueren SpeicherIndex kompensiert.

Ich müsste dann also ab Prefetch=6 auf die alte Methode zurückgreifen, um in jeder Situation am schnellsten zu sein. Kommt aber wohl auch etwas auf die Quelle an.

[alzaimar]

Zitat:

Zitat von Satty67

Wörterbuch mit Zeilen bis 20 Buchstaben Länge.
Prefetch ist auf 5
Dann wird nur ca 25% in den Speicher eingelesen (etwas Overhead durch den Index)

Ein bisserl mehr ist es schon.
Ein (Ansi)String ist ein Zeiger (4 Bytes) auf eine Struktur, die die Länge (4 Bytes) + Referenzzähler (4 Bytes) enhält. Danach folgt der String sowie 2 Nullen (2 Bytes) am Ende des Strings. Macht also 14 Bytes Overhead pro String (hier nachzulesen).
Dein FileIndex verbrät also je Zeile neben dem Prefetch 26 Bytes an Overhead. (14 Bytes vom String, 8 Bytes vom Record und 4 Bytes vom Array). Somit enthält dein FileIndex mehr Daten, als die Datei groß ist.

Wozu benötigst du das denn? Vielleicht gibt es andere Datenstrukturen, um dein Problem zu lösen.

[Satty67]

Zitat:

Zitat von alzaimar

Ein (Ansi)String ist ein Zeiger (4 Bytes) auf eine Struktur, die die Länge (4 Bytes) + Referenzzähler (4 Bytes) enhält. Danach folgt der String sowie 2 Nullen (2 Bytes) am Ende des Strings.

Gut, der verwendete Datentyp für den Prefetch-String sollte geändert werden. Zwar relativiert sich das bei längeren Zeilen, aber die sind ja nicht garantiert.

Die 8,5 MByte große Testdatei (600.000 Zeilen) belegte bei mir mit Prefetch=0 ca. 4 Mbyte, bei Prefetch=1024 sind es 23 Mbyte. Da muss ich also dringend was ändern.

Zitat:

Zitat von alzaimar

Wozu benötigst du das denn?

Gar nicht... im Initial-Thread hast Du ja auch Vorschläge gemacht, gebraucht hat das ein anderer. Das ist einfach nur der Reiz ein Problem zu lösen.

[alzaimar]

Zitat:

Zitat von Satty67

Gar nicht... im Initial-Thread hast Du ja auch Vorschläge gemacht, gebraucht hat das ein anderer. Das ist einfach nur der Reiz ein Problem zu lösen.

:mrgreen: :wall: :cheers:

Ich würde:
1. Den Prefetch als String[X] (x<=5) statisch deklarieren, somit entfällt ein Großteil des Overheads.
2. Einen Cache zwischenschalten (auch eine Prima Übung).

Der Cache merkt sich die N zuletzt gefetchten Zeilen. Bevor Du eine Zeile aus der Datei liest, fragst Du, ob sie schon im Cache vorhanden ist. Wenn ja, ist gut. Wenn nicht, liest Du sie aus der Datei und packst sie in den Cache. Wenn der Cache voll ist, schmeisst er die am längsten nicht abgefragte Zeile aus dem Speicher raus. Hier musst Du einiges an Gehirnschmalz investieren, damit der Cache nicht zu langsam wird. Speziell das 'Suchen' und 'die am längsten nicht abgefragte Zeile' dürften etwas kniffelig zu implementieren sein, wenn man es richtig schnell machen will.

Vielleicht reicht es, sich die jeweils 3 zuletzt gelesenen Zeilen zu merken. Dann würdest du das Pivot-Element nur 1x pro Sort nachladen müssen. Zudem kannst Du Dir überlegen, kleinere Bereiche (< 10000 Zeilen) komplett in den Speicher zu laden, zu sortieren, und wieder abzuspeichern. Das sollte die Sortierung nochmals vorantreiben

[Satty67]

Gut, also den Datentyp muss ich ändern. Angedacht war ja auch ein array of Char, was aber wieder aufwändiger als ein ShortString wäre. Das hat priorität, weil das ganze ja sonst kein Sinn macht.

TStringList verbrät übrigens mit 29 MB noch mehr Speicher, da wäre ich mit meinen 4 MB ja schon mit der jetzigen Version ganz gut im Rennen. Gleich schnell bin ich aber nur, wenn ich mir auch 23 MB nehme.

***

Caching wird ein wichtiges Thema, das ich mir als zweiten Schritt vornehmen muss. ich denke ich fange mir einem kleinen Cache an, dann kann ich eine korrekte Verwaltung besser kontrollieren. Arbeitet die Verwaltung korrekt, sollte ein Vergrößern dann auch kein Problem sein.

[Luckie]

Also ich habe mir mal deine Klassen Deklaration angeguckt, sieht gut aus.

[alzaimar]

Ich habe mal den Algorithmus im Wiki nachgebaut. Der Vorteil ist, das man den Speicherbedarf festlegen hat. Das Verfahren degeneriert also nicht und funktioniert auch bei beliebig großen Dateien, ist dafür aber langsamer. [Edit]: Nö, sogar schneller.

Im Prinzip passiert Folgendes:

1. Eingabedatei wird in einzelne Abschnitte a <MaxSize> Bytes unterteilt:
1.1 Es werden solange Zeilen eingelesen, bis die Gesamtgröße <MaxSize> erreicht.
1.2 Diese Stringliste wird in-memory sortiert (TStringlist.Sort)
1.3 Abschließend wird diese Liste in einer temporären Datei gespeichert.
2. Ein K-Merge Algorthmus vermischt die K-temporaren Dateien (jeweils sortiert)

Dabei ist (1.2) der eigentliche Bottleneck, obwohl Quicksort zu den schnellsten Sortieralgorithmen gehört.

Kann man das optimieren?

Antwort: Ja.

Der Trick: Wir verwenden eine spezielle (String)Listenstruktur, die Strings beim Einfügen gleich sortiert ablegt und speichern dann den Inhalt in einer Datei ab. Normalerweise würde man das mit einem Array machen, per Binärsuche die Einfügeposition suchen und dort einfügen. Man könnte auch einen Binärbaum verwenden. Das ist aber unter dem Strich nicht schneller als Quicksort, da beide Verfahren vom Aufwand O(log n) sind. Was also tun?

Glücklicherweise existiert eine Listenstruktur, die wesentlich schneller ist: SkipLists. Der Aufwand zum Einfügen eines Objektes ist annähernd O(1), ggü O(log n) bei Binärsuche. Beim Einfügen von n Elementen werde ich also mit einer Skipliste in O(n) fertig sein, ggü O(n log n) bei einer Binärsuche bzw. Quicksort.

Herkömlicher Code:

Delphi-Quellcode:

While not Eof (Inputfile) do begin
  ReadLn (Inputfile, sText);
  sStringList.Add (sText);
End;
sStringList.Sort;
sStringList.SaveToFile (OutputFilename);

optimierter Code;

Delphi-Quellcode:

While not Eof (Inputfile) do begin
  ReadLn (Inputfile, sText);
  sSkipList.Add (sText);
End;
Assignfile (OutputFile, OutputFilename);
Rewrite (OutputFile);
sSkipList.First; // Iterator auf 1.Element setzen
While Not sSkipList.EndOfLine Do Begin // Solange noch Elemente in der Liste sind
  Writeln (OutputFile, sSkipList.CurrentKey); // Aktuellen Iterator-Wert speichern
  sSkiplist.Next; // Zum nächsten Wert gehen
End;
CloseFile (OutputFile);

Anstatt also eine Stringliste zu füllen und anschließend zu sortieren, fülle ich eine Skiplist und speichere den Inhalt ab, indem ich die Liste sequentiell von vorne nach hinten durchlaufe. Der Inhalt ist damit automatisch sortiert

Mit dieser Optimierung sortiert die vorgestellte Klasse eine 6MB-Textdatei in 1.6 anstatt 6.3 Sekunden (bei 1MB Puffer).
150MB werden in 60 Sekunden sortiert, ggü. 160 Sekunden mit herkömmlichem Sort (bei 10MB Puffer).

Auch wenn die hier vorgestellte Klasse langsamer sein sollte, als Satty67's Version (wovon ich mal ausgehe), könnte man das Skiplist-Verfahren auf seine Klasse anwenden, um sie noch weiter zu optimieren.

[Satty67]

Angewendet auf meine Wörterbuch (wegen der Vergleichbarkeit):

Mit Defaultwert aMemoryToUse=10.000.000 belegt es ~59 MB Arbeitsspeicher.
Mit aMemoryToUse=1.000.000 nur noch ~7 MB :thumb:
(Im Taskmanager sieht man das schlecht, weil es so fix ist)
Das Ding ist in der Version ganz schön schnell (~2200 ms)

Sortiert in der Version jetzt noch Binär, statt alphanumerisch (bei meiner wenigstens A-Z/a-Z korrekt), aber selbst bei Verdoppelung der Zeit, wird es damit nicht langsamer als die QuickSort Variante (mit Speicher).

PS: Der QuickSort von Borland für TList ist 6% langsamer als mein QuickSort (um meine Ehre wenigstens noch zu retten) :lol:

Zitat:

Zitat von Luckie

Also ich habe mir mal deine Klassen Deklaration angeguckt, sieht gut aus.

Danke, ein bisschen Lob kann ich jetzt gebrauchen. War am Ende auch nicht ganz so schlimm, auch wenn ich da noch nicht automatisiert arbeiten kann.

€: gerade gewundert warum bei der SkipList-Klasse die Ergebnisliste kleiner ist. SkipList entfernt doppelte Einträge... müsste man entsprechend ändern, wenn die Datenmenge nicht verändert werden darf.

[alzaimar]

Wat? Dat Teil is schneller? :gruebel: Lustic, aber diese Skiplistoptimierung ist wirklich nett.

Edit: Ich hänge mal eine verbesserte Version (mit doppelten Einträgen und überschreibbarer 'CompareKeys' Methode) an. Kannst ja mit rumspielen.

Noch eins: Findest Du 60MB Speicherverbratung schlimm? Du hast doch genug davon, also...

[Satty67]

Zitat:

Zitat von alzaimar

diese Skiplistoptimierung ist wirklich nett.

Ist sie, das macht schon Spass. Hatte noch versucht mit der QuickSort/InsertionSort Kombo zu punkten, konnte aber nur beim reinen Speicher-Sortieren nochmal 20% gut machen... wenn es über die Festplatte läuft, ist die SkipList Variante einfach nicht zu schlagen.

Zitat:

Zitat von alzaimar

Noch eins: Findest Du 60MB Speicherverbratung schlimm? Du hast doch genug davon, also...

Also Ich hätte auch eine 300 MB Datei gleich via Speicher sortiert... aber denke 60 MB sollte jeder frei haben, sonst ist es besser erst mal den Rechner zu optimieren ;)