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

[stoxx]

Zitat:

So, hab jetzt mal ein bisschen rumprobiert, komme damit aber überhaupt nicht klar.
Es scheitert schon beim blockweisen auslesen. Wenn man einen Block ließt, ist es ja nicht immer sicher, das komplette Zeilen im Block liegen, sondern auch mal abgehackte Zeilen.

´


Da Deine Probleme auch noch im technischen und nicht nur algorithmischen Bereich liegen, schau Dir mal diese Funktion hier an.

diese kannst Du nach Deinen belieben Verändern und nutzen, Dein Index File mit der StartPos und Länge aufzubauen.
Danach solltest Du auch damit gezielt von LineStart bis LineEnd lesen können.

Aber bitte diese Funktion "GrabLine" nicht SO NUTZEN wie sie ist, um eine bestimmte Zeile zu lesen, die Funktin geht nämlich JEDESMALL immer von vorn durch und zählt die Zeilen .... das würde natürich ewig dauern ...


http://www.swissdelphicenter.ch/de/showcode.php?id=1628



...

[Satty67]

Zitat von k6n:

Hallo Satty, Deine Methode habe ich soweit verstanden, aber verbraucht diese Methode nicht auch ziemlich viel Speicher, wenn die Datei z.B so um die 300-500MB groß ist? Dan landet man auch ganz schnell jenseits der 100MB, oder? Ich glaub ich gebs auf.

Ja, wenn die Zeilen nur so lang wie der "part" sind, liest Du sogar die ganze Datei in den Speicher.

Entweder eine Methode, die auf der Festplatte sortiert, dann reicht ein einfacher Index (notfalls auch auf der Festplatte angelegt). Aber dann musst Du jeden String zum Vergleichen neu auslesen. So wie ich das sehe, ist beim besten Sortierverfahren immer noch Faktor 16 beim Element Zugriff nötig, also bis in den mehrstelligen GByte Bereich von der Festplatte lesen.

Wenn Festplattenzugriff nahezu egal sind, ist die Umsetzung ein Kinderspiel... Verglichen wird statt Array[n] eben StringFromFile[n]. Beim "Swap" werden dann Index-Einträge oder gleich die Strings in der Datei getauscht (wobei bei letzterem eben das Problem der unterschiedlichen Record-Länge auftaucht)

[blauweiss]

Meine naive Frage:
Wäre es nicht deutlich geschickter, diese "sehr große" Textdatei in eine Datenbank einzulesen, dort zu sortieren und ggfs. am Ende wieder in eine Textdatei zurückzuschreiben ?

Blauweiss

[himitsu]

das mit der Liste wurde ja schon mehrfach gesagt und wenn man darin den Zeilenanfang mit ablegt, kann man estmal grob vorsortieren und müßte dann nur noch für einen Teil der Vergleiche (vor der Zeilenanfang übereinstimmt) die jeweilige ganze Zeilen nachladen.

Delphi-Quellcode:

Var TextList = Array of Record
      Start:     Int64;
      Length:    Integer;
      TextStart: String[11];  // 11+1 = 12 Byte ... insgesammt 24 Byte pro Zeile
    End;

// 1.000.000 Zeilen = 24 MB
bei sowas wäre dann nur die Zeilenanzahl ausschlaggebend und nicht die Dateigröße.

das Sortieren nur des Arrays (der Indexliste) und dann das sortierte Speichern in einer neuen Datei scheint optimaler zu sein, als alles direkt in der Datei zu sortieren, zumindestens wenn die Zeilen unterschiedlich lang sind.
siehe TPartialTextFile dort kann man ja Zeilen zwischendrin ändern, aber dann müssen alle Zeilen danach womöglich verschoben werden ... (fast) jedesmal, wenn was geändert wird.

[p80286]

Zitat von blauweiss:

Meine naive Frage:
Wäre es nicht deutlich geschickter, diese "sehr große" Textdatei in eine Datenbank einzulesen, dort zu sortieren und ggfs. am Ende wieder in eine Textdatei zurückzuschreiben ?

Blauweiss

und woher soll k6n die Datenbank nehmen? Nur um eine Textdatei zu sortieren eine Datenbank zu benutzen ist ungefähr so wie mit der LKW-Zugmaschine zum Bäcker fahren.

Gruß
k-h

[himitsu]

nicht schön, aber einfach

Delphi-Quellcode:

Type TTextListRec = Record
    Start:     Int64;
    Length:    Integer;
    TextStart: String[11];  // 11+1 = 12 Byte ... insgesammt 24 Byte pro Zeile
  End;
  TTextList = Array of TTextListRec;

