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

[k6n]

Hallo,

Ich suche eine Möglichkeit in Delphi eine relativ große (Text-)Datei möglichst schnell alphanumerisch zu sortieren, ohne diese komplett in den Speicher zu laden. Es gibt einige Tools, die das können, z.B die sort.exe, die auf jeden Unix basierten System gibt. Diese Datei ist zwar nicht die schnellste, aber sie schafft es beliebig große Dateien zu sortieren, ohne dabei (zu)viel Speicher zu verbrauchen.

Eine Möglichkeit wäre, die Datei blockweise zu lesen, aber wie kann man diese dann noch komplett sortieren, wenn man keinen Zugriff auf jede Zeile hat?

Kann mir jemand einen Tipp geben, wie man sowas machen könnte?

Gruß

[Satty67]

Die meisten Sortierverfahren vergleichen benachbarte Blöcke. Das sollte also per Buffer lösbar sein.

[k6n]

Zitat:

Zitat von Satty67

Die meisten Sortierverfahren vergleichen benachbarte Blöcke. Das sollte also per Buffer lösbar sein.

Verstehe aber trotzdem nicht ganz, wie man damit eine große Datei sortieren kann.

Kann mir vielleicht jemand ein ganz kleines Beispiel oder so dazu schreiben, damit mir das Prinzip klar wird?

Danke!

[nahpets]

Hallo,

schau mal bitte dort: http://www.stefan-baur.de/cs.algo.sort.html. Auf der Seite werden diverse Sortieralgorithmen beschrieben, zum Teil auch mit Quelltexten zu unterschiedlichen Programmiersprachen. Es geht dort quasi um Theorie und Praxis. Eventuell hilft Dir das ja weiter.

[k6n]

Zitat:

Zitat von nahpets

Hallo,

schau mal bitte dort: http://www.stefan-baur.de/cs.algo.sort.html. Auf der Seite werden diverse Sortieralgorithmen beschrieben, zum Teil auch mit Quelltexten zu unterschiedlichen Programmiersprachen. Es geht dort quasi um Theorie und Praxis. Eventuell hilft Dir das ja weiter.

Die gängigen Sortierverfahren sind mir bekannt, aber die benötigen immer ein komplettes Array mit den Werten und um das zu bekommen, muss man die Datei komplett in den Speicher laden und genau das möchte ich ja nicht.

[himitsu]

wenn es nicht unbedingt schnell sein muß, dann z.B. per TPartialTextfile

oder wenn die datei z.B. aufsteigend sortiert werden soll:
man könnte auch die Datei durchgehn
sich einen Index aller Zeilen anlegen (also wie diese beginnen)

loop:
dann die Datei nochmals duchgehn
sich ein array mit den "kleinsten" Zeilen anlegen (also mit deren Index + Inhalt)
dann zeile für zeile weitergehn (anhand dr Indexe) und jeweils in dem array "größere" durch "kleinere" Zeilen ersetzen
hat am Ende der Datei eine Hand voll der "kleinsten" Zeilen
schreibt diese Zeilen in eine neue Datei
und löscht deren Indexe aus der Liste

und noch geht man wieder zu loop und macht mit den restlichen Zeilen weiter


[add]
oder halt ala RadixSort einen Index (mit den Zeilenanfängen) anlegen, dann diesen sortieren und am ende eine neue Datei anhand der sortierten Indexliste erstellen.

[Dax]

Du kannst die Datei zerteilen, die Teile sortieren und dann wieder mergen ;)

[nahpets]

Hallo,

Zitat:

Zitat von k6n

Die gängigen Sortierverfahren sind mir bekannt, aber die benötigen immer ein komplettes Array mit den Werten und um das zu bekommen, muss man die Datei komplett in den Speicher laden und genau das möchte ich ja nicht.

