Entwickler-Ecke :: Thema anzeigen - Sortierung mehrerer Spalten in einem festen Satzaufbau

haschme - Mi 14.10.15 09:52
Titel: Sortierung mehrerer Spalten in einem festen Satzaufbau

Hallo zusammen,

wie die Überschrift schon sagt, versuche ich derzeit ein Tool zu entwickeln das eine Datei mit festen Satzaufbau individuell sortieren kann.

Der Nutzer kann nach Übergabe der Datei die Spalten auswählen, die sortiert werden sollen. Dabei kann jede Spalte individuell konfiguriert werden.

Z.B. Spalte 1 soll Aufsteigend, alphanumerisch sortiert werden, Spalte 2 soll dagegen Absteigend und Numerisch sortiert werden.
(Es sollen auch noch mehr Spalten möglich sein!)

Spalte 1-------------Spalte 2-------Spalte3...
--B---------------------5
--C---------------------9
--A---------------------7

würde dann zu

Spalte 1-------------Spalte 2-------Spalte3...
--A---------------------9
--B---------------------7
--C---------------------5

Ich habe das ganze schon mit einem Dataview ausprobiert, dem ich einfach ein Datatable übergebe und dann so sortiere wie ich es mir wünsche.
Hat auch zuerst wunderbar geklappt.
Doch sobald die Eingabedateien zu groß werden reicht der Arbeitsspeicher einfach nicht mehr aus, da die Dataview leider sehr schnell anwächst.

Hätte da jemand eine Idee, wie ich es besser machen kann? :-)

Vieln Dank!

haschme - Mi 14.10.15 14:29

Also zuletzt waren es ca. 11 millionen Datensätze mit einer Satzlänge von 550 Zeichen.
Da die Userrechner nur 4GB Arbeitsspeicher zur Verfügung haben war die Sortierung nicht mehr möglich.

Zu deiner Antwort: Ein DataGridView ist zum Anzeigen von Daten da oder? (habs selbst noch nicht oft benutzt)
Ich will die Daten die sortiert werden garnicht anzeigen sondern sortieren nach den vom Nutzer übergebenen Spalten und dann in eine Ausgabedatei schreiben.

Hatte zuvor die Spalten die sortiert werden sollten sowie deren Zeilennummer in einer Datatable eingelesen und diese dann an ein Dataview übergeben.
Danach habe ich dann an Dataview.Sort einen String übergeben der je nach Konfiguration der Spalten angibt wie sortiert werden muss.

Danach bin ich die Dataview mit einer foreach-Schleife durchgelaufen und habe die einzelnen Zeilen aus der Quelldatei in einem String eingelesen und direkt in die Ausgabedatei geschrieben.

Leider brauchte die Dataview bei den 11 millionen Datensätzen einfach zuviel RAM.

Th69 - Mi 14.10.15 15:11

Hallo,

da sind ja auch mindestens 12GB (wegen interner Speicherung der Strings im UTF16 bzw. UCS-2 Format 2 Byte je Zeichen).

Aber welcher Anwender soll sich denn soviele Daten auf einmal anschauen? Und würde es nicht mehr Sinn machen, diese Daten in eine Datenbank zu bringen und darauf dann entsprechende Filter- und Sortieroperationen aufzurufen?

haschme - Mi 14.10.15 15:17

Hallo, ich habe meinen vorherigen Beitrag nochmal editiert.
Ich denke es lag ein Missverständnis vor.

Also die Daten sollen nicht vom Nutzer angesehen werden sondern die Daten sollen nur verarbeitet bzw. sortiert werden und in einer Datei (z.B. Textdatei) wieder ausgegeben werden.

Th69 - Mi 14.10.15 16:18

