FileQuickSort (Dateien mit wenig Speicherlast sortieren)

[Luckie]

Zitat von Satty67:

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

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

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.

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 von Luckie:

OOP beherrscht Delphi schön länger.

Ok, dann hab' ich mich 15 Jahre erfolgreich davor gedrückt. 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 . 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

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;