Sortieren im Stream

[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

[Jester]

http://stxxl.org

und merge sort sinnvoll parallelisieren geht mit multi-way merging

[hustbaer]

Jester schrieb:

und merge sort sinnvoll parallelisieren geht mit multi-way merging

Geht das auch ohne Random-Access in die Teil-Listen? Der Algorithmus den ich kenne benötigt Random-Access auf Inputs und den Output und ist daher IMO für das Mergen von vielen Files die nicht zusammen in den Speicher passen nicht ideal. Kann OK sein wenn random IO schnell genug ist, aber wenn nicht dann wird die Sache dadurch vermutlich eher langsamer als schneller.

Also verglichen mit Algorithmen die mit "forward only" IO auskommen und dafür den letzten 2-way Merge in O(N) machen. Das Schreiben des Ergebnisses auf den Datenträger ist schliesslich immer O(N), und so lange man mit dem letzten Merge die Konstante nicht zu sehr nach oben treibt...

[Sarkast]

SideWinder schrieb:

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

Du bist lustig, ich soll also 16 GB RAM- Riegel neben den Linux- Riegel streuen und hoffen, daß die sich ineinander verlieben und heiraten?
Nee, da sind 512 MB fest aufgelötet, das müssen sich OS und Applikation teilen.

rapso schrieb:

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. )

Achso, ja klar! Kleine Pakete, dafür viele.

rapso schrieb:

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).

Da liegen die Hasen im Pfeffer. Schreiben tu' ich erstmal am PC, bevor ich das zum Schluß portiere. Die Erfahrungen auf dem Target- OS/FS mit caching nebst delayed wb auf das Flashdrive waren nicht sehr ermutigend, random access eine performance- Katastrophe. Das war ja auch der Ausgangspunkt, selber bestimmen zu können, was mit dem Speicher passiert, also wer ihn kriegt.
Das enthebt mich auch der Herumspielereien an den Einstellungen fürs Caching usw., weil, was am PC gut läuft, auf dem Riegel nicht zwangsweise auch gut laufen muß.

rapso schrieb:

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)

Hab der Einfachheit halber quicksort fürs Sortieren im RAM genommen, das einzig Ungünstige ist, daß es im Schnitt n * log(n), schlimmstenfalls n² Vergleiche braucht. Aber schaut momentan nach ausreichender Zügigkeit aus. Da könnte man vllt. später über mehrere Threads nachdenken.

rapso schrieb:

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

Das war das erste, was ich gemacht hab, die Meßwertaufnahme durch einen Dummy- Generator ersetzt.
Das mit der Skalierung ist noch nicht klar, weil es die Meßwertaufnehmer für 3 € , 300 € oder ca. 1000 € (pro Kanal) gibt, aber dann mit 1, 1000, 18000- facher Auflösung. Ähnlich verhält es sich mit der Zeitbasis. Ich kann nur sagen, was ich wünsche, was die kaufen ist oft was anderes.

So, die vorsortierten Listen kann ich dann wirklich rein sequentiell lesend/schreibend zusammenmergen, da müssen wirklich nur zwei Elemente in den Speicher (2 Instream, 1 Outstream). Das geht auch überraschend flott, ich hab' hier "nur" das Problem, daß sich mein Progrämmchen noch verkaspert, welche Dateien gerade zusammenzuziehen sind. Es "vergißt" entweder eine Datei oder versucht, Dateien zu öffnen, die es nicht gibt. Aber das hat mit Sortieren direkt erstmal nichts zu tun.

[Jester]

Du solltest Dir ünerlegen mehr als zwei streams auf einmal zu mergen. Jedes mergen erfordert einmal das vollständige lesen und schreiben aller Daten. Also warum das zweimal oder noch öfter machen, wenn man mit geringem Mehraufwand (CPU) den Datendurchsatz (I/O) senken kann.

[Sarkast]

Jester schrieb:

Du solltest Dir ünerlegen mehr als zwei streams auf einmal zu mergen. Jedes mergen erfordert einmal das vollständige lesen und schreiben aller Daten. Also warum das zweimal oder noch öfter machen, wenn man mit geringem Mehraufwand (CPU) den Datendurchsatz (I/O) senken kann.

