anwenden:sort1mio
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | anwenden:sort1mio [2020-07-26 18:34] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Wie sortiert man eine Million 32bit-Ganzzahlen (mit weniger als 2 MB Hauptspeicher in C++)? ====== | ||
+ | > // I think the bubble sort would be the wrong way to go. // | ||
+ | >> -- Barack Obama | ||
+ | |||
+ | Vor kurzem stieß ich auf ein YouTube-Video | ||
+ | ([[http:// | ||
+ | aus dem US-Präsidentschaftswahlkampf 2008, | ||
+ | in welchem der Kandidat eine Job-Interview-Frage des damaligen Google-Chefs Eric Schmidt souverän, | ||
+ | aber dennoch diplomatisch beantwortet. | ||
+ | Die Hintergründe beleuchtet ein | ||
+ | [[http:// | ||
+ | der New York Times. Einiges deutet darauf hin, dass die Frage auf den | ||
+ | [[http:// | ||
+ | eines prominenten Google-Mitarbeiters anspielt: Guido van Rossum, Erfinder von Python, | ||
+ | beantwortet darin diese Frage " | ||
+ | [[http:// | ||
+ | gibt neben dieser Quelle auch einige allgemeine Hinweise. | ||
+ | Zwei Aspekte erschienen mir interessant genug, um ihnen genauer nachzugehen: | ||
+ | * Wie sieht eine Lösung in C++ aus? | ||
+ | * Gibt es einen Geschwindigkeitsunterschied zwischen den Lösungen in C++ und Python? | ||
+ | |||
+ | ====== Grundidee ====== | ||
+ | Sortieren geschieht am schnellsten im Hauptspeicher, | ||
+ | Im speziellen Fall, der häufiger eintritt als erwünscht, reicht aber der Hauptspeicher nicht einmal aus, | ||
+ | alle Daten zu halten. | ||
+ | (Virtueller Speicher ist auch keine Lösung, da dieser über langsame Festplattenzugriffe realisiert wird.) | ||
+ | Ein externes Sortierverfahren muss her. | ||
+ | Ein rein externes Verfahren wie Mergesort erfordert jedoch viele Sortierläufe mit langsamen Zugriffen auf die Festplatte. | ||
+ | Die Lösung, ein Kompromiss aus internem und externem Sortieren, besteht aus zwei Phasen. | ||
+ | - Die Datenquelle wird blockweise in den Hauptspeicher geladen, sortiert, und die sortierten N Blöcke in eine temporäre Datei geschrieben. | ||
+ | - Ein [[http:// | ||
+ | |||
+ | |.oO0*|o0*.O|O.*o| | ||
+ | | ||
+ | |.*o0O|.*o0O|.*oO| | ||
+ | \ | / | ||
+ | jeweils kleinstes Element finden --> |.......> | ||
+ | ====== Implementierung ====== | ||
+ | ===== Phase 1: Blockweises Vorsortieren ===== | ||
+ | Die erste Phase lässt sich im Vorwärtsgang über die Eingabedatei erledigen. | ||
+ | Liegen die Zahlen als Binärdaten in der Datei vor, können sie schnell, | ||
+ | d.h. ohne Konvertierung zwischen Textformat und Binärformat, | ||
+ | in den Hauptspeicher geholt und auch wieder ausgelagert werden. | ||
+ | |||
+ | <code cpp> | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | #include < | ||
+ | |||
+ | size_t const TESTSIZE = 1000000; | ||
+ | size_t const BLOCKSIZE = 100000; | ||
+ | size_t const BUFFERSIZE = 1024; | ||
+ | |||
+ | std:: | ||
+ | { | ||
+ | return std::cerr; | ||
+ | } | ||
+ | |||
+ | size_t partition(std:: | ||
+ | { | ||
+ | std:: | ||
+ | std:: | ||
+ | size_t written = 0; | ||
+ | |||
+ | int block[BLOCKSIZE]; | ||
+ | size_t const size = sizeof(int); | ||
+ | size_t start = in.tellg(); | ||
+ | while (in.read((char*)block, | ||
+ | { | ||
+ | size_t stop = in.tellg(); | ||
+ | size_t n = (stop - start) / size; | ||
+ | std:: | ||
+ | if (n) out.write((char*)block, | ||
+ | written += n; | ||
+ | start = stop; | ||
+ | } | ||
+ | return written; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ===== Phase 2: n-Wege-Mischen ===== | ||
+ | Die zweite Phase erfordert dagegen ein ständiges Hin- und Herspringen zum jeweils nächstkleinsten Element. | ||
+ | Das Positionieren in der Temporärdatei ist zeitaufwendig. | ||
+ | Dies kann abgemildert werden, wenn mehrere Ganzzahlen auf einmal gelesen und gepuffert werden. | ||
+ | |||
+ | Die optimale Puffergröße ist durch Laufzeitmessung bestimmbar. | ||
+ | Dabei muss der Platzbedarf für N Puffer ebenfalls der Hauptspeicherbeschränkung genügen. | ||
+ | <code cpp> | ||
+ | class Buffer | ||
+ | { | ||
+ | public: | ||
+ | Buffer(std:: | ||
+ | : file_ (file) | ||
+ | , start_(start-BUFFERSIZE) | ||
+ | , end_ (end) | ||
+ | { | ||
+ | read(); | ||
+ | } | ||
+ | | ||
+ | int first() const { return data_.front(); | ||
+ | bool empty() const { return data_.empty(); | ||
+ | void next() | ||
+ | { | ||
+ | data_.pop_front(); | ||
+ | if (empty()) read(); | ||
+ | } | ||
+ | | ||
+ | void read() | ||
+ | { | ||
+ | size_t const block = sizeof(int); | ||
+ | start_ += BUFFERSIZE; | ||
+ | if (start_ >= end_) return; | ||
+ | // log() << "read buffer pos = " << start_ << ' | ||
+ | // log() << " | ||
+ | assert(file_); | ||
+ | file_-> | ||
+ | int buf[BUFFERSIZE]; | ||
+ | size_t n = std:: | ||
+ | file_-> | ||
+ | n = file_-> | ||
+ | data_= std:: | ||
+ | } | ||
+ | private: | ||
+ | std:: | ||
+ | std:: | ||
+ | size_t start_; | ||
+ | size_t end_; | ||
+ | }; | ||
+ | </ | ||
+ | Mit dieser Hilfsklasse kann das n-Wege-Mischen implementiert werden. | ||
+ | Aus Phase 1 ist die Anzahl zu sortierender Zahlen bekannt. | ||
+ | |||
+ | Eine Prioritätswarteschlange erledigt in der zweiten Phase die Buchhaltung, | ||
+ | aus welchem Block das jeweils kleinste Element entnommen wurde. | ||
+ | Wenn dieser Block (bzw. sein Puffer) noch nicht leer ist, wird das nächste Element eingereiht. | ||
+ | <code cpp> | ||
+ | bool nWayMerge(size_t n, std::string infile, std::string outfile) | ||
+ | { | ||
+ | std:: | ||
+ | std:: | ||
+ | if (!in || !out) return false; | ||
+ | | ||
+ | std:: | ||
+ | for (size_t i = 0; i < n; i+= BLOCKSIZE) | ||
+ | { | ||
+ | Buffer buffer(& | ||
+ | if (!buffer.empty()) buffers.push_back(buffer); | ||
+ | } | ||
+ | log() << buffers.size() << " way sort, buffers created\n"; | ||
+ | | ||
+ | typedef std:: | ||
+ | std:: | ||
+ | | ||
+ | for (int i = 0; i < buffers.size(); | ||
+ | { | ||
+ | Buffer& buffer = buffers[i]; | ||
+ | queue.push(pair(buffer.first(), | ||
+ | } | ||
+ | |||
+ | int outbuffer[BUFFERSIZE]; | ||
+ | int count = 0, written = 0; | ||
+ | while (!queue.empty()) | ||
+ | { | ||
+ | pair p = queue.top(); | ||
+ | queue.pop(); | ||
+ | int value = p.first; | ||
+ | // log() << value << ' '; | ||
+ | outbuffer[count++] = value; | ||
+ | if (count == BUFFERSIZE) | ||
+ | { | ||
+ | out.write((char*) outbuffer, count*sizeof(int)); | ||
+ | written += count; | ||
+ | count = 0; | ||
+ | } | ||
+ | int bufNo = p.second; | ||
+ | Buffer& buffer = buffers[bufNo]; | ||
+ | buffer.next(); | ||
+ | if (!buffer.empty()) queue.push(pair(buffer.first(), | ||
+ | } | ||
+ | if (count) | ||
+ | { | ||
+ | out.write((char*) outbuffer, count*sizeof(int)); | ||
+ | written += count; | ||
+ | } | ||
+ | return written == n; | ||
+ | } | ||
+ | </ | ||
+ | Die eigentliche Sortierroutine bestimmt einen Temporärdateinamen | ||
+ | und sorgt dafür, diese Datei nach Gebrauch zu löschen. | ||
+ | <code cpp> | ||
+ | bool run(std:: | ||
+ | { | ||
+ | std::string tmp(std:: | ||
+ | log() << " | ||
+ | size_t nElements = partition(source, | ||
+ | log() << "n way merge to sorted file\n"; | ||
+ | bool done = nWayMerge(nElements, | ||
+ | log() << " | ||
+ | std:: | ||
+ | return done && nElements != 0; | ||
+ | } | ||
+ | </ | ||
+ | ===== Testrahmen ===== | ||
+ | Eine Datei mit Zufallszahlen wird erzeugt: | ||
+ | <code cpp> | ||
+ | bool createTestFile() | ||
+ | { | ||
+ | int const max = TESTSIZE; | ||
+ | std:: | ||
+ | for (int i = 0; i < TESTSIZE; ++i) | ||
+ | { | ||
+ | int x = rand(); | ||
+ | out.write((char*)& | ||
+ | } | ||
+ | return bool(out) && out.tellp() / sizeof(int) == TESTSIZE; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Ein Puffer muss den ihm zugewiesenen Bereich aus einer Binärdatei komplett verarbeiten: | ||
+ | <code cpp> | ||
+ | bool testBuffer() | ||
+ | { | ||
+ | if (!createTestFile()) return false; | ||
+ | std:: | ||
+ | if (!in) return false; | ||
+ | Buffer buffer(& | ||
+ | int count = 0; | ||
+ | while (!buffer.empty()) | ||
+ | { | ||
+ | // log() << buffer.first() << ' '; | ||
+ | ++count; | ||
+ | buffer.next(); | ||
+ | } | ||
+ | return count == TESTSIZE; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Die Ausgabedatei sollte aufsteigend sortiert sein: | ||
+ | <code cpp> | ||
+ | |||
+ | bool isSorted(std:: | ||
+ | { | ||
+ | std:: | ||
+ | int x, y; | ||
+ | !in.read((char*) &x, sizeof(int)); | ||
+ | while (in.read((char*) &y, sizeof(int))) | ||
+ | { | ||
+ | // log() << x << ' '; | ||
+ | if (x > y) return false; | ||
+ | x = y; | ||
+ | } | ||
+ | // log() << x << ' | ||
+ | return true; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | In den Testrahmen wird die Zeitmessung eingebaut: | ||
+ | <code cpp> | ||
+ | void demo() | ||
+ | { | ||
+ | using namespace std; | ||
+ | clock_t begin = clock(); | ||
+ | srand(time(nullptr)); | ||
+ | log() << " | ||
+ | log() << "N = " << TESTSIZE << ' | ||
+ | log() << "Block = " << BLOCKSIZE << ' | ||
+ | log() << " | ||
+ | assert(BUFFERSIZE <= BLOCKSIZE); | ||
+ | log() << " | ||
+ | assert(testBuffer()); | ||
+ | clock_t start = clock(); | ||
+ | |||
+ | assert(run(" | ||
+ | |||
+ | clock_t stop = clock(); | ||
+ | log() << "check sorted data\n"; | ||
+ | assert(isSorted(" | ||
+ | log() << "test result: success\n"; | ||
+ | log() << double(stop - start) / CLOCKS_PER_SEC << " seconds for n way sort\n"; | ||
+ | clock_t end = clock(); | ||
+ | log() << double(end - begin) / CLOCKS_PER_SEC << " seconds incl. start-up & verification\n"; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Das Programm kann wahlweise als Demo oder zum Sortieren vorhandener Binärdateien genutzt werden. | ||
+ | <code cpp> | ||
+ | int main(int argc, char* argv[]) | ||
+ | { | ||
+ | if (argc == 3) run(argv[2], | ||
+ | else | ||
+ | { | ||
+ | demo(); | ||
+ | log() << " | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | ====== Uhrenvergleich ====== | ||
+ | Das Programm wurde mittels | ||
+ | g++ -O3 sort1mio.cpp | ||
+ | (bestmögliche Optimierung) mit MinGW GCC Version 4.6 64bit | ||
+ | übersetzt und auf einer AMD Turion X2 2.1GHz unter Windows 7 64bit getestet. | ||
+ | Der Programmlauf mit Testrahmen ergab Laufzeiten von 0,8 Sekunden (Zeitmittel aus 4 Läufen). | ||
+ | Die eigentliche Sortierroutine benötigte davon 0,4 Sekunden. | ||
+ | Die optimale Puffergröße scheint bei 1024 Ganzzahlen, also 4kB zu liegen. | ||
+ | Kleinere Puffergrößen (512 Byte) führen zu 0,2 Sekunden langsameren Läufen. | ||
+ | Größere Puffer führen zu einer leichten Verlangsamung. | ||
+ | |||
+ | Auf der gleichen Maschine benötigte das oben erwähnte | ||
+ | [[http:// | ||
+ | unter Python 3.2 mit der von diesem Testprogramm erzeugten Datei test.dat 7 Sekunden für einen Lauf. | ||
+ | Die Sortierergebnisse beider Programme wurden mit diff verifiziert. | ||
+ | |||
+ | ====== Zusammenfassung ====== | ||
+ | Die Lösung in C++ umfasst ca. 150 Quelltextzeilen (ohne Testrahmen). | ||
+ | Das Pythonprogramm ist durch die Nutzung vorgefertigter Module | ||
+ | (array für Binärdateizugriff und Pufferung, heapq für das n-Wege-Sortieren) | ||
+ | erheblich kürzer. | ||
+ | |||
+ | Überraschend (?) ist die ca. 20fache Laufzeit des Pythonprogramms. | ||
+ | Nicht der Abarbeitungsgeschwindigkeit wegen ist Python | ||
+ | [[http:// | ||
+ | geworden, ihre Qualitäten liegen auf anderen Gebieten. (No language wars please!) | ||
+ | |||
+ | ===== Anmerkung ===== | ||
+ | Vor einigen Jahren war ich verblüfft von der Aussage, | ||
+ | Java sei mittlerweile schneller als C++, | ||
+ | nachzulesen in [Cay Horstmann: Core Java 2, Band 2 - Expertenwissen. | ||
+ | Deutsche Ausgabe, Addison-Wesley, | ||
+ | Das angegebene Programm, ein Primzahlsieb des Eratosthenes, | ||
+ | lief tatsächlich dreimal schneller als das gleich implementierte Programm in C++ | ||
+ | --- solange man C++ ohne Optimierung übersetzte! | ||
+ | Mit der Option -O3 beim GCC bzw. beim Wechsel von Debug- zur Releasekonfiguration in Visual C++ | ||
+ | ist das entstandene Programm etwa zehnmal schneller als vorher. | ||
+ | Neu war mir das nicht. Erstaunlich war eher, | ||
+ | dass der Verfasser mehrerer guter Bücher zu C++ und Java dies nicht beachtet hatte. | ||
+ | (Wollte er es nicht wahrhaben, da das Buch für die Firma Sun entstand?) | ||
anwenden/sort1mio.txt · Zuletzt geändert: 2020-07-26 18:34 von 127.0.0.1