Hi!
Hat jemand jemand eine Idee zum Thema?

Was möchtest du machen? Eine Textdatei mit einer Größe von mehr als einem GB zeilenweise sortieren? Viele Textdateien mit insgesamt 1 GB? Oder was anderes?

Im Grund handlt es sich wieder mal nur um einen kleinen Denkanstoß zur Lösung einen Problems. Welches ich dann auf mein Projekt übertrage.

Ich habe 1 Datei > 1GB deren ASCII-inhalt ich nach Alphabet sortiern will und da versuche ich es erst gar nicht mit StrList.Sort

Hallo,

willst Du Buchstaben oder Worte oder Zeilen sortieren?

Gruss Horst

Beides. Es wird aber alles als String behandelt.

Hallo,

drei Moeglichkeiten und als Antwort beides
Du meinst also Worte und Zeilen , oder ?

Gruss Horst

Schau mal, ob du unter EXTERNES SORTIEREN was brauchbares findest. Ich habe sowas selbst noch nicht implementiert, aber eine grundsätzlich brauchbare Methode ist es, die grosse Datei in mehrere kleine aufzuteilen, diese separat zu Sortieren und die sortierten Dateien wieder mischen.

Stefan

Sowas hier mächte ich sortieren:

bla55vathn
asdhasd7ds
sd77dssdas
dsdadsd8aa
{ ein paar miilionen weiter }
sdhsaduasösdad
asjdasdausduas
asjdasjduasdas
sadsadsa7as78das89
asdasda9sasdasß´
assaa8asas
{und noch ein paar miilionen weiter }
sajfasdhjfsdäsd
dsfsddf8dsf66dsfd
2312h2hh3h2h32312

//Edit: @Stefan.Buchholtz an sowas dachte ich auch. Mal sehen ob ich irgendwie umsetzten kann.

Das Verfahren mit dem Mischen nennt sich Mergesort. Implementierungen hierzu findet man bestimmt auch im Forum - wenn auch nur in der Form, dass da überschaubare Listen sortiert werden.
Das Verfahren müsste halt um die Aufteilung der großen Datei erweitert werden. Und auch das Zusammenfügen hinterher zu einer großen Datei muss man n bissel überlegen, wie man das am besten macht.

Ich habe mir schon bei deinem ersten Posting gedacht, dass du deine Passwortlisten sortieren willst.

Ich hatte mal das Problem, eine nur 70MB grosse Datei sortieren zu müssen.
Ich hatte mit Mergesort von Martin Waldenburg experimentiert (gabs/gibs auf torry), aber meine Version war dann doch schneller:
1.Pass: ASCII-Text in ein File Of String[xxx], wegen Random Access zugriff
2.Pass: Quicksort auf Filebene, bis die Blöcke < 20.000 Zeilen sind, dann per Stringliste einlesen, Sort, speichern
3.Pass: File Of String[xxx] wieder in die Text-Datei

[edit] Mehr zu dem Thema : www.sortieralgorithmen.de/index.html [/edit]

klappte ganz gut. Hier könnte ein Heapsort noch schneller werden. Damals reichte mir aber die QSort-Variante.
Wenn Du eine schnelle DB hast (z.B. MSSQL mit BCP) dann schiebst du die Zeile einfach in den server und lässt den die Arbeit machen. Dazu sind sie auch da. BCP ist ein Tool (Bulk Copy), um -rizzafizz- Unmengen von Daten direkt in den server zu schaufeln. Das geht mit ca. 10000 recs pro Sekunde, bis RAM voll ist. Bei deinem GB könnte das dauern. Tut es aber sowieso.

War wohl nichts.

Horst_H hat folgendes geschrieben:

War wohl nichts.

Äh...

Hallo,

ein neuer Anlauf.
Vorab:
Ich gehe mal davon aus es existiert nur ein Wort pro Zeile in der Textdatei.

TSTringList.Sort skaliert sehr gut.
Ich habe mal Testdateien mit 10000,x10,..bis 10e7 Zeilen erzeugt.


diese sortierten in


Der Speicherbedarf ist etwas hoch 16 Byte+(LaengeString+1)div 8+1)*8