Function FilePos(Var InFile: TextFile): Int64;
  Begin
    LARGE_INTEGER(Result).HighPart := 0;
    LARGE_INTEGER(Result).LowPart := SetFilePointer(TTextRec(InFile).Handle,
      0, @LARGE_INTEGER(Result).HighPart, FILE_CURRENT) - (TTextRec(InFile).BufEnd - TTextRec(InFile).BufPos);
  End;

Procedure FileSeek(Var InFile: TextFile; Pos: Int64);
  Begin
    TTextRec(InFile).BufPos  := 0;
    TTextRec(InFile).BufEnd  := 0;
    SetFilePointer(TTextRec(InFile).Handle,
      LARGE_INTEGER(Pos).LowPart, @LARGE_INTEGER(Pos).HighPart, FILE_BEGIN);
  End;

Function GetFullLine(Var InFile: TextFile; Const List: TTextList; Index: Integer): AnsiString;
  Begin
    If (Index < 0) or (Index >= Length(List)) Then
      Raise Exception.Create('index out of range');
    FileSeek(InFile, List[Index].Start);
    ReadLn(InFile, Result);
  End;


Var InFile, OutFile: TextFile;
  List:  TTextList;
  i, i2: Integer;
  S:     AnsiString;
  Temp:  TTextListRec;

Begin
  AssignFile(InFile, 'Unit1.pas');
  Reset(InFile);

  AssignFile(OutFile, 'Unit1_.pas');
  Rewrite(OutFile);

  // einlesen
  i := 0;
  While not EoF(InFile) do Begin
    ReadLn(InFile, S);
    Inc(i);
  End;
  SetLength(List, i);
  FileSeek(InFile, 0);
  i := 0;
  While not EoF(InFile) do Begin
    List[i].Start     := FilePos(InFile);
    ReadLn(InFile, S);
    List[i].Length    := Length(S);
    List[i].TextStart := S;
    Inc(i);
  End;

  // sortieren
  For i := 0 to High(List) - 1 do
    For i2 := i + 1 to High(List) do
      If (List[i].TextStart > List[i2].TextStart) or ((List[i].TextStart = List[i2].TextStart)
          and (GetFullLine(InFile, List, i) > GetFullLine(InFile, List, i2))) Then Begin
        Temp     := List[i];
        List[i]  := List[i2];
        List[i2] := Temp;
      End;

  // sortiertes speichern
  For i := 0 to High(List) do
    WriteLn(OutFile, GetFullLine(InFile, List, i));

  CloseFile(OutFile);
  CloseFile(InFile);
End;

nicht über FilePos und FileSeek wundern ... die alten Delphifunktionen ala ReadLn, Seek undCo. könnten nur bis 2 GB (drum neues FilePos für altes FilePos) und Seek ist bei Textdateien eigentlich nicht möglich (drum neues FileSeek)

ja und das Sortieren könnte man auch noch optimieren, aber das wollte ich dir überlassen

[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;

[himitsu]

Tschuldschung, hatte wärend des Backups ein paar Minütchen Zeit gefunden

Und du hast immerhin noch 'ne Fehlerbehandlung und eine bessere Sortiervariante drin.


Ich hatte es mir dagegen mit ReadLn leicht gemacht (muß kein Zeilenende suchen, allerdings sind diese alten Funktionen nicht grad schnell/optimal ) ... da frag ich mich natürlich warum man bei TFileStrem sowas nicht mit eingebaut hat -.-°

[Satty67]

Auf jeden Fall hab' ich wieder ettliche Synapsen in meinem Gehirn angeregt... und der Threadstarter hat jetzt viel Material zum umsetzen.

Deine Version hab' ich mir natürlich auch gleich kopiert. Mal sehen, ob ich am Wochenende da QuickSort einbaue.

[Satty67]

Der Code von himitsu hat mich erst verwirrt...

Delphi-Quellcode:

  i := 0;
  While not EoF(InFile) do Begin
    ReadLn(InFile, S);
    Inc(i);
  End;
  SetLength(List, i);

Er zählt erst nur die Zeilen um danach nochmal die Datei komplett zu lesen...

...bis ich festgestellt hab, dass das...

Delphi-Quellcode:

i := Length(FileIndex);
SetLength(FileIndex,i+1);

innerhalb einer großen Schleife seeehr langsam ist.

SetLength sollte man also in größeren Blöcken reservieren. Um eine Datei nicht 2x lesen zu müssen, kann man auch große Blöcke reservieren und bei Bedarf immer erweitern (am Ende dann halt auf tatsächliche Größe beschneiden).