Mei, damit hast du mir was angetan, allgemein n streams zu mergen ist schon was anderes als immer nur 2, aber ich nehms halt sportlich, weil mein Ehrgeiz geweckt wurde.
Zumindest schaut es aber so aus, als ob sich das rentieren könnte, würde es durchlaufen. Da bin ich noch dran und wünsch mir wenigstens österlich dicke Eier.

[Jester_logoff]

Wo ist das Problem? Du willst k streams mergen, dann lädst Du Daten in Blöcke Blöcke B[1] bis B[k]. Außerdem brauchst Du k zaehler C[1],...,C[k], initial alle 0.

Dann erstellst Du eine Priority Queue Q, in die Du die Nummern 1 bis k einfügst (nämlich aus welchem stream das nächste Element kommt) und zwar i mit Priorität B[C[i]].

Jetzt musst Du einfach nur immer wieder das Element mit der höchsten (niedrigsten Priorität) aus der Queue entnehmen, dann weißt Du wo das nächste Element herkommen muss; angenommen i kommt raus -> nächstes Element im Ausgabeblock ist B[i][C[i]], danach C[i] erhöhen. Wenn der Block B[i] leer läuft muss nachgefüllt werden. Am besten Du hältst immer zwei Blöcke pro Stream vor und hängst wenn einer leer ist den zweiten um und lädst dann direkt wieder nach.

[hustbaer]

Ja, man kann das mit einer Priority-Queue machen wenn man unbedingt will. Würde ich nicht wollen. Viel zu kompliziert.

Oder man kann einen binären Baum aus 2-way Stream-Merge Operatoren aufbauen. Würde ich wollen. Viel weniger kompliziert.

[Jester]

Das ist imo schwieriger zu implementieren, weil man eben nicht mit fertigen Datenstrukturen auskommt und mehr händisch machen muss. Kann man natürlich machen. Würde ich nicht wollen. Zum Glückmuss ich weder noch.

[Sarkast]

hustbaer schrieb:

Ja, man kann das mit einer Priority-Queue machen wenn man unbedingt will. Würde ich nicht wollen. Viel zu kompliziert.

Oder man kann einen binären Baum aus 2-way Stream-Merge Operatoren aufbauen. Würde ich wollen. Viel weniger kompliziert.

Das mit Priority hab ich erstmal eh nicht verstanden, außerdem war ich da schon so weit, daß ich nicht alles wegwerfe.
Um Ostern nochmal aufleben zu lassen, ich mache n Eierrutschen auf, von denen nur bekannt ist, daß pro Pipe eine stetige Sortierung (auf- oder absteigend dank quicksort) vorliegt. Da gucke ich mir das an, was in den Rutschen liegt, nehme das kleinste (oder größte) Ei raus, und stopfe es in die Ausgangs- Rinne, bis nichts mehr aus den n Rinnen nachrutscht.
Wenn ich keine sortierten Körbe mehr habe, die ich in die Rinnen kippen kann, geht es eine Ebene höher.

Tut flotter, als immer nur 2 Dateien zu mergen, aber die Rekursion, die ich dazu gebastelt hab, fällt gelegentlich auf die Nase. Da muß ich halt durch, dazu muß mir aber auch keiner die Hand halten. Schätze eure Begeisterung, >100 loc auf bugs zu filzen so hoch wie meine, irgendwo <0.

Eher lieber Tips, wie ich den Datenmüll hinterher entsorge, der sich dabei unweigerlich ergibt. Also den Hinweis, wie ich ein shell- script (bash unter *ix bzw. command/powershell unter win) lostreten kann. Oder den Hinweis, wo ich die Frage am besten poste.

[computertrolls]

Sarkast schrieb:

Schätze eure Begeisterung, >100 loc auf bugs zu filzen so hoch wie meine, irgendwo <0.

Bau dir einen Unit Test.