na schön, der MergeSort, der dort beschrieben ist, dürfte (ggfls. nach Aufarbeitung) ja genau Dein Problem lösen. Der MergeSort im Beispielquelltext arbeitet halt mit zwei Teilen, das sieht aber so aus, als könne man mit etwas Aufwand da auch 4 oder 8 oder mehr Teile draus machen. Für das Sortieren der einzelnen Teile musst Du dann immer nur eines der Teile im Speicher haben und sortieren. Das schreibst Du dann temporär weg. Beim Zusammenfügen nimmst Du zuerst Teil 1 und 2, dann Teil 1 und 3 ...
Na, zum Mergen könnte man dann auch die einzelnen Teile parallel von der Platte lesen und in eine neue Datei schreiben, man liest die einzelnen Teile solange, bis der aktuelle Satz einer anderen Datei kleiner als der eigene ist. Das kann man über (fast) beliebig viele Dateien machen. Der Programmieraufwand dürfte nicht mal übermäßig groß sein.

Wie groß sind die zu sortierenden Dateien den überhaupt?

[p80286]

hallo K6n,

da gibt es was für Dich, ich glaube es heißt mergesort. Ggf. müßtest Du unter externe Sortierverfahren suchen.
Das Prinzip stammt noch aus der Großrechnerzeit.

Im Prinzip funktioniert das in zwei Schritten:
A) lese Eingabedatei
solange Datensatze sortiert vorliegen in Ausgabedatei schreiben.
wenn nicht mehr sortiert dann neue Ausgabedatei anlegen.
B) lies den ersten Datensatz aus allen Ausgabedateien
vergleiche alle Sätze und schreibe den kleinsten in die Pufferdatei
bis alle Ausgabedateien gelesen sind
verarbeite die Pufferdatei mit A)
wenn nur noch eine Ausgabedatei vorliegt ist alles sortiert.

Wenn Dein Verfahren stabil sein soll dann mußt Du beim Wegschreiben der "kleinsten Sätze" den mit dem kleineren Index bevorzugen.
Du kannst das Verfahren beschleunigen indem Du möglichst große Happen vorsortierst. Dann solltest Du allerdings auch hier ein stabiles Verfahren nutzen, also Finger weg von QuickSort.

In der ursprünglichen Version wird nur mit 2 Ausgabedateien gearbeitet. Dann wird immer hin und her geschaltet wenn die Sortierung unterbrochen wird. Das fördert allerdings die Schreib/Lesetätigkeit auf der Platte.

Ich hoffe das hilft Dir weiter

K-H

(ich bin zu langsam!)

[k6n]

Vielen Dank erstmal an alle! :thumb: Ich probiere mal ein bisschen rum, auch wenn ich befürchte, dass es nichts wird. :cyclops:

[alzaimar]

