Sort 1TB file

[SeppJ]

seldon schrieb:

http://sortbenchmark.org/
[...]
Und da sortiert man dann auch ganz sicher nicht einfach nur Zahlen, womit sich die Zählerei sowieso erledigt hat.

Der Indy-Benchmark macht genau das

[volkard]

Das Zählen ist lukrativ, weil jeder Wert im Durchschnitt 256 mal auftaucht.

Ich würde an Folgendes denken:
Beim Mergen hat man Streams von Paaren mit (Wert;Anzahl), und die bei Ungleichheit wird wie gehabt das Paar mit dem kleineren Wert geschrieben und weggelesen, bei Gleichheit einfach ein Paar mit dem Wert und der Summe der Anzahlen geschrieben und beide weggelesen. Ich könnte mir vorstellen, daß damit das Schreibvolumen Stufe für Stufe gehörig eingedampft wird.

Ansonsten gehts's nur drum, auf der Drehplatte zu vermeiden, daß der Kamm dauernd lange Wege macht. Uih... Stets die 2G als Puffer verwenden, klar.
Paarmal (8?) durchlaufen und nach ersten paar Bits sichten und Sichtungen rausschreiben. Hätte den Vorteil, daß die nächsten 8 Files am Stück wären. Nochmal machen, dann mergen? Unendlich viele Möglichkeiten.

Hat man zufällig drei Drehplatten? Dann könnte man immer von zweien auf die dritte mergen und hätte stets volle Bandbreite.

Mit SSDs in TB-Größe gehts's wieder anders.

[hustbaer]

seldon schrieb:

Ich halte es bei einer Datenmenge von 1TB nicht für angebracht, die Komplexitätsklasse mit "*gähn*" abzutun.

Mein Bauchgefühl sagt mir, dass es hier angebracht ist
Daher das "*gähn*" - weil du mMn. auf etwas rumreitest dass bei genau der gegebenen Aufgabenstellung irrelevant ist. (Also so lange es um den Unterschied Quicksort + "breitem" Merge vs. O(N) geht -- bei "schlimmerem" als Quicksort würden wir vermutlich wirklich ein Problem bekommen.)

seldon schrieb:

1TB Daten zu sortieren, das wird ne Weile dauern, ganz egal, wie du es anfängst, und "Ansatz 1 dauert nen Tag, das ist mir zu lange" belegt nicht, dass Ansätze 2 und 3 schneller laufen.

Ich müsste es ausprobieren, aber wieder: mein Bauchgefühl sagt mir dass es in deutlich weniger als einem Tag geht. So lange man es cachefreudnlich implementiert, und sowohl Quicksort als auch Mergesort sind cachefreudnlich (ich hoffe, es ist spät, ich kann nicht mehr denken, hihi).

seldon schrieb:

Ich hab jetzt mal nachgemessen, anstatt mir Zahlen zusammenzufantasieren, und du hast in Bezug auf eine Sache recht: Die seeks auf einer Festplatte kommen zu langsam. Nicht so langsam, wie du es einschätzt -- das pegelt sich in meiner Messung recht schnell bei so 1000 seek-read-seek-write-Zyklen pro Sekunde ein (Zugriffsstelle in der Datei jeweils zufällig ausgewürfelt), aber zu langsam für den use case.

Also hier sagt mir meine Erfahrung dass das nicht sein kann. Hast du mit einem File gemessen das - so wie im Beispiel - viel viel grösser als das als File-Cache zur Verfügung stehende RAM war?

seldon schrieb:

Abhängig von der Festplatte mag das variieren -- ich habe jetzt auf einer einzelnen consumer-hdd gemessen, wo in der Realität ein RAID wahrscheinlicher wäre -- aber wahrscheinlich nicht mehr als eine Größenordnung.

Mit RAID kannst du quasi beliebig skalieren - du brauchst nur genügend Platten. Aber bei nem Rechner mit 2 GB RAM ein fettes RAID anzunehmen... also das wäre schon etwas komisch.

