Zeilen in Datei lexokografisch sortieren ?

[tuxedo]

Servus,
stecke mal wieder an ner Aufgabe fest.

Ich soll ein Programm schreiben das eine beliebig lange Datei X einließt und die Zeilen lexikografisch sortiert in eine Datei X.sort schreibt.
Das ganze soll möglichst effizient sein und darf keine einschlägigen Bibliotheksfunktionen verwenden...

Ein naiver Ansatz wäre alle Zeilen in ein eindimensionales String-Array packen und mit Quicksort in Kombination mit String.compareTo() sortieren lassen. Anschließend alles in X.sort schreiben.

'N Kumpel hats getestet... Dauert relativ lang. Zudem bricht mir das ganze bei Textdateien um 30MB ab...Zu wenig Speicher.
Mein zweites Bedenken bei diesr naiven Lösung: ist compareTo() eine einschlägige Bibliotheksfunkion, oder nicht ?

Das ganze muss sich doch auch Speicher- und Laufzeiteffizient lösen lassen...Aber ich komm nicht drauf. Hatte schon etliche einfälle. Habe diese aber alle wieder verworfen weil sich beim programmieren rausgestellt hat daß diese auch nicht praktikabel, gar nicht anwendbar sind.

Gruß
Alex

 

[pogo]

mein tipp nimm nicht quick sort sondern lieber mergesort oder heap sort, die sind im worst case schneller wie der quick sort, da sie garantiert n ld(n) brauchen und nicht länger

 

[Bleiglanz]

braucht Heapsort nicht weniger Speicher als Mergesort? Nachlesen!

Wenn dein Speicher ausreicht, dann nimm eine SortedMap und füge jede neu gelesene Zeile einfach ein - ggf. identische mittzählen- (das Ding ist ja vorsortiert und das Einfügen in eine vorsortierte Liste geht seeeehr viel schneller als das nachträgliche "Vollsortieren")

gibts eine Begrenzung der Stringlänge?

Ich kenn die Aufgabe eigentlich nur als Spassaufgabe mit verschiedenen Zahlen in einem festen Bereich (ints oder ähnlichem), nämlich so:

angenommen du willst eine Datei mit 1 Mio Integers, die alle verschieden sind und die zwischen 1 und 10 Mio liegen und die zeilenweise daherkommen sortieren.

dann nimmst einfach ein boolean[10000000] (oder gleich ein BitSet) und setzt ein true, wenn die Zahl auftaucht....

Aber bei Strings?

Offenbar musst du die Strings alle einlesen (wenn du nicht mit verteilten Dateien arbeiten willst)

mach halt buckets (A,B,...) nach Anfangsbuchstaben und sortiere diese getrennt - ggf. mit den ersten beiden Buchstaben als key.

eventuell auch die Datei einmal zusätzlich lesen und analysieren und für jede Kombination speichern, wann sie das letzte Mal vorkommt, das bringt aber wohl nichts

Wenn du wirklich bel grosse Textdateien sortieren willst (30 MB - 300 MB ---usw), dann sehe ich auch nicht wie das gehen soll, vor allem wenn die letzte Zeile mit A anfängt. Dann muss du sie ja komplett lesen und kannst nicht anfangen zu schreiben...

Aber auch meine Idee ist problematisch

Angenommen du beschliesst, die Datei 26 mal zu lesen, beim ersten durchlauf alle A... zu nehmen, zu sortieren und dann rauszuschreiben (usw.)

dann darfst du nicht readLine verwenden, sonst müllst du ja deinen Speicher voll (und die GC dauert dann etwas länger...)

 

[pogo]

jup heap sort braucht weniger speicher al merge sort.