Bau dir ein Array, dessen Elemente du einfach durchnummerierst.
Anschließend nimmst du einen Zufallsgenerator und nimmst dir damit die Elemente zufällig aus dem Array und speicherst sie unsortiert in ein anderes ab, im sortierten Array markierst du sie als entnommen.
Mit dem nun unsortierten Array hast du nun Testdaten für den Unittest.
Die richtige Reihenfolge, die raus kommen muss, kennst du, damit sollte der Unittest funktionieren.

Wenn's noch etwas besser werden soll, sorgst du noch für doppelte Einträge, denn die dürften beim Messen auch vorkommen, sofern ein Zeitstempel nicht extra für Einzigartigkeit sorgt.

Eher lieber Tips, wie ich den Datenmüll hinterher entsorge, der sich dabei unweigerlich ergibt. Also den Hinweis, wie ich ein shell- script (bash unter *ix bzw. command/powershell unter win) lostreten kann. Oder den Hinweis, wo ich die Frage am besten poste.

Ich verstehe die Frage nicht.
Wenn du Daten im Dateisystem löschen musst, dann gibt's dafür rm, /dev/null und Co.

[Sarkast]

computertrolls schrieb:

Bau dir ein Array, dessen Elemente du einfach durchnummerierst.
Anschließend nimmst du einen Zufallsgenerator und nimmst dir damit die Elemente zufällig aus dem Array und speicherst sie unsortiert in ein anderes ab, im sortierten Array markierst du sie als entnommen.
Mit dem nun unsortierten Array hast du nun Testdaten für den Unittest.
Die richtige Reihenfolge, die raus kommen muss, kennst du, damit sollte der Unittest funktionieren.

Wenn's noch etwas besser werden soll, sorgst du noch für doppelte Einträge, denn die dürften beim Messen auch vorkommen, sofern ein Zeitstempel nicht extra für Einzigartigkeit sorgt.

Schon, es wären dennoch ein paar Zeilen und doofe Indexfehler finde ich dann doch selber, da muß ich keinen von euch belästigen.
Übrigens, natürlich sind die Datensätze "unique", weil es ja darauf ankommt, alle Meßkanäle genau zur gleichen Zeit abzunehmen, folglich alle mit Zeitstempel/Werte auf einen Trigger genommen werden, wobei die Zeitstempel logischerweise identisch sind. Wenn's interessiert, die Zeitbasis sind ein paar zig ns und gesucht werden ganz zum Schluß Identitäten im Verlauf (also f'(t) und f"(t) ) zur Ablage in einer verkürzten Tabelle.

computertrolls schrieb:

Ich verstehe die Frage nicht.
Wenn du Daten im Dateisystem löschen musst, dann gibt's dafür rm, /dev/null und Co.

Danke, ich weiß schon, was ich in ein bash- script bzw. batch reinzuschreiben hätte, aber ich weiß nicht, wie ich das unter C starte. Wäre insofern easy, als daß ich mich dann nicht mit APIs auseinanderzusetzen hätte.

[computertrolls]

Sarkast schrieb:

computertrolls schrieb:

Ich verstehe die Frage nicht.
Wenn du Daten im Dateisystem löschen musst, dann gibt's dafür rm, /dev/null und Co.

Danke, ich weiß schon, was ich in ein bash- script bzw. batch reinzuschreiben hätte, aber ich weiß nicht, wie ich das unter C starte. Wäre insofern easy, als daß ich mich dann nicht mit APIs auseinanderzusetzen hätte.

Wenn dir eine Quick & Dirty Lösung reicht, dann geht's so:

#include <stdlib.h>
...
system("rm datei.xyz");

Das ruft dann rm auf oder irgendein anderer Befehl des Systems.
Der String muss einfach deinem Konsolenbefehl entsprechen.

Als Quick & Dirty Lösung ist das allemal ausreichend.

[Sarkast]

computertrolls schrieb:

Wenn dir eine Quick & Dirty Lösung reicht, dann geht's so:

#include <stdlib.h>
...
system("rm datei.xyz");

Das ruft dann rm auf oder irgendein anderer Befehl des Systems.
Der String muss einfach deinem Konsolenbefehl entsprechen.

Als Quick & Dirty Lösung ist das allemal ausreichend.

Das reicht mir völlig.