Sort 1TB file

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.

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

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.