Sortieren im Stream

Sarkast schrieb:

Ah, Mergesort scheint mir das passende Stichwort zu sein, Danke!

@hustbaer: Nee, bei 1 GB RAM würde ich schon in Euphorie verfallen. Die HW ist so ein Linux- Riegel, bei dem ich froh sein kann, so um die 200 MB zu bekommen.

Aaalso, wenn ich keinen großen Denkfehler habe, zersäge ich die unsortierte Datei in Chunks, die ich im Speicher halten und sortieren kann und kriege dann soundsoviel sortierte Teildateien.
Die kann ich dann aber auch quasi "in einem Rutsch" mergen oder überseh' ich da was?

OK, zumindest bin ich jetzt nicht planlos.

Wenn du die Daten im Speicher halten willst, dann wird es beim letzten Merge definitiv nicht mehr ins Ram passen.

So wie ich das verstehe, musst du zumindest zum Schluss alles auf Dateisystemebene machen. Und das unter der Voraussetzung, du passt den Algorithmus derart an, dass bei kleinen Dateien das Zeugs im RAM gemerged wird.

D.h. der letzte Merge besteht aus jeweils zwei riesigen, aber für sich sortierten Dateien und die musst du wieder zusammenführen.

Du kannst ja mal auf einem Blatt Papier die Folge 9, 7, 8, 6, 5, 3, 4, 2, 1 mit Mergesort sortieren, unter der Annahme, dass jede Ziffer 1 Byte groß ist und du aber nur 4 Bytes RAM zur Verfügung hast, dann sollte das Problem schon offensichtlich werden.

Sarkast

computertrolls schrieb:

Wenn du die Daten im Speicher halten willst, dann wird es beim letzten Merge definitiv nicht mehr ins Ram passen.

So wie ich das verstehe, musst du zumindest zum Schluss alles auf Dateisystemebene machen. Und das unter der Voraussetzung, du passt den Algorithmus derart an, dass bei kleinen Dateien das Zeugs im RAM gemerged wird.

D.h. der letzte Merge besteht aus jeweils zwei riesigen, aber für sich sortierten Dateien und die musst du wieder zusammenführen.

Du kannst ja mal auf einem Blatt Papier die Folge 9, 7, 8, 6, 5, 3, 4, 2, 1 mit Mergesort sortieren, unter der Annahme, dass jede Ziffer 1 Byte groß ist und du aber nur 4 Bytes RAM zur Verfügung hast, dann sollte das Problem schon offensichtlich werden.

Hmm, aber doch nicht, wenn ich das File elementweise vergleiche. Ich denke mir das so:

9,1,8,2,7,3,6,4,5,0,1,2,3,4,5,5,6,7,8,9     // erstmal in zwei Dateien splitten, RAM- gerechte chunks
  => 9,1,8,2,7,3,6,4,5,0 | 1,2,3,4,5,5,6,7,8,9   // und sortieren
  => 9,8,7,6,5,4,3,2,1,0 | 9,8,7,6,5,5,4,3,2,1
  => Datei Links           Datei Rechts

Jetzt muß ich die Dateien nur noch elementweise Links mit Rechts vergleichen und das jeweils größere in den Outstream schreiben und das nächste Element aus demjenigen Stream lesen, wo ich das herhatte.

=> nach Herkunft gekennzeichneter Outstream
  => L9,R9,L8,R8,L7,R7,L6,R6,L5,R5,R5,L4,R4 ... L1,R1,L0

Müßte doch so funktionieren oder überseh' ich da was grob?

hustbaer

computertrolls schrieb:

Du kannst ja mal auf einem Blatt Papier die Folge 9, 7, 8, 6, 5, 3, 4, 2, 1 mit Mergesort sortieren, unter der Annahme, dass jede Ziffer 1 Byte groß ist und du aber nur 4 Bytes RAM zur Verfügung hast, dann sollte das Problem schon offensichtlich werden.

Es gibt kein Problem.
Mergen von zwei Blöcken ist ne Stream Operation.
Man liest ein Byte vom linken Stream (File) und eins vom rechten Stream (File). Das kleinere schreibt man raus und liest an der Stelle wieder eins nach. Und schreibt wieder das kleinere raus (auch wieder in ein File). So lange bis einer der beiden Inputs leer ist, dann kopiert man einfach den rest vom anderen Input und dann ist man fertig.
Tadaa.

hustbaer

Sarkast schrieb:

