I think the bubble sort would be the wrong way to go.

– Barack Obama

Vor kurzem stieß ich auf ein YouTube-Video (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 Artikel der New York Times. Einiges deutet darauf hin, dass die Frage auf den Blog-Eintrag eines prominenten Google-Mitarbeiters anspielt: Guido van Rossum, Erfinder von Python, beantwortet darin diese Frage "Pythonic way". 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?

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.

1. Die Datenquelle wird blockweise in den Hauptspeicher geladen, sortiert, und die sortierten N Blöcke in eine temporäre Datei geschrieben.
2. Ein 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

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.

#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;
}

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.

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_;
};

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.

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;
}

Die eigentliche Sortierroutine bestimmt einen Temporärdateinamen und sorgt dafür, diese Datei nach Gebrauch zu löschen.

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;
}

Eine Datei mit Zufallszahlen wird erzeugt:

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;
}

Ein Puffer muss den ihm zugewiesenen Bereich aus einer Binärdatei komplett verarbeiten:

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;
}

Die Ausgabedatei sollte aufsteigend sortiert sein:

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;
}

In den Testrahmen wird die Zeitmessung eingebaut:

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";
}

Das Programm kann wahlweise als Demo oder zum Sortieren vorhandener Binärdateien genutzt werden.

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;
}

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

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 Sprache des Jahres 2010 geworden, ihre Qualitäten liegen auf anderen Gebieten. (No language wars please!)

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