Ich habe das mal folgendermaßen gemacht:
1.Textdatei in ein temporäre Datei kopieren. Dabei alle Zeilen auf gleiche Länge bringen (mit #0 auffüllen). Hauptsache ich kann per Seek auf eine Zeile direkt zugreifen.
2.Quicksort auf die Textdatei loslassen. Bei Blöcken < 20000 habe ich die Zeilen eingelesen, in-Memory-Quicksort drübergebraten und den sortieren Block wieder abgespeichert.
3. Abschließend die temporäre Datei wieder in eine Textdatei zurückschreiben.

Dauer bei einer 75MB großen Datei (vor 8 Jahren, auf einer oberlahmen Krücke) nur ca. 2 Minuten. Sollte heutzutage also schnell genug sein.

[ThomasNds]

Hallo,

die Google-Stichworte, die du suchst, lauten "externes sortieren"
und "Mischsortieren direktes Mischen". Eine sehr schöne Beschreibung des
Sortierens von DAteien, die nicht in den Hauptspeicher passen,
findet sich in Wirth: Algorithmen und Datenstrukturen. Die englische
Version des Buches gibt es hier (ab Seite 67):
http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf
Einen groben Überblick (ohne Code) liefert z.B.
http://www.inf.fu-berlin.de/lehre/SS...ipt/ALP2K2.pdf

Eine Alternative wäre das Einlesen der Strings in einen B-Baum
oder eine Datenbank, um sie dann sortiert herauszulesen.

Andere Alternative, wenn der Hauptspeicher nur geringfügig
zu klein ist: Ein Array mit Verweisen in die Datei anlegen, etwa

Code:

  Index: Array of Record
                   Stringstart: Fileoffset
                    Stringlänge: Integer
                  end

Ein Arrayelement benötigt 8 Byte, also kann man in z.B. 20 MB
gut 2 Millionen Feldelemente anlegen. Das Array wird gefüllt,
indem man einmal durch die ganze Datei durchliest. Dann sortiert
man das Array (hepasort o.ä). Anschließend kann man die
Strings sortiert aus der Datei auslesen und in eine neue
schreiben.

Gruß

T.

[ub60]

Um halbwegs abschätzen zu können, was Du brauchst, konkretisiere doch mal Deine Anforderung:

• Wie viele Zeilen maximal (Größenordnung)?
• Welche Zeileninhalte (gut verteilt, Häufungen, ...)?
• Maximale Zeilenlänge?

ub60

[SirThornberry]

Ich muss mal etwas OT werden :duck:

Zitat:

Zitat von k6n

...Es gibt einige Tools, die das können, z.B die sort.exe, die auf jeden Unix basierten System gibt.

Was passt da nicht? Richtig - das bei einer Unixdistribution ein ausführbare Datei beiliegt die als .exe benannt ist. Das ist höchstens der Fall wenn ein Windowsnutzer unter Linux wütet oder wenn jemand Wine installiert hat...

[k6n]

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.

Mein kläglicher Versuch: :tongue:

Delphi-Quellcode:

const
  BUFSIZE = 20; //kleiner Wert zum Testen
var
  sBuf : Ansistring;
  iRead: Integer;
begin
  with TFileStream.Create('c:\test.txt', fmOpenRead) do
    try
      SetLength(sBuf, BUFSIZE);
      iRead := Read(sBuf[1], BUFSIZE);
      while iRead = BUFSIZE do
      begin
        ShowMessage(sBuf); //Testausgabe
        iRead := Read(sBuf[1], BUFSIZE);
      end;
      if iRead > 0 then //Rest
      begin
        SetLength(sBuf, iRead);
        ShowMessage(sBuf); //Testausgabe
      end;
    finally
      Free;
    end;
end;

Bitte um Berichtigung :lol:

Zitat:

Zitat von ub60

Um halbwegs abschätzen zu können, was Du brauchst, konkretisiere doch mal Deine Anforderung:

• Wie viele Zeilen maximal (Größenordnung)?
• Welche Zeileninhalte (gut verteilt, Häufungen, ...)?
• Maximale Zeilenlänge?

ub60

Also die Dateien können schon sehr groß sein (bis zu 300MB) und die Zeilenlängen variieren sehr stark.

@SirThornberry: Die sort.exe kam von cygwin...

[Satty67]

Die Blöcke müsste natürlich größer sein, aber Du hast recht... da die Records (Zeilen) eine variable Größe haben, wird das ziemlich aufwändig. Zwar kann man innerhalb eines Blockes problemlos sortieren, weil die Gesamt-Blockgröße gleich bleibt, aber sobald zwischen Blöcken ausgetauscht werden muss wird es kompliziert.

Die Idee mit dem angelegten Index (ein paar Post vorher) finde ich da dann doch die bessere Variante. Wobei man die Dateizugriffe minimieren kann, indem man dem Index einen Teil der Zeile spendiert:

Delphi-Quellcode:

TIndexEntry = record
  offset,
  size    : Integer;             // size könnte man auch lassen, wenn man immer auf Zeilenseperator prüft
  part    : array[0..2] of Char  // Bsp. die ersten 3 Zeichen als Muster
end;

1) Man liest den Haupt-Index ein, muss also einmal die ganze Datei durcharbeiten.
2) Sortiert den Haupt-Index Anhand des Teilstring "part"
3) Arbeitet den fertig sortierten Haupt-Index chronologisch ab
- Index(n) <> Index(n+1) dann Zeile gleich in Zieldatei schreiben
- Index(n) = Index(n+1) dann ganze Quell-Zeile in einer neuen Teil-Liste zum nachsortieren puffern, solange bis wieder Index(n) <> Index(n+1). Dann sortiert man diese Teilliste und speichert sie in der Zieldatei.