@hustbaer: Nee, bei 1 GB RAM würde ich schon in Euphorie verfallen. Die HW ist so ein Linux- Riegel, bei dem ich froh sein kann, so um die 200 MB zu bekommen.

Naja dann nimmst du einfach 64 MB oder sowas als initiale Chunk-Grösse

Sarkast schrieb:

Aaalso, wenn ich keinen großen Denkfehler habe, zersäge ich die unsortierte Datei in Chunks, die ich im Speicher halten und sortieren kann und kriege dann soundsoviel sortierte Teildateien.

Ja.

Sarkast schrieb:

Die kann ich dann aber auch quasi "in einem Rutsch" mergen oder überseh' ich da was?

Grundsätzlich ja.
Wenn du allerdings so viele Chunks hast dass du pro Chunk nur einen klitzekleinen Input-Puffer verwenden kannst, dann wird es langsam*. Kommt auf die Hardware an, aber so grob 1 MB** war bei mir immer ein guter Wert.

Du willst also nicht Byte für Byte lesen, nichtmal Sektor für Sektor. Du willst eben ~~ 1MB am Stück aus dem File in einen Puffer lesen. Und erst wenn der Puffer leer ist liest du wieder 1 MB.

Wenn das bedeutet dass du auf z.B. 64 gleichzeitige Input-Streams limitiert bist, dann ist das eben so. Wenn du dann mehr als 64 Files hast musst du halt erstmal je 64 von den Files in je ein grosses mergen, und danach mit den grossen Files einen 2. Durchgang machen. Bzw. wenn auch die grossen Files immer noch zu viel sind einen 3. Durchgang. Usw.

Da sich die Anzahl der Files in jedem Durchgang auf 1/64 reduziert wird die Anzahl der Durchgänge aber auf jeden Fall nicht sehr gross sein.

*: Lesen mit so kleinen Input-Puffern ist nur schnell wenn das OS preventiv mehr Daten als angefordert wurden in den Cache liest. Wenn du aber zu viele Files aufmachst und zu wenig RAM hast, und "random" mal aus diesem mal aus jedem File ein paar kB liest, dann kann das mit dem File-Cache natürlich auch nicht mehr gut funktionieren. Das OS kann schliesslich auch kein RAM herzaubern wo keines ist.

**: Wenn das Speichermedium Flash ist (SSD, Speicherkarte, ...), bzw. allgemein eines das keine "Seek-Zeiten" hat, dann kann es sein dass deutlich kleinere Puffer für gute Performance reichen. Es kommt einfach auf das Verhältnis der "Fixkosten" einer "Seek+Read" Operation zur linearen Lesegeschwindigkeit an. Einfach verschiedene Grössen durchprobieren.

ps: Es kann auch sein dass es beim Schreiben was bringt selbst zu puffern und grössere Blöcke am Stück zu schreiben. Kommt aufs System an. Wenn das System es all zu eilig hat alles was es zum Schreiben übergeben bekommt sofort auf den Datenträger zu schreiben, dann kann dir das die nächste Leseoperation verzögern. Und da du nur einen Output hast kannst du dir da auf jeden Fall nen halbwegs grossen Puffer leisten.

Sarkast

hustbaer schrieb:

*: Lesen mit so kleinen Input-Puffern ist nur schnell wenn das OS preventiv mehr Daten als angefordert wurden in den Cache liest. Wenn du aber zu viele Files aufmachst und zu wenig RAM hast, und "random" mal aus diesem mal aus jedem File ein paar kB liest, dann kann das mit dem File-Cache natürlich auch nicht mehr gut funktionieren. Das OS kann schliesslich auch kein RAM herzaubern wo keines ist.

**: Wenn das Speichermedium Flash ist (SSD, Speicherkarte, ...), bzw. allgemein eines das keine "Seek-Zeiten" hat, dann kann es sein dass deutlich kleinere Puffer für gute Performance reichen. Es kommt einfach auf das Verhältnis der "Fixkosten" einer "Seek+Read" Operation zur linearen Lesegeschwindigkeit an. Einfach verschiedene Grössen durchprobieren.

Jau, ich bin jetzt eh an der schlichtesten Lösung dran und die basiert nunmal auf möglichst sequentiellem Lesen und Schreiben. Komplizierter kann ich's später auch noch machen.
Tatsächlich scheinen Filehandles nicht besonders ressourcenschonend zu sein und das delayed write buffering fordert auch seinen Tribut, sieht man an den Timestamps der Meßwerte ganz gut.
Mal schauen, wie's aussieht, wenn ich die ersten Vollmessungen durch habe und erstmal bei konservativen Buffergrößen bleibe.

