Sortieren im Stream

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.

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.

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.

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.