Sortieren im Stream



  • Hi zusammen, folgendes Problem:

    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ß.
    Tjoh, und was man zum Sortieren so findet, geht davon aus, daß man genug Speicher hat. Ein File als indizierbaren Speicher anzusprechen, das wird extrem schnarchig, ist mithin nicht gangbar.

    Wo finde ich passende Algorithmik, wenn ich nicht auf Java/C++ - Klassen(bibliotheken) zugreifen kann? Irgendwie scheinen die Suchmaschinen mit lauter solchen Out-of-the-Box- Lösungen zugespammed zu sein.

    Danke mal so.



  • Du könntest die Daten nach Messgröße gruppieren und in Gruppen sortiert in neue Dateien abspeichern.

    Eventuell auch in mehreren Durchgängen.
    Wenn du die Messdaten grob in Gruppen vorsortiert hast, dann sind deine vielen Gruppendateien logischerweise kleiner als die große Anfangsdatei und dann passen die einzeln somit in den Speicher.
    Am dem Punkt könntest du dann gängige Sortieralgorithmen anwenden.

    Das grobe Vorsortieren machst du mit einem Parser, der die Daten einfach vom Anfang bis zum Schluss durchläuft.

    Wenn's etwas effizienter sein soll, dann kannst du mehrere Blöcke auf einmal einlesen und auf die verschiedenen Cores verteilen und dort schon einmal vorsortieren und in die einzelnen Dateien schreiben.



  • Oder genau andersrum: Die Datei in handhabbare Teile aufsplitten (also in Teile, die man im Arbeitsspeicher halten und sortieren kann), und dann mit Mergesort zusammenfügen.



  • SG1 schrieb:

    Oder genau andersrum: Die Datei in handhabbare Teile aufsplitten (also in Teile, die man im Arbeitsspeicher halten und sortieren kann), und dann mit Mergesort zusammenfügen.

    Das wäre auch mein Vorschlag.

    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.

    @Sarkast
    Beim finalen "zusammenmergen" musst du bei "klassischem" Mergesort log2 N Durchgänge machen. D.h. du musst die gesamten Messdaten log2 N mal komplett lesen und komplett wieder schreiben. Wobei N die Anzahl der Stücke ist. D.h. du willst schonmal relativ grosse Stücke machen um mit N halbwegs runterzukommen. Übertreiben zahlt sich allerdings nicht aus, da du pro Verdoppelung der Stückgrösse ja bloss einen Durchlauf gewinnst.

    Man kann aber statt wie beim klassischen Mergesort immer nur zwei Stücke zu einem grösseren zusammenzumergen auch 4, 8, 16 ... Stücke auf einmal mergen. Damit kommst du dann auf log4 N , log8 N , log16 N ... runter. Was schonmal ein riesen Vorteil ist.

    ----

    Die Extremvariante ist dann alle Stücke auf einmal zu mergen. Wobei das nur Sinn macht wenn man einen ausreichend grossen Teil jedes Stücks als Lesepuffer im RAM halten kann. Angenommen du hast so wenig Stücke dass du pro Stück ca. 1 MB RAM oder mehr hast, dann geht das relativ gut. Dabei machst du grundsätzlich nen klassischen Mergesort, allerdings mit allen "merges" auf einmal. Ist ein bisschen schwer zu erklären, aber im Prinzip baust du dir eine Baumstruktur auf. Die inneren Knoten, inklusive dem Root-Knoten, sind dabei Merge-Operatoren die jeweils zwei Kind-Knoten haben. Und die Blatt-Knoten sind File-Reader die einfach aus einem der "Stücke-Files" lesen.

    Und dann liest du einfach das Ergebnis aus dem Root-Knoten aus 🙂

    Der Algorithmus läuft gut single-threaded, lässt sich im Falle des Falles aber auch sehr einfach parallelisieren.

    Angenommen du hast 1.5 GB RAM zur Verfügung könntest du eine Stückgrösse von 1 GB wählen und dann 1000 solche Stücke parallel mergen. Ginge also bis zu einer Gesamtmenge von 1 TB.



  • 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. 🙂



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



  • 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?



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



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



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



  • 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]



  • 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?



  • 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. 🙂



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



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



  • 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? 🙂


Anmelden zum Antworten