Sarkast schrieb:

Hmm, aber doch nicht, wenn ich das File elementweise vergleiche.

Richtig, aber du wolltest es ja im RAM halten und das geht spätestens beim letzten Merge nicht mehr:

Sarkast schrieb:

zersäge ich die unsortierte Datei in Chunks, die ich im Speicher halten und sortieren kann

Jetzt muß ich die Dateien nur noch elementweise Links mit Rechts vergleichen und das jeweils größere in den Outstream schreiben und das nächste Element aus demjenigen Stream lesen, wo ich das herhatte.

Exakt, also nichts mit alles im RAM halten.

hustbaer schrieb:

Es gibt kein Problem.

Da er es im RAM halten wollte, siehe oben, schon.

Mergen von zwei Blöcken ist ne Stream Operation.

So sollte man es auch machen, aber alles ins RAM geht halt nicht.

Sarkast

computertrolls schrieb:

Mergen von zwei Blöcken ist ne Stream Operation.

So sollte man es auch machen, aber alles ins RAM geht halt nicht.

Naja, das war ja genau der Ausgangspunkt meiner Frage. Mir hat das Stichwort Mergesort gefehlt, weil mir dadurch erst klar geworden ist, wie mir sortierte Teillisten (für die das RAM ja reicht) helfen.

Sarkast schrieb:

Komplizierter kann ich's später auch noch machen.

Falls du das machst, dann schau dir noch einmal meinen ersten Vorschlag an.
Da kannst du dann gleich auf mehreren Kernen unabhängig voneinander große und dann voneinander unabhängige Datenmengen im RAM sortieren.

Es ist allerdings richtig, was hustbear gesagt hat. Da könntest du dir etwas einfallen lassen und bspw. die Buckets noch einmal aufteilen:

[quoote="hustbear"]
Hat im Vergleich zum Vorschlag von computertrolls den Vorteil dass es nicht auf Kenntnis des Wertebereichs des Sort-Keys angewiesen ist und man keine Probleme mit "Buckets" bekommen kann die dann doch wieder zu gross werden.
[/quote]

hustbaer

Parallelisieren lässt sich der Mergesort ebenfalls.
Und CPU-Zeit wir hier eh nicht das Problem sein.

Bucketsort als Lösung für Datenmengen die man nicht mehr gesamt in den Speicher bekommt ist echt Betteln um Probleme.

hustbaer schrieb:

Parallelisieren lässt sich der Mergesort ebenfalls.

Du kannst zwar die Zwischenschritte parallelisieren, aber wie parallelisierst du den letzten Merge?

Und CPU-Zeit wir hier eh nicht das Problem sein.

Das Problem sind die I/O Operationen zur SSD/HD, deswegen macht es meiner Meinung nach Sinn sich einen Algorithmus zu suchen, der möglichst auf dem RAM arbeiten kann.
Mit Bucketsort geht das.
Dazu kann man das ganze noch sehr schön parallelisieren, es gibt da praktisch keine nennenswerten Konflikte.

Und ich denke schon, dass das etwas bringt, weil Vergleiche auch Geld kosten und ein Single Core ansonsten alle n Vergleiche selber durchführen muss. Eine Rechenlast, die man gut auf mehrere Kerne verteilen kann, wenn sich der Algorithmus dafür eignet.
Inwiefern und ob die I/O Operationen auf das RAM die Kerne limitieren, das müsste man einfach mal ausprobieren. Oder meinst du, die limitieren einen Kern so stark, dass selbst ein einziger Kern genügen würde?

Bucketsort als Lösung für Datenmengen die man nicht mehr gesamt in den Speicher bekommt ist echt Betteln um Probleme.

Findest du?
Warum?

Sarkast

Bitte nicht jetzt schon streiten, bin gerade erst dabei, den ersten Merge von zwei vorsortierten Teillisten fertig zu implementieren.
Wenn der erste Wurf "good enough" ist, werde ich da nicht weiter herummurksen, weil ich dafür nichtmal ein Schulterklopfen erwarten darf. Bin eigentlich ziemlich fachfremd und kein Informatiker und komme zu solchen Dingen nur, weil mich mal jemand mit den Worten: "Heh, du kannst doch programmieren, oder?" angehauen hat, seitdem landet sowas bei mir.
Und Feierabend hab ich eigentlich seit halb fünf, aber es interessiert mich nunmal.