alzaimer hat ja seine Daten in ein einheitliches Format gebracht, das ist aber nicht unbedingt notwendig. Ich dachte eher an pChar.
Man sortiert erst einmal soweit wie moeglich intern und schreibt die Daten in eine neue Datei weg.
Etwa so:
Teile Dateigroesse in 2^?? gleiche Abschnitte(a x-Mbyte), so dass mergen gut moeglich ist,zb. < 32 Mbyte , auf.
Jetzt ein Vielfaches k dieser Abschnitte zusammenfassen und intern sortieren.
wiederhole
..lese solange Daten in stringlist wie es geht (k Abschnitte).
..sortiere.
..schreibe in neue Datei, alle X-Mbyte EndPosition merken.
Bis alle Daten verarbeitet.

wiederhole
Jetzt Abschnittsweise mergen von 0..k-1 mit k..2*k-1{2k..3k-1 mit 3k..4*k-1 etc}
also einlesen von Abschnitt 0 und k mergen,falls ein Abschnitt leer dessen Nachfolger laden, kontinuirlich wegschreiben und wieder all X-byte EndPosition merken.
K verdoppeln
bis k = alle Abschnitte.

Ich hoffe das ist einigemassen verstaendlich.

Gruss Horst

Meine Lösung stammt von 1999, die werde ich mal überdenken

Mal ein anderer Ansatz:

Erzeuge 26 Dateien, die nur Worte mit dem jeweils gleichen Anfangsbuchstaben beinhalten.
Sortiere diese dann intern, am Besten mit Quicksort.
Füge dann die 26 Dateien wieder zusammen.
Das ganze funktioniert gut, wenn sich die größte entstehende Einzeldatei intern mit Quicksort sortieren lässt.

Ansonsten schreib mal etwas genauer:
Wie lang ist die längste Zeile?
Wie viele Zeilen sind es etwa?
Kommen alle Anfangsbuchstaben etwa gleich häufig vor oder handelt es sich um eine Art Wörterbuch?
Muss die Datei nur einmal sortiert werden, oder häufiger?

Dann kann man sicher qualifiziertere Antworten geben.

ub60

So, hier mal eine Lösung, die laufen sollte. Geht bestimmt schneller. Aber diese hier würde auch 100TB sortieren, dauert vielleicht ein wenig, bombt aber nicht wegen Speichermangel aus.

Vermutlich wäre ein Mergesort mit temporären Datein noch besser, aber so gehts eben auch. Man sortiert ASCII-Dateien ja auch nicht jeden Tag.

Es soll sogar Leute geben, die ihre Texte in einer DB speichern. Soll sogar klappen

Hier eine Lösung, die wesentlich schneller ist. Sie ist von Martin Waldenburg und basiert auf dem Mergesort Algorithmus.

Hallo,

hah! Comparetext wird benutzt.Das bringt allein schon einen !!! 5-fachen Zeitgewinnn !!! gegenueber TStringlist, welches AnsiStringCompare benutzt.
Ich teste das Programm gerade mit einer 1.2 Gbyte Datei (100MioZeilen x10 Zeichen+#13#10)
Dabei werden zuerst Dateien a 11.18 Mb(0% Leerlauf) erzugt dann -> 55.92 Mb ->279,6 Mb(10% Leerlauf) -> fertig.

Jetzt ist es fertig in 12min04s.-> 1.66 Mb/s
Das ist doch recht flott.
Ich teste es jetzt mit 32Mbyte (bei 64 Abbruch -> zuwenig Speicher bei 1 Gbyte RAM, wozu habe ich den gekauft? ).
Bisheriger maximaler Speicherbedarf 88Mbyte, 500 MB verfuegbar.
Es dauert eine Ewigkeit laenger...15min10s (Dummerweise auch eine aeltere Festplatte, also Aussage ohne Wert).

Also ganz bin ich nicht ueberzeugt, da das innere Sortieren zu langsam ist.

Gruss Horst

Bin wieder da...

Luckie hat folgendes geschrieben:

Ich habe mir schon bei deinem ersten Posting gedacht, dass du deine Passwortlisten sortieren willst.

Käse besorg Dir ne neue Glaskugel, Luckie - die Alte scheint kaputt zusein! Warum sollte ich PW-Listen nach Alphabet sortieren?? Und dann auch noch so aufwendig...

Die anderen Möglickeiten werde ich mir mal ansehen.