seldon schrieb:

Eine Messung auf SSD werde ich noch nachreichen, sobald ich wieder vor einer SSD sitze. Da das Zugriffsmuster für eine HDD sehr ungünstig ist und einer SSD geschwindigkeitstechnisch prinzipiell egal sein sollte (auch wenn es Gift für das wear-leveling ist), sollte uns das in realistischere Bereiche rücken.

Ich hab' die Zahl nicht einfach aus der Luft gegriffen. Günstige SSDs schaffen alleine schon wegen dem "langsamen" SATA Bus nicht mehr als etwa 100K IOPS. Und das ist ohne read-modify-write, als muss man die Zahl sogar nochmal halbieren. Und wenn du es nicht optimierst läuft alles mit Queue-Depth 1, und die Performance stirbt dir komplett weg.

seldon schrieb:

Wenn Faktor 1000 bei ner SSD richtig ist (Messung folgt noch), dann sind es 3 Tage und gut 4 Stunden, das wäre auf einer Node mit 2 GB verfügbarem RAM realistischer. Meine Vermutung ist aber, dass, weil Seeken der SSD echt egal ist, der Unterschied nochmal größer ausfallen wird.

Siehe oben. Die 100K IPOS sind schon sehr hoch geschätzt. Und das ist bestenfalls "nur" Faktor 50 gegen die von dir gemessenen (und von mir bezweifelten *g*) 1000 Read-Modify-Write pro Sekunde.

seldon schrieb:

In einer Messung von Thomas Krenn einer Intel-SSD im Januar (Link weiter unten) zeigte sich da kein Unterschied zwischen sequentiellen und zufälligen Zugriffen, und wenn man die 8 Terabyte Zähler da wirklich mit 90 MB/s durchdübeln kann, reden wir nur noch von einem Tag. Das alles unter dem Vorbehalt einer Messung, die ich noch tun muss -- dummerweise bedeutet das, dass diese Hochrechnung nicht so richtig wertvoll ist.

Die 90 MB/s kommen schon hin. Mit Queue-Depth "ganz viel", und 4K Zugriffen. Mit 512 Byte Zugriffen (=1 Sektor= kleiner geht nicht) schafft eine moderne SSD es auch noch (aber nur weil sie mit 4K deutlich mehr als 90 MB/s schafft).
Und von den 512 Byte verwendest du worst-case dann 4 (oder 1 oder 6 oder 8 - einen Zähler halt - kommt dann drauf an ob man ne Spetialbehandlung für überlaufende Zähler machen will, oder lieben den Zähler so breit dass er nicht überlaufen kann). Und im average-case werden es auch deutlich weniger als 512 Byte sein. Mit MB/s zu rechnen führt hier nicht weit => IOPS ist schon der sinnvolle Wert beim Rausschreiben der Zähler.

seldon schrieb:

Gegenrechnung Mergesort: Ich hab wieder mal gemessen. Auf meinem i7-4771 dauert ein std::sort (also ein Quicksort) von 1 GB Zufallsdaten ~21 Sekunden. Das muss man tausend mal machen, sind knapp 6 Stunden. zwei davon im RAM zu std::mergen dauert hier 0,41 Sekunden. Wenn man alles im Speicher halten könnte und durch sukzessives Mergen größere Vektoren zusammenbauen würde (immer zwei mergen), wäre man am Ende hochgerechnet eine halbe Stunde beschäftigt. Das alles im RAM zu halten ist natürlich illusorisch, wenn uns nur 2 GB zur Verfügung stehen. Nehmen wir - jetzt wird's dekadent - eine >2 Terabyte-SSD als scratch space an, die einen Datendurchsatz von 250 MB/s Lesen und 90 MB/s Schreiben schafft (das sind Optimalwerte aus einer Messung von Thomas Krenn im Januar). Wir erzeugen ein Datenvolumen von 10 TB (10 Merge-Ebenen, für die jeweils der gesamte Content gelesen und geschrieben wird. Die naheliegende Idee, alles gleichzeitig zu mergen, skaliert mit O(n²) und wird langsamer sein), das macht 11 Stunden Lesen und 1 Tag und gut 6 Stunden Schreiben. Wir sind inzwischen bei 2 Tagen.