hustbaer

computertrolls schrieb:

hustbaer schrieb:

Parallelisieren lässt sich der Mergesort ebenfalls.

Du kannst zwar die Zwischenschritte parallelisieren, aber wie parallelisierst du den letzten Merge?

Gar nicht - zumindest nicht sinnvoll. Dass das nicht unendlich skaliert ist klar. Aber es sollte gut genug für die meisten Anwendungen skalieren.

computertrolls schrieb:

Und CPU-Zeit wir hier eh nicht das Problem sein.

Das Problem sind die I/O Operationen zur SSD/HD, deswegen macht es meiner Meinung nach Sinn sich einen Algorithmus zu suchen, der möglichst auf dem RAM arbeiten kann.
Mit Bucketsort geht das.

Mit Merge-Sort geht das genau so
Ich würde sagen sogar noch viel besser, da du dir die Chunk Grössen aussuchen kannst, und nicht auf die Verteilung der Keys angewiesen bist.

computertrolls schrieb:

Dazu kann man das ganze noch sehr schön parallelisieren, es gibt da praktisch keine nennenswerten Konflikte.

Den Pass der über das Input-File drüberackert und es in Buckets aufteilt zu parallelisieren ist nicht einfach. Und genau so wie Vergleichen nicht gratis ist, ist es auch nicht gratis die Items anhand einer "Stelle" des Keys in Buckets aufzuteilen.

computertrolls schrieb:

Und ich denke schon, dass das etwas bringt, weil Vergleiche auch Geld kosten und ein Single Core ansonsten alle n Vergleiche selber durchführen muss. Eine Rechenlast, die man gut auf mehrere Kerne verteilen kann, wenn sich der Algorithmus dafür eignet.

Der letzte Merge muss single-threaded laufen, also N Vergleiche. Aber nicht N log N vergleiche. Die log N - 1 passes vor dem letzten Pass können parallel laufen.

computertrolls schrieb:

Inwiefern und ob die I/O Operationen auf das RAM die Kerne limitieren, das müsste man einfach mal ausprobieren. Oder meinst du, die limitieren einen Kern so stark, dass selbst ein einziger Kern genügen würde?

Das kommt auf viele Faktoren an. Wie gross die Items sind, wie kompliziert der Key zu vergleichen ist, wie schnell das Mass-Storage-Device ist...

computertrolls schrieb:

Bucketsort als Lösung für Datenmengen die man nicht mehr gesamt in den Speicher bekommt ist echt Betteln um Probleme.

Findest du?
Warum?

Weil es schwer so zu implementieren ist dass es keine Fälle gibt wo es einem um die Ohren fliegt. Was machst du wenn du zu viele Keys hast die in den selben Bucket gehören? Dann musst du diesen Bucket dynamisch weiter unterteilen. Kompliziert. Dabei aber aufpassen dass man insgesamt nicht in zu viele Buckets unterteilt, weil einen sonst das Erzeugen/Schreiben/Lesen von zig- oder hunderttausenden Bucket-Files umbringt. Noch komplizierter.

Ich mag generell Algorithmen nicht deren "Eigenschaften" stark von den Input-Daten abhängig sind. Hier also wie gross die Chunks werden bzw. wie viele Chunks es gibt abhängig davon wie die Keys verteilt sind. Dabei ist es viel zu einfach irgendwas zu übersehen wo dann doch wieder irgendwelche Probleme entstehen.

hustbaer

Sarkast schrieb:

Bitte nicht jetzt schon streiten,

Wir diskutieren doch bloss.

Sarkast schrieb:

bin gerade erst dabei, den ersten Merge von zwei vorsortierten Teillisten fertig zu implementieren.
Wenn der erste Wurf "good enough" ist, werde ich da nicht weiter herummurksen

Verlangt auch keiner von dir. Mach das was für dich Sinn macht!

Das passiert hier oft dass jemand ne Frage stellt, und dann weiterdiskutiert wird obwohl die Frage schon beantwortet wurde, einfach weil die anderen Forenteilnehmer Spass daran haben sozusagen.

hustbaer schrieb:

computertrolls schrieb:

Dazu kann man das ganze noch sehr schön parallelisieren, es gibt da praktisch keine nennenswerten Konflikte.

