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 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 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 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! Ich probiere mal ein bisschen rum, auch wenn ich befürchte, dass es nichts wird.