(jeweils plus das, was in beiden Fällen gemacht werden muss)

#1 ich weiss nicht wo du die Werte hernimmst. Die €180 Samsung 840 PRO in meinem PC schafft an die 500 MB/s beim linear lesen und auch beim linear Schreiben.

#2 wieso sollte man immer nur jeweils zwei Blöcke auf einmal zusammenmergen? Damit meine Variante abstinkt?
Als erstes zerteilst du das File in 1000 1 GB Blöcke, und sortierst diese (Quicksort). Soweit OK.
Aber dann mergest du alle 1000 Blöcke in einem Durchgang zusammen.
Die Daten der Input-Blöcke kannst du dabei mit einem z.B. 1 MB Puffer pro Block "streamen". Also erstmal alle Puffer anfüllen, und wenn ein Puffer leer ist, liest du einen neuen 1 MB Block aus der passenden Stelle des Temp-Files.
Und die Output-Daten streamst du ebenso wieder: alles in einen 1 MB (oder gerne auch etwas grösser) Output-Puffer schreiben, und wenn der voll ist ans Output-File anhängen.

Der IO Aufwand beim Mergen beläuft sich damit auf 1x Lesen und 1x Schreiben von jeweils 1 TB. In 1 MB Blöcken, was, wie ich früher schon erwähnt habe, so-gut-wie optimale Geschwindigkeit bedeutet. Auch mit ner HDD.

seldon schrieb:

Egal, was am Ende konkret schneller wäre, man kann sich bei solchen Datenmengen nicht mehr auf sein Gefühl verlassen -- vor allem, wenn sich das Gefühl vor allem um etwas dreht, das am Ende einen konstanten Faktor ausmacht. Den Daumen vor die Schnauze zu halten und zu sagen "Komplexitätsklasse, gähn. Gefühlt muss der Mergesort da in zwei Stunden durch sein" führt einen in die Irre. Der Haken ist genau

hustbaer schrieb:

Zumindest nicht bei gängigen Systemen mit gängigen RAM Grössen.

...wir reden hier nicht mehr von gängigen Größen.

Also erstmal hast du hier genau das selbe gemacht - aber OK, das schreibst du ja gleich selbst

Und dann... wie, keine gängigen Grössen? Ich hab RAM Grössen geschreiben. Und 2 GB RAM ... naja, OK, das ist sogar schon weniger als "gängig".
Mein Einwand war konkret bezogen auf dein Abtun von Bäumen als in-memory Datenstruktur "weil Komplexitätsklasse". Und da kannst du gerne mal googeln - eine Hashmap ist in-memory fast nie wesentlich schneller als ein Baum. Weil keiner genug RAM hat um in Bereiche vorzustossen wo die Hashmap aufholen könnte.
Mit einem einfachen Hashtable, selbst implementiert, ohne double Hashing oder Buckets oder sonstwas, könnte man um eine Grössenordnung schneller sein. Den würde man dann nicht gesamt "flushen", sondern einfach bei ner Kollision den einen kollidierenden Wert "flushen". Was vermutlich sogar gut wäre, da die HDD/SSD dann fast permanent arbeitet und es kaum Pausen gibt wo "nur gerechnet" wird. Die IO Kosten bringen dich dabei aber immer noch um.

Und gerade um das Senken der IO Kosten ging es mir ja beim Vorschlag statt der Hashmap eine Treemap zu verwenden. Weil man die "sortiert" rausschreiben kann, was für ne HDD ein wesentlich günstigeres Zugriffsmuster ist als "random". Auch wenn man dabei immer weder etliche Sektoren überspringt. Und selbst mit einer SSD kannst du mit der Treemap Zähler die im selben Sektor liegen mit nur einem Zugriff rausschreiben, wohingegen du mit der Hashmap diesen Sektor dann doppelt oder dreifach angreifen müsstest.

seldon schrieb:

Medallien-Kehrseite: Ich hab den Effekt des log(n)-Faktors größer eingeschätzt und hätte erwartet, dass der mergesort deutlich länger braucht. Den Schuh des getrügten Gefühls muss ich mir auch anziehen.

Hihi, genau.

seldon schrieb:

Worauf wir jetzt noch überhaupt nicht eingegangen sind, ist der eigentliche Trick im Umgang mit solchen Datenmassen: Parallelisierung. Ich habe in der Aufgabenstellung jetzt keine Information darüber gesehen, wie viele Prozessorkerne der TE benutzen darf, aber letztendlich ist das Szenario der Aufgabe eh unrealistisch. Ich lass mal folgenden Link da:

http://sortbenchmark.org/

...und stelle anheim, dass derart große Datenmengen in der Praxis immer verteilt auf großen HPC-Clustern verarbeitet werden, wo man das in brauchbarer Zeit hinkriegt, und wo jede Node auch ausreichend RAM rumliegen hat, um nicht dauernd Dinge auf Platte schreiben zu müssen. Und da sortiert man dann auch ganz sicher nicht einfach nur Zahlen, womit sich die Zählerei sowieso erledigt hat.

Womit wir dann vermutlich wieder beim Quicksort + Merge wären, weil das supi-einfach parallelisierbar ist

[hustbaer]

volkard schrieb:

Hat man zufällig drei Drehplatten? Dann könnte man immer von zweien auf die dritte mergen und hätte stets volle Bandbreite.

Wieso nicht erst mit Quicksort handliche Blöcke machen, und die dann alle auf einmal mergen?
Oder spinne ich jetzt und Mergen ist in Wirklichkeit gar nicht streambar?

[volkard]

hustbaer schrieb:

volkard schrieb:

Hat man zufällig drei Drehplatten? Dann könnte man immer von zweien auf die dritte mergen und hätte stets volle Bandbreite.

Wieso nicht erst mit Quicksort handliche Blöcke machen, und die dann alle auf einmal mergen?
Oder spinne ich jetzt und Mergen ist in Wirklichkeit gar nicht streambar?

Die 500 handlichen Dateien könnten dazu führen, daß wenn man sie auf einer Drehplatte zugleich lesen will, daß pro neuem Sektor der Kamm die volle Random-Seek-Zeit braucht (das sind Millisekunden!). Mit 3 Platten müßte der Kamm nie umherspringen, sondern nur gelegentlich mal einen Zylinder um +-1 wechseln.

Klar vorher Quicksort/Introsort und alle kleineren Tricks.

[asdfaaa]

hustbaer schrieb:

seldon schrieb:
Worauf wir jetzt noch überhaupt nicht eingegangen sind, ist der eigentliche Trick im Umgang mit solchen Datenmassen: Parallelisierung. Ich habe in der Aufgabenstellung jetzt keine Information darüber gesehen, wie viele Prozessorkerne der TE benutzen darf, aber letztendlich ist das Szenario der Aufgabe eh unrealistisch. Ich lass mal folgenden Link da:

http://sortbenchmark.org/

...und stelle anheim, dass derart große Datenmengen in der Praxis immer verteilt auf großen HPC-Clustern verarbeitet werden, wo man das in brauchbarer Zeit hinkriegt, und wo jede Node auch ausreichend RAM rumliegen hat, um nicht dauernd Dinge auf Platte schreiben zu müssen. Und da sortiert man dann auch ganz sicher nicht einfach nur Zahlen, womit sich die Zählerei sowieso erledigt hat.

Womit wir dann vermutlich wieder beim Quicksort + Merge wären, weil das supi-einfach parallelisierbar ist

Wobei die Zeiten dort durch 2 "Tricks" entstehen:
1. Die Zeiten, um die Daten im Hadoop Cluster zu verteilen, werden nicht gemessen. (MMn ist das der grosse Fake: Eigentlich gehoert das mit dazu um eine Vergleichbarkeit der Loesungsansaetze zu bekommen. Ggf. einfach als getrennte Messung, aber wenigstens dokumentiert)
2. Es werden deutlich mehr Daten verarbeitet, damit ueberhaupt alle Knoten etwas sinnvolles zu tun haben.

Dennoch: Die von Hustbaer vorgeschlagene Loesung mit Streaming der vorher mit Quicksort sortierten Bloecke halte ich fuer den einzig sinnvollen Ansatz auf einer einzelnen Maschine. Ein Optimierungsansatz waere vielleicht KEIN RAID zu nutzen sondern nur ein BOD (Bunch of Disks) und die vorsortierten Bloecke geschickt auf die Platten (und Disk-Controller) zu verteilen.

[hustbaer]

@volkard
Ja, 100% Linear-Lesen Geschwindigkeit wird man nicht bekommen. (Ich hab' mich auch wiedermal verschätzt mit 1 MB Puffern ist man sogar noch deutlich davon entfernt - siehe unten.)

Aber wenn man den Grossteil der 2 GB RAM die man hat zum Puffern der 500~1000 Input-Streams verwendet, dann wird's schon gehen. 1 MB pro Input-Stream sollten damit locker drin sein. Wenn man die Grenzen gut auslotet (also wie viel RAM man wirklich verwenden kann, bevor das OS anfängt zu pagen) vermutlich sogar etwas mehr.

Laut h2benchw liegen Desktop HDDs so im Bereich 12~20ms für das Lesen eines Sektors an einer zufälligen Position - nehmen wir mal 16ms an (Mittelfeld).
Danach geht's mit Linear-Lesen Geschwindigkeit weiter - im Moment so ca. 130~150 MS/s -- nehmen wir 140 MB/s an.
D.h. pro Megabyte ca. 7ms.
In Summe für 1 MB Lesen an einer zufälligen Position dann 16+7=23ms.
D.h. wir bekommen auf der HDD immer noch ~43 MB/s hin.
Also ca. 1/3 von der Linear-Lesen Geschwindigkeit.

Die Zwischenpuffer für das Mergen von je zwei Streams zu einem kann man viel kleiner machen, da ein "Seek" im RAM ja kaum weh tut. 64 KB sollten da locker reichen, d.h. dafür geht kaum RAM drauf (insgesamt weniger als 100 MB).

Den Output-Puffer können wir grösser machen, von dem brauchen wir ja nur einen. 100 MB sollte man sich dafür leisten können. Ich nehme dafür jetzt einfach mal 100 MB/s für's Schreiben an (wird real eher mehr sein), also 10ms pro Megabyte.

D.h. wir brauchen für den Merge pro Megabyte insgesamt 23ms zum Lesen und 10ms zum Schreiben, also in Summe 33ms.

Wenn wir mehrere Durchgänge machen, so dass wir immer volle Speed bekommen, brauchen wir pro Megabyte pro Durchgang idealerweise 7 Lesen + 7 Schreiben=14ms.

=> Wenn wir mit zwei Durchgängen auskommen, dann sind wir mit 28 statt 33 ms knapp schneller.
Wenn wir mehr als zwei Durchgänge brauchen gewinnt aber schon die "alles in einem" Variante (deutlich). Und mit ner SSD sowieso.

[seldon]

Verkürzend zusammengefasst: Ich habe mit einer 32GB großen Daten gemessen. Auf dein Bauchgefühl re iops mag ich mich nicht verlassen. Auf mein Bauchgefühl sollte ich mich auch nicht verlassen. Die 250 MB/s kamen aus dem Link im Text. Deine SSD kann ich nicht nachmessen; wenn du selbst nachmessen willst, wieviel Random-I/O sie hinkriegt, gegen harte Fakten werde ich nicht argumentieren. Andernfalls muss ich das selbst machen, was aber dauert, bis ich eine Maschine mit SSD in die Finger kriege. Bulk-Merge wäre keine gute Idee, weil das quadratisch skaliert -- führt zu weniger I/O, dafür zu mehr Extrarechenaufwand, als das I/O gekostet hätte. Darum ist Mergesort auch nirgends mit Bulk-Merge spezifiziert. Ich mag mich manchmal verschätzen, aber wenn du ernsthaft glaubst, dass ich absichtlich schlechte Implementationen einer Methode aussuche, um damit ergebnisverfälschende Vergleiche anzustellen, dann brauchen wir nicht mehr miteinander zu diskutieren. Im konkreten Fall solltest du es einfach mal ausprobieren; nach meinen Hochrechnungen würde das Mergen im RAM auf die Art nicht eine halbe Stunde, sondern auf der gleichen Maschine grob anderthalb Tage dauern.

Was Hashmaps angeht, ich finde per Suchmaschine nichts, was deinen Standpunkt erhärtet. Hast du eine Quelle für mich? Meine eigene Messung:

#include <ctime>
#include <iostream>
#include <map>
#include <unordered_map>
#include <random>

void measure_tree() {
  int tsum = 0;
  std::map<int, int> treemap;
  std::mt19937 rng;

  std::clock_t beg = std::clock();

  for(int i = 0; i < N; ++i) {
    ++treemap[rng()];
  }

  for(auto &e : treemap) {
    tsum += e.second;
  }

  std::clock_t end = std::clock();

  std::cout << tsum << ", " << static_cast<double>(end - beg) / CLOCKS_PER_SEC << '\n';
}

void measure_hash() {
  int hsum = 0;
  std::unordered_map<int, int> hashmap;
  std::mt19937 rng;

  hashmap.max_load_factor(0.8);
  hashmap.reserve(N / 0.8 + 1);

  std::clock_t beg = std::clock();

  for(int i = 0; i < N; ++i) {
    ++hashmap[rng()];
  }

  for(auto &e : hashmap) {
    hsum += e.second;
  }

  std::clock_t end = std::clock();

  std::cout << hsum << ", " << static_cast<double>(end - beg) / CLOCKS_PER_SEC << '\n';
}

int main() {
  measure_hash();
  measure_tree();
}

ergibt

$ for i in 1000000 10000000 100000000; do g++ -std=c++11 -O3 -DN=$i foo.cc && ./a.out; done
1000000, 0.187788
1000000, 0.636026
10000000, 2.05519
10000000, 10.8927
100000000, 26.4502
100000000, 181.287

Und das wird mit mehr Elementen nicht besser.

[seldon]

Nachtrag: Die besten Ergebnisse für den Bulk-Merge kriege ich mit folgendem Code:

#include <ctime>
#include <algorithm>
#include <random>
#include <vector>
#include <iostream>

struct merge_data {
  std::size_t vector_index;
  std::vector<int>::const_iterator iter;
};

int main() {
  std::vector<std::vector<int>> vecs(1 << 10, std::vector<int>(1 << 12));

  std::mt19937 rng;

  for(auto &v : vecs) {
    std::generate(v.begin(), v.end(), rng);
    std::sort(v.begin(), v.end());
  }

  std::vector<merge_data> iters(vecs.size());
  for(std::size_t i = 0; i < vecs.size(); ++i) {
    iters[i].vector_index = i;
    iters[i].iter = vecs[i].begin();
  }

  std::clock_t beg = std::clock();

  while(!iters.empty()) {
    auto next = std::min_element(iters.begin(),
                                 iters.end(),
                                 [](merge_data const &lhs, merge_data const &rhs) {
                                   return *lhs.iter < *rhs.iter;
                                 });
    ++next->iter;
    if(next->iter == vecs[next->vector_index].end()) {
      iters.erase(next);
    }
  }

  std::clock_t end = std::clock();

  std::cout << static_cast<double>(end - beg) / CLOCKS_PER_SEC << '\n';
}

Dauert hier gut 4.4 Sekunden. Für 16 MB. Mit größeren Blöcken wird die Sache schlimmer, weil der CPU-Cache dann nicht mehr reicht; dann kommt etwa Faktor 8 (ymmv) nochmal drauf (66 Sekunden für 32 MB). Aufs Terabyte hochgerechnet sind das 3 Tage und 8 Stunden, wenn alls immer heiß im Cache ist. Das ist die theoretische Untergrenze; ob das File-I/O, das in unregelmäßigen Abständen stattfinden müsste (für jeweils 16KB am Stück), möglich ist, ohne den CPU-Cache-Effekt zu beschädigen (so wegen Kontext-Switches und derlei), ist für mich nicht offensichtlich. Ohne diesen Effekt reden wir pessimistisch von etwa vier Wochen.

Das alles nur fürs Iterator-Schubsen. Aus Dateien gelesen oder in sie geschrieben ist damit noch nichts, wobei das bei dieser Vorgehensweise nicht den Löwenanteil ausmachen dürfte.

[asdfaaa]

@seldon

Dein Code sortiert und merged alles auf einmal. Das ist aber nicht der diskutierte Ansatz. Schneller (ich kann es hier im Moment nicht ausprobieren) ist mit sehr hoher wahrscheinlichkeit eine paralleles Sortieren der einzelnen Vektoren und danach ein Merge derart, dass immer nur das erste Element der bereits sortierten Vektoren betrachtet und das davon kleinste in das Ziel kopiert wird. So sind bei n Vergleichen n-1 ELemente im Cache. Zumindest bis zu einer gewissen Anzahl von Vektoren.

[prioq]

prioq schrieb:

Kein Problem, dafür gibt's die std::priority_queue .

[volkard]

seldon schrieb:

Bulk-Merge wäre keine gute Idee, weil das quadratisch skaliert

Nimm nen Heap, in den Du (ersterWert;ZeigerAufStream) der 500 Streams stopfst. Dann skaliert Bulk-Merge auch logarithmisch und alles wird gut.

[hustbaer]

@seldon
Man merged natürlich immer nur zwei Streams direkt.
Aber halt insgesamt trotzdem alles auf einmal.

Das was du hintereinander machen würdest, mit zurückschreiben auf die Disk dazwischen, baust du als Baum auf. Ein Durchgang bei dir wird zu einer Ebene im Baum.
Die Leaf-Ebene (1. Durchgang) besteht aus Disk-Readern.
Danach kommen jeweils Merger.
Jeder Knoten hat einen Puffer und eine "FillBuffer" Operation, mit dem der Knoten darüber den Puffer neu auffüllen kann wenn er leergelaufen ist.

Das "FillBuffer" vom Disk-Reader liest dabei einfach nur, und das "FillBuffer" vom Merger merged eben.

Die Merge-Schleife arbeitet dabei also auf 2 Arrays und schreibt ihren Output in ein weiteres Array. Sehr Cache-freundlich. Und ab und an muss sie die "FillBuffer" der Kindknoten aufrufen.

[seldon]

Ah.

...

Okay, das sind Argumente. Auf beides bin ich gestern irgendwie überhaupt nicht gekommen, was mir im Nachhinein ziemlich peinlich ist.

[nurf]

Zurück zum Ursprungsthema, wer fragt sowas und warum.
Das ist ein typischer Einstellungstest für Facebook oder Google.
Dabei geht es auch darum "Out-Of-The-Box" zu denken.
Bei der Anzahl von Kollisionen braucht doch keiner wirklich eine sortierte Zielmenge, das ist doch schon ne Fangfrage.

Ansonsten: Quicksort ist vielleicht nicht das Schnellste hier, aber alle Anfänger stürzen sich auf Quicksort.

Nicht einmal hab ich in diesem Thread bisher das Stichwort "Kompression" gelesen (vielleicht hab ichs auch überlesen).

Folgende Lösungsansätze biete ich mal an:
Naives durchzählen: 1TB => 40bit Addressierung
10 Mal sequentiell die Ausgangsmenge durchgehen.
Dauer = 10TB/Festplattenspeed
Wegschreiben von 10*2 GB ist vernachlässigbar.

4Bit Durchzählen:
So bringt man die Werteraum in 2GB unter.
Wenn der 4bit Wert überläuft -> wegschreiben und mit dem Wert auf Festplatte addieren.
Das können aber Extra-Threads machen.
Vorteil: nur 1TB sequentiell lesen
Nachteil: randomisierte Lese/Schreibzugriffe auf Zielmenge.

[volkard]

nurf schrieb:

Nicht einmal hab ich in diesem Thread bisher das Stichwort "Kompression" gelesen (vielleicht hab ichs auch überlesen).

Ich hatte einen Vorschlag, der zusammenfaltet.

nurf schrieb:

Folgende Lösungsansätze biete ich mal an:
Naives durchzählen: 1TB => 40bit Addressierung
10 Mal sequentiell die Ausgangsmenge durchgehen.
Dauer = 10TB/Festplattenspeed
Wegschreiben von 10*2 GB ist vernachlässigbar.

Versteh Deine Rechnung nicht.
Eine Zahl kann maximal 2^36 mal vorkommen, also lauter 36-Bit-Zähler, also 9 Byte, also passen 238Mio Zähler ins ram, also 291 Durchläufe.

nurf schrieb:

4Bit Durchzählen:
So bringt man die Werteraum in 2GB unter.
Wenn der 4bit Wert überläuft -> wegschreiben und mit dem Wert auf Festplatte addieren.
Das können aber Extra-Threads machen.
Vorteil: nur 1TB sequentiell lesen
Nachteil: randomisierte Lese/Schreibzugriffe auf Zielmenge.

Ähm, der 4-Bit-Wert läuft dauernd über! Es muss immer oder zu mehr als 99.9% weggeschrieben werden. Das wird lahm, weil das Wegschreiben ja nix zur Sortierung beiträgt.

[hustbaer]

@seldon
Siehst du, genau deswegen dachte ich auch du willst mich vielleich veräppeln

@nurf
Ich denke wir haben hier schon eine ziemlich gute Lösung.
Und ob das ne Fangfrage ist oder nicht ist dabei doch völlig egal.
Ob es ne Frage für nen Einstellungs-Test ist, ist natürlich nicht egal, genau so wie ob es ne Klausurfrage oder Hausaufgabe ist.
Aber hey, ich hab' zumindest nicht als erster geantwortet

[SeppJ]

hustbaer schrieb:

Aber hey, ich hab' zumindest nicht als erster geantwortet

Der Fragesteller hat sich ja sogar schon im Eingangsbeitrag selber geantwortet mit einer Lösung, die im Ansatz der diskutierten gleicht. Nur die Details habt ihr inzwischen feiner ausgearbeitet. Also eigentlich ideal, wie ein Thread wie dieser verlaufen soll.

[hustbaer]

Stimmt, das entspricht im Prinzip "unserer" Lösung.
Hatte ich ganz vergessen, da ich auch erst auf dem "zählen" Dampfer war, und mir gedacht habe das geht viel besser

Einzig wie das mit dem Mergen gemeint ist ist nicht klar, also ob ihm klar ist war dass man das mit nem Graphen aus 2-Way-Merge "Streams" machen sollte.