Den Teilstring "part" müsste man dann anpassen, das es ausgewogen ist zw. Größe Haupt-Index und zu erwartende Teilisten. Je ähnlicher alle Zeilen, desto schlechter wird die Methode. Vorteil wäre halt, das die Datei nur zweimal komplett gelesen wird. Sortieren direkt in der Datei würde etwa die 20fache Menge bedeuten.

Evtl. könnte man sogar für beide Indexlisten TStringList verwenden, wenn man den Offset im Objekt speichert und auf size verzichtet.

[Reinhard Kern]

Zitat:

Zitat von SirThornberry

Ich muss mal etwas OT werden :duck:

Zitat:

Zitat von k6n

...Es gibt einige Tools, die das können, z.B die sort.exe, die auf jeden Unix basierten System gibt.

Was passt da nicht? Richtig - das bei einer Unixdistribution ein ausführbare Datei beiliegt die als .exe benannt ist. Das ist höchstens der Fall wenn ein Windowsnutzer unter Linux wütet oder wenn jemand Wine installiert hat...

Hallo,

du willst uns also damit sagen, dass es hier verboten ist, auch nur auf die Existenz einer Lösung hinzuweisen, wenn sie nicht Bestandteil von Delphi ist? Ich habe ja sowieso nicht mehr viel Hoffnung für die Zukunft der Sprache Pascal/Delphi, aber wenn schon hier im Forum Sektierer mit Tunnelblick und geiferndem Hass auf alles anderssprachliche dominieren, brauche ich mir keine Sorgen mehr machen, dann ist es längst vorbei. So ein Ende unter Fanatikern hat die schöne Sprache Pascal nicht verdient.

Gruss Reinhard

[Satty67]

Also ich glaube er wollte nur sagen, dass sort.exe so garnicht nach unix klingt.

"Geifernder Hass" lese ich in dem Thread nur in einem Post :roll:

[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. :|

[stoxx]

guck Dir nochmal die Antwort von alzaimar an .. die hast Du glaub ich etwas überlesen ..

Ein IndexFile kannst Du auch aufbauen .. sinnvoller wäre aber sowas ...

eine Liste mit folgenden Records ..

TRow = record
FileStartPos, RowLenght : Integer;
end;

Du machst von jeder Zeile ein Element dieses Records (incl des Zeilenumbruches)
Dann nimmst Du einen universellen Sortieralgorithmus, welcher die Verwendung einer SortComparefunktion erlaubt.
Das einzige, was Du nun implementieren musst ist eine Vergleichsfunktion zweier Elemente, die Du vergleichen willst, in Deinem Fall "Zeilen"

Der Sortieralgorithmus vergleicht immer 2 beliebige Elemente, er ruft dazu Deine eigene definierte Vergleichsfunktion auf.
(Den Pointer übergibst Du vorher dem Sortieralgorithmus)
Da Du das File nicht im Speicher hast, musst Du beim Vergleichen zweier Elemente einfach immer die 2 Zeilen vom File einlesen. Das kannst Du deswegen machen, weil Du ja die StartPos und die Länge der entsprechenden Zeile hast .. die 2 eingelesenen Zeilen vergleichst Du, und gibst als Result dem Sortieralgorithmus zurück, welche der beiden Elemente (Zeilen) kleiner ist.
Danach hast Du eine sortierte Index liste, und kannst ein neues File durch umkopieren sortiert erstellen.

so ist das .... :-)

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

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:

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 :angel2:

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 :roll:

[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 :angel2:

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


Ich hatte es mir dagegen mit ReadLn leicht gemacht (muß kein Zeilenende suchen, allerdings sind diese alten Funktionen nicht grad schnell/optimal :oops: ) ... 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).

[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. :thumb:

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. :thumb: Ich setz' mich mal dran und versuche es zu verstehen. :-D

[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 :wink:

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." :gruebel:

himitsu vs. D5 Compiler = 1:0 :mrgreen:

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, :angel2:
welchen es im D7 nicht mehr gibt (hatte extra D7 genommen, um sowas möglichst zu vermeiden :stupid: )


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 :angel2:

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 :!: