no way to compare when less than two revisions

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

@@ 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://www.youtube.com/watch?v=k4RRi_ntQc8|Obama Computer Science Question]])
+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://www.nytimes.com/2007/12/02/business/02digi.html?_r=1&_r=2&n=Top/Reference/Times%20Topics/People/R/Richardson,%20Bill&oref=slogin|Artikel]]
+der New York Times. Einiges deutet darauf hin, dass die Frage auf den
+[[http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html|Blog-Eintrag]]
+eines prominenten Google-Mitarbeiters anspielt: Guido van Rossum, Erfinder von Python,
+beantwortet darin diese Frage "Pythonic way".
+[[http://stackoverflow.com/questions/134158/how-would-you-sort-1-million-32-bit-integers-in-2mb-of-ram|Stack Overflow]]
+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, einen schnellen Sortieralgorithmus vorausgesetzt.
+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://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge|N-Wege-Mischen]] erzeugt die sortierte Ausgabedatei.
+  |.oO0*|o0*.O|O.*o|  Eingabedatei
+     v      v    v
+  |.*o0O|.*o0O|.*oO|  sortierte Blöcke
+    \    |     /
+    jeweils kleinstes Element finden --> |.......> Ausgabedatei
+====== 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 <algorithm>
+#include <deque>
+#include <fstream>
+#include <cassert>
+#include <string>
+#include <iostream>
+#include <cstdlib>
+#include <queue>
+#include <cstdio>
+#include <ctime>
+size_t const TESTSIZE = 1000000;
+size_t const BLOCKSIZE = 100000;
+size_t const BUFFERSIZE = 1024;
+std::ostream& log() // for Debugging
+{
+  return std::cerr;
+}
+size_t partition(std::string infile, std::string outfile)
+{
+  std::ifstream in (infile.c_str(), std::ios::in  |std::ios::binary);
+  std::ofstream out(outfile.c_str(), std::ios::out|std::ios::binary);
+  size_t written = 0;
+  int block[BLOCKSIZE];
+  size_t const size = sizeof(int);
+  size_t start = in.tellg();
+  while (in.read((char*)block, sizeof(block)))
+  {
+    size_t stop = in.tellg();
+    size_t n = (stop - start) / size;
+    std::sort(block, block + n);
+    if (n) out.write((char*)block, n * size);
+    written += n;
+    start = stop;
+  }
+  return written;
+}
+</code>
+===== 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::ifstream* file, size_t start, size_t end)
+  : 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()  // Pufferunterlauf
+  {
+    size_t const block = sizeof(int);
+    start_ += BUFFERSIZE;
+    if (start_ >= end_) return;
+    // log() << "read buffer pos = " << start_ << '\n';
+    // log() << "end  buffer pos = " << end_ <<'\n';
+    assert(file_);
+    file_->seekg(start_ * block, std::ios::beg);
+    int buf[BUFFERSIZE];
+    size_t n = std::min(BUFFERSIZE, end_-start_);
+    file_->read((char*)buf, n * block);
+    n = file_->tellg() / block - start_;
+    data_= std::deque<int>(buf, buf + n);
+  }
+private:
+  std::ifstream* file_;
+  std::deque<int> data_;
+  size_t start_;
+  size_t end_;
+};
+</code>
+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::ifstream in (infile.c_str(), std::ios::in  |std::ios::binary);
+  std::ofstream out(outfile.c_str(), std::ios::out|std::ios::binary);
+  if (!in || !out) return false;
+  std::vector<Buffer> buffers;  // 1 buffer per block
+  for (size_t i = 0; i < n; i+= BLOCKSIZE)
+  {
+    Buffer buffer(&in, i, std::min(n, i + BLOCKSIZE));
+    if (!buffer.empty()) buffers.push_back(buffer);
+  }
+  log() << buffers.size() << " way sort, buffers created\n";
+  typedef std::pair<int,int> pair;
+  std::priority_queue<pair, std::vector<pair>, std::greater<pair>> queue;
+  for (int i = 0; i < buffers.size(); ++i)
+  {
+    Buffer& buffer = buffers[i];
+    queue.push(pair(buffer.first(), i));
+  }
+  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(), bufNo));
+  }
+  if (count)
+  {
+    out.write((char*) outbuffer, count*sizeof(int));
+    written += count;
+  }
+    return written == n;
+}
+</code>
+Die eigentliche Sortierroutine bestimmt einen Temporärdateinamen
+und sorgt dafür, diese Datei nach Gebrauch zu löschen.
+<code cpp>
+bool run(std::string destination, std::string source)
+{
+  std::string tmp(std::tmpnam(0));
+  log() << "Partition to temp file: " << tmp << '\n';
+  size_t nElements = partition(source, tmp);
+  log() << "n way merge to sorted file\n";
+  bool done = nWayMerge(nElements, tmp, destination);
+  log() << "remove temp file\n";
+  std::remove(tmp.c_str());
+  return done && nElements != 0;
+}
+</code>
+===== Testrahmen =====
+Eine Datei mit Zufallszahlen wird erzeugt:
+<code cpp>
+bool createTestFile()
+{
+  int const max = TESTSIZE;
+  std::ofstream out("test.dat", std::ios::out|std::ios::binary);
+  for (int i = 0; i < TESTSIZE; ++i)
+  {
+    int x = rand();
+    out.write((char*)&x, sizeof(int));
+  }
+  return bool(out) && out.tellp() / sizeof(int) == TESTSIZE;
+}
+</code>
+Ein Puffer muss den ihm zugewiesenen Bereich aus einer Binärdatei komplett verarbeiten:
+<code cpp>
+bool testBuffer()
+{
+  if (!createTestFile()) return false;
+  std::ifstream in ("test.dat", std::ios::in|std::ios::binary);
+  if (!in) return false;
+  Buffer buffer(&in, 0, TESTSIZE);
+  int count = 0;
+  while (!buffer.empty())
+  {
+    // log() << buffer.first() << ' ';
+    ++count;
+    buffer.next();
+  }
+  return count == TESTSIZE;
+}
+</code>
+Die Ausgabedatei sollte aufsteigend sortiert sein:
+<code cpp>
+bool isSorted(std::string file)
+{
+  std::ifstream in(file.c_str(), std::ios::in|std::ios::binary);
+  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 << '\n';
+  return true;
+}
+</code>
+In den Testrahmen wird die Zeitmessung eingebaut:
+<code cpp>
+void demo()
+{
+  using namespace std;
+  clock_t begin = clock();
+  srand(time(nullptr));
+  log() << "random numbers up to " << RAND_MAX << '\n';
+  log() << "N = " << TESTSIZE << '\n';
+  log() << "Block = " << BLOCKSIZE << '\n';
+  log() << "Buffer = " << BUFFERSIZE << '\n';
+  assert(BUFFERSIZE <= BLOCKSIZE);
+  log() << "Create test data\n";
+  assert(testBuffer());
+  clock_t start = clock();
+  assert(run("sorted.dat", "test.dat"));
+  clock_t stop = clock();
+  log() << "check sorted data\n";
+  assert(isSorted("sorted.dat"));
+  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";
+}
+</code>
+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], argv[1]);
+  else
+  {
+    demo();
+    log() << "Command:\n\tprog sourcefile destinationfile\n";
+  }
+  return 0;
+}
+</code>
+====== 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://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html|Python-Programm]]
+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://www.tiobe.com/index.php/content/paperinfo/tpci/index.html|Sprache des Jahres 2010]]
+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, München 2005, S. 187].
+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?)