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

[Satty67]

Das war klar... himitsu wieder schneller, hat sogar den Index mit VorschauString umgesetzt

Ich hatte schon eine erste Version in Arbeit, die noch ohne Vorschau-String (part, TestStart etc.) arbeitet und wollte die danach optimieren. Den Code wegschmeißen will ich jetzt auch nicht, auch wenn er noch Fehler enthalten könnte:

Delphi-Quellcode:

procedure FileQuickSort(SourceFileName, TargetFileName: String);
type
  TIndex = record
    offset,
    size  : Integer;
  end;
  TFileIndex = array of TIndex;
var
  FileIndex : TFileIndex;
  aSourceFileStream : TFileStream;

  // Liest eine Stringzeile aus der Quelldatei
  function GetStringLine(Index : TIndex; Upper : Boolean): string;
  var
    CharStr : PAnsiChar;
  begin
    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;

  // QuickSort mit Datei-Zeilen
  procedure QuickSort(LoIndex, HiIndex: Integer);
  var
    LoIdx, HiIdx: Integer;
    Pivot: String;
    Swap : TIndex;
  begin
    // Stelle die Ordnung bzgl. des Pivotelements her.
    LoIdx := LoIndex;
    HiIdx := HiIndex;

    // Ermitteltes Pivot-Element wäre besser, aber erst mal nur
    Pivot := GetStringLine(FileIndex[(LoIndex + HiIndex) div 2], True);

    repeat
      while GetStringLine(FileIndex[LoIdx], True) < Pivot do Inc(LoIdx);
      while Pivot < GetStringLine(FileIndex[HiIdx], True) 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;

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

var
  i, count, lastOffset : Integer;
  aTargetFile : TextFile;
  Chr : AnsiChar;
begin
  try
    // Quelldatei exclusiv öffnen, wir wollen ja keine verfälschten Ergebnisse
    aSourceFileStream := TFileStream.Create(SourceFileName,fmOpenRead or fmShareExclusive);
    try

      // DateiIndex aufbauen
      lastOffset := 0;
      count := aSourceFileStream.Read(Chr, 1);
      while count = 1 do begin
        case Chr of
          #13 : begin
            // Return, aktuelle Zeile ist abgeschlossen
            // Index wird erweitert, Offset und Size gespeichert
            // neuer letzter offset ans Ende setzten
            i := Length(FileIndex);
            SetLength(FileIndex,i+1);
            FileIndex[i].offset := lastOffset;
            FileIndex[i].size := aSourceFileStream.Position - (lastOffset+1);
            lastOffset := aSourceFileStream.Position;
          end;
          #10 : begin
            // LineFeed folgt, dann lastOffset +1
            inc(lastOffset);
          end;
        end;
        count := aSourceFileStream.Read(Chr, 1);
      end;
      // Letzte Zeile, die kein abschließendes #13 hatte, auch noch speichern
      i := Length(FileIndex);
      SetLength(FileIndex,i+1);
      FileIndex[i].offset := lastOffset;
      FileIndex[i].size := aSourceFileStream.Position - (lastOffset);


      // QuickSort des Index anwerfen
      if Length(FileIndex) <> 0 then QuickSort(0, Length(FileIndex)-1);

      // Zieldatei ausgeben
      AssignFile(aTargetFile, TargetFileName);
      {$I-}
      Rewrite(aTargetFile);
      {$I+}
      if IOResult = 0 then begin
        for i := 0 to Length(FileIndex)-1 do
          WriteLN(aTargetFile, GetStringLine(FileIndex[i], False));
      end;
      CloseFile(aTargetFile);

    finally
      aSourceFileStream.Free;
    end;

  // Quelldatei Fehler
  except
    on EFOpenError do ShowMessage('Quell-Datei kann nicht geöffnet werden!');
  end;
end;