OK, aber selbst ohne Anzeige (für den Anwender) sind es eben einfach zu viele Daten, so daß ich dir eben eine [embedded] Datenbank (wie z.B. SQLite) empfehlen würde (für C# z.B. sqlite-net [https://github.com/praeclarum/sqlite-net] oder Mono.Data.SQLite [http://www.mono-project.com/docs/database-access/providers/sqlite/]).

Ralf Jansen - Mi 14.10.15 17:47

Ohne Datenbank brauchst du ein ~externes~ Sortierverfahren das immer nur Teile deiner Datei lädt. Die auf divide and conquer basierenden Sortierverfahren bieten sich da an. Z.B. beim Mergesort [https://de.wikipedia.org/wiki/Mergesort] kann man wunderbar das Teilen und Mischen einzeln im Speicher abarbeiten. Die Zwischenergebnisse die man gerade nicht braucht schiebt man dann temporär auf Platte und hält sich somit seinen Speicher frei. Unterstützung vom Framework bekommst du dafür aber nicht. Mußt du schon selbst implementieren oder jemanden finden der ähnliches bereits gemacht hat.

haschme - Fr 16.10.15 10:22

Hallo nochmal,

ich habe jetzt mal den cmsort ausprobiert.
Das ist ein echt schönes tool mit vielen nützlichen Funktionen, vielen Dank für den Tipp!

Weis jemand ob man eine Einstellmöglichkeit bei dem cmsort tool hat um Daten zurück zu bekommen,
um Beispielsweise einen Fortschrittsbalken zu erstellen?

Ich würde dem Nutzer gerne zumindest zeigen können was das Tool gerade macht oder wie lange es noch dauert.

Habe mir die Doku durchgelesen aber leider nichts dazu gefunden.

Ich habe cmsort mal über die Datei mit den 11 Millionen Datensätzen laufen lassen. Leider scheint cmsort nicht für so große Dateien geeignet zu sein.
Es sortiert mittlerweile über eine Stunde und ist noch nicht fertig. (Die Datei ist über 5 GB groß)

Vielen Dank!

Horst_H - Fr 16.10.15 14:06

Hallo,

ein kurzer Blick auf http://www.chmaas.handshake.de/delphi/freeware/cmsort/cmsort.htm#review zeigt doch, um welche zeitlichen Dimensionen es geht.
Die Daten: 16 MIo Zeilen mit insgesamt 3 GB.
Der User hat 2014 ein anderes Programm nach 8x24h = 192 h abgebrochen, als zu etwa 70% fertig war.

Du hast 550 Zeichen x 11Mio Zeilen =6.05 Gb.
erstelle doch eine Zeitreihe mit Dateien unterschiedlicher Größe.
500.000, 1 Mio, 2 Mio, 4 Mio....
Man kann ja dann die Größe und Anzahl temporären Datein anschauen.
Sobald temporäre Dateien entstehen müsste es erheblich langsamer werden.
Mit kleinen Dateien kann man die Sortiergeschwindigkeit an sich testen.Indem man zweimal hintereinander die selbe Datei sortiert

Gruß Horst

haschme - Mi 21.10.15 14:48

Hallo,

also CMsort funktioniert auf jedenfall schonmal recht gut.

Ist CMsort das beste externe Tool zur Sortierung bzw zur Sortierung mehrerer Spalten?

Des Weiteren ist mir aufgefallen, je mehr Speicher ich CMsort zur Verfügung stelle desto schneller arbeitet das Tool.
Gibt es da einen Richtwert wie groß der Speicher den das Tool in etwa benutzen darf sein sollte?

Gibt es noch andere Schrauben als den Speicher an denen man drehen kann um das ganze zu beschleunigen?

Dies sind meine gemessenen Werte bei einer Datei mit 1 Million Zeilen:

.
......1 mio mit 16.384 KB = 4:19 min
.
......1 mio mit 262.144 KB = 2:12 min
.
......1 mio mit 1.048.576 KB = 1:09 min
.
für eine Datei mit 8.516.859 Zeilen (Sortiert habe ich nur von Start 1 Länge 5) brauchte CMsort
mit zur Verfügung gestellten 524.288 KB : 29:37 min

Horst_H - Fr 23.10.15 22:13

Hallo,

ich habe mal 11MioZeilen Zufallsbuchstaben a 550 Zeichen sortieren lassen Spalte 1..500, mit zugewiesenen 2Gbyte RAM unter Linux32/wine.
24 min geht doch.
Beim mergen der Dateien fiel mir noch auf, das nur 113 MB statt 1968 Mb, wie während des sortierens der Einzelabschnitte, belegt werden.
Da hätte ich erwartet, dass von den 5 Dateien jeweils 400 Mb eingelesen werden und dann wieder weggeschrieben wird.
Bei einer SSD wäre es egal.
Probe05

Gruß Horst

haschme - Mi 28.10.15 10:58

probe.txt war deine Eingangsdatei und test.txt deine Ausgabedatei richtig?

Wenn ja, verstehe ich nicht weshalb die Dateien am Ende unterschiedlich groß sind.
Im Prinzip wird ja nur die Reihenfolge verändert aber nicht die Menge des Inhalts.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!