Den Pass der über das Input-File drüberackert und es in Buckets aufteilt zu parallelisieren ist nicht einfach. Und genau so wie Vergleichen nicht gratis ist, ist es auch nicht gratis die Items anhand einer "Stelle" des Keys in Buckets aufzuteilen.

Ein Thread liest den Datenstrom von Anfang bis Ende und macht daraus Teilstücke, die es im RAM in jeweils ein Arrays legt.
Sobald ein Array voll ist, wird es gleich an einen eigenen Thread abhängig von der Core-Anzahl (oder sofern Hyperthreading hier Sinn macht, auch abhängig davon) zur Weiterbearbeitung weitergegeben.

Jeder einzelne Thread der ein Array zum Bearbeiten erhalten hat kriegt ein paar echte Buckets zugewiesen und gilt als Besitzer dieser Buckets, welcher er dann, auch direkt auf die Platte schreiben darf (natürlich unter der Berücksichtigung, dass man dabei den ersten Thread nicht stört), diejenigen Buckets die schon zugewiesen wurden dürfen von anderen Threads nicht benutzt werden.
Dafür nutzen die anderen Threads dann für diese Art von Bucket einen Zwischenpuffer im RAM.

Der Zwischenpuffer wird dann nach und nach an den Besitzerthread weitergereicht und der Thread der den Zwischenpuffer hatte, legt einen neuen Zwischenpuffer im RAM an, so ist er immer ausgelastet.
Der Besitzerthread schreibt den Puffer dann auf die Platte.

Eventuell kann es Sinn machen, die ganze Aufgabe mit dem Besitzerthread der ja die schreibende Arbeit übernimmt, auch einfach dem ersten Thread, der sich sowie um das Einlesen kümmert, also die HD belegt, zu übergeben. In dem Fall arbeiten die anderen nur auf dem RAM mit ihren Zwischenpuffern. Das hat den Vorteil, dass es bei einer HD keine unnötigen Zeitverlust bezüglich der Seekzeit gibt.

Wenn die Daten dann alle in ihrem jeweiligen Bucket gelandet sind, dann kann man diese dann an die jeweiligen Threads fair und gleichmäßig nach der Bucketgröße nach und nach aufteilen.
Die Threads arbeiten dann ihren Bucket einzeln ab und sortieren ihn, wenn alles ins RAM passt, mit schnelleren Sortierverfahren wie bspw. Quicksort. Wenn sie damit fertig sind, kriegen sie den nächsten freien Bucket.

Wenn ein Bucket schon zu groß ist, könnte man für den dann immer noch Mergesort verwenden oder ihn einfach noch einmal in zwei Subbuckets aufteilen.

Sofern nötig, fügt man dann am Schluss alle sortierten Buckets aneinander.

Weil es schwer so zu implementieren ist dass es keine Fälle gibt wo es einem um die Ohren fliegt. Was machst du wenn du zu viele Keys hast die in den selben Bucket gehören? Dann musst du diesen Bucket dynamisch weiter unterteilen. Kompliziert. Dabei aber aufpassen dass man insgesamt nicht in zu viele Buckets unterteilt, weil einen sonst das Erzeugen/Schreiben/Lesen von zig- oder hunderttausenden Bucket-Files umbringt. Noch komplizierter.

Ich mag generell Algorithmen nicht deren "Eigenschaften" stark von den Input-Daten abhängig sind. Hier also wie gross die Chunks werden bzw. wie viele Chunks es gibt abhängig davon wie die Keys verteilt sind. Dabei ist es viel zu einfach irgendwas zu übersehen wo dann doch wieder irgendwelche Probleme entstehen.

Ja, die Komplexität ist höher, mit ihr auch die Fehleranfälligkeit, aber es kann auch performanter sein.
Denn Zeitaufwand für den letzten Merge bei Mergesort würde ich nämlich recht hoch einschätzen.

hustbaer

Ja, ich verstehe schon wie man es machen kann. Ich sage bloss dass es nicht einfach ist. Implementier einfach mal beide Varianten, dann siehst du vermutlich warum ich Merge-Sort besser finde.

computertrolls schrieb:

Denn Zeitaufwand für den letzten Merge bei Mergesort würde ich nämlich recht hoch einschätzen.

Und ich relativ gering. Und nu?

rapso

Sarkast schrieb:

Ich logge Messergebnisse,sehr viele (ein paar GB pro Aufzeichnung) und die passen folglich nicht auf einmal in den Speicher, landen also in einem File, das ich hinterher vollständig sortieren muß.

wirklich interesant fuer eine gute loesung waere zu wissen was fuer datensaetze du eigentlich hast.
wie gross ist ein eintrag?
welche art von daten sind enthalten? (strings? floats?)

hustbaer

Grundsätzlich hast du natürlich Recht dass Fragen nach ein paar Details meistens Sinn macht. Ich überlege mir aber gerade was es in diesem Fall für einen Unterschied machen könnte. Klar, wenn der Sort-Key klein genug ist könnte man die Keys direkt im RAM sortieren. Dann bleibt aber das Problem dass man die eigentlichen Daten noch in die korrekte Reihenfolge bringen muss, d.h. tonnenweise random Reads und das bremst auch gewaltig. Sonst fällt mir mal nix ein was hier wesentlich sein könnte.

Oder denkst du an was ganz anderes?

Sarkast

rapso schrieb:

wirklich interesant fuer eine gute loesung waere zu wissen was fuer datensaetze du eigentlich hast. wie gross ist ein eintrag?
welche art von daten sind enthalten?

Hergeleitet wird das Ganze natürlich aus digitaler Sensorik, davon bleibt aber nur die Timestamp als uint32 unberührt. Aus der Zwischenergebnisrechnung fallen dann pro Kanal zwo doubles plus stamp als set an, also 20 Bytes, davon gut 30'000 pro Meßsekunde, der typische Meßverlauf braucht so grob 6 bis 8 Minuten. Kann sein, daß ich da nochmal ein int32 dauerhaft ins set nehmen muß, ich brauch's sowieso grad zum Debuggen.

Drei bis sieben Kanäle soll die Schachtel bewältigen können.
Achso, ja, sortiert werden soll auf einen der Doubles im set. Ja, ich weiß, doubles sind unschön, aber momentan kann/will mir keiner was über die Skalierung der Meßwertaufnehmer erzählen.

Inwiefern hilft dir das?

rapso

@hustbaer @Sarkast
Grundsaetzlich ist die chance etwas zu optimieren besser wenn man mehr darueber weiss. Einfach nur "paar GB daten" ist wirklich nicht viel.
1Billion ints zu sortieren ist anders als 1Mio 1kb datensaetze. (Und datensaetze kosteneffektiv in eine vorgegebene reihenfolge zu bringen ist eine andere problemstellung. Ich glaube hier gab es sogar mal einen kleinen contest dafuer. )

Zum eigentlichen:
Sind also maximal 20byte*30'000*(8*60)*7 -> 1.87GB, das koenntest du vielleicht mit memory mapped files auf einer 32bit cpu, trotz nur 200MB freien ram, mappen. Das OS hat ein paar vorteile z.b. beim file caching, thread scheduling etc. wenn das klappt. (Dann koenntest du auch, um eine referenz zu haben, ein std sort messen).

Ich denke ich wuerde beim eigentlichen sortieren, erstmal radix sort versuchen, weil es linear durch die datei durchgeht und, sobald der datensatz ins ram passt, nur noch darauf arbeitet.

Wenn du fit bist im coden, wuerde auch nichts gegen bucketsort sprechen, zumindestens fuer den ersten durchgang. (Haengt aber auch vom wertebereich der doubles ab)

ansonsten, stell doch einen generator fuer pseudo daten rein, vielleicht hat jemand langeweile und probiert sich dran.

FILE* f=fopen("data","wb");
if(!f)
  return;
for(size_t a=0;a<30000*(60*8)*7;a++)
{
  int stamp=a;
  double x=sin((double)a);
  double y=cos((double)a);
  fwrite(&stamp,1,sizeof(stamp),f);
  fwrite(&x,1,sizeof(x),f);
  fwrite(&y,1,sizeof(y),f);
}
fclose(f);

nicht schoen, nicht schnell, aber du kannst es ja anpassen damit es representabel fuer deine datensaetze ist.

Ja, ich weiß, doubles sind unschön, aber momentan kann/will mir keiner was über die Skalierung der Meßwertaufnehmer erzählen.

Vielleicht kann dir hier im forum auch jemand dazu helfen

SideWinder

Out-of-the-box gedacht: ist es evtl. die günstigere Option 16 GB RAM zu kaufenu und das ganze via QuickSort zu sortieren?

MfG SideWinder