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

[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

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:

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

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

Ich muss mal etwas OT werden :duck:

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

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