Manchmal ist der Platz entscheidend

Beim Programmieren geht es nicht immer nur um die Laufzeitkomplexität. Oft spielt auch der Platzbedarf eine Rolle. Vor allem, wenn man viele Objekte im Speicher behalten will, kommt es manchmal darauf an, wieviel eine bestimmte Datenstruktur intern noch braucht. std::set kann da besonders gierig sein: mindestens 2 Pointer pro Objekt zusätzlich stehen zu Buche.

Das Video basiert auf einem Artikel von Matt Austern: "Why you shouldn't use set (and what you should use instead)".

Video

Quelltext

#include <iostream>
#include <vector>
#include <algorithm>

#include <boost/date_time/posix_time/posix_time.hpp>

int main()
{
  unsigned int size = 2000000;
  std::vector<unsigned int> ivec(size);
  for (unsigned int i = size; i > 1; --i) {
    ivec.push_back(i);
  }

  boost::posix_time::ptime before1 = boost::posix_time::microsec_clock::local_time();
  std::sort(ivec.begin(), ivec.end());
  boost::posix_time::ptime after1 = boost::posix_time::microsec_clock::local_time();
  std::cerr << static_cast<double>((after1-before1).total_microseconds())/1000000 
    << " s zum sortieren\n";
  
  boost::posix_time::ptime before2 = boost::posix_time::microsec_clock::local_time();
  for (int i = 0; i < 1000; ++i) {
    unsigned long long val = i;
    val *= size;
    val /= 1000;
    auto it = std::binary_search(ivec.begin(), ivec.end(), val);
  }
  boost::posix_time::ptime after2 = boost::posix_time::microsec_clock::local_time();
  
  std::cerr << static_cast<double>((after2-before2).total_microseconds())/1000 
    << " µs pro Suche\n";
}

Erkärung

Das Problem mit std::set: um seine interne Datenstruktur aufzubauen benötigt es mindestens zwei Pointer pro Element. Meist kommen noch ein paar weitere Verwaltungsinformationen dazu. Wenn man relativ große Objekte speichern will, macht das kaum einen Unterschied. Geht es aber um viele kleine Objekte, dann kann das zum Problem werden. Im Beispiel hier werden Integer gespeichert. Jeder Integer ist auf meiner Platzform 4 Byte groß. Die beiden zusätzlich notwendigen Pointer sind allerdings schon je 8 Byte. 400% Overhead sind eine gewaltige Hausnummer, die zwischen "machbar" und "nicht machbar" unterscheiden kann. Notwendig ist dieser Aufwand, weil std::set nicht nur schnell lesen, sondern auch schnell schreiben kann. Beide Operationen laufen in O(log n) im Verhältnis zur Anzahl der gespeicherten Elemente. Wenn man hier die Anforderungen etwas niedriger ansetzt, dann kommt man ggf. auch zum Ziel und spart dabei eine Menge Platz.

Grundgedanke ist der folgende: wenn unsere Menge an Elemente sehr viel häufiger durchsucht, als verändert wird, dann lohnt es sich, die Veränderung teurer zu machen, um das Suchen schnell zu halten. Die suche in O(log n) ist nämlich auch dann möglich, wenn wir mit std::vector arbeiten. Die einzige Voraussetzung: die Elemente im vector müssen sortiert sein. Dann kann man nämlich das Verfahren der binären Suche anwenden. Genau wie std::set schließt die binäre Suche in jedem Schritt die Hälfte der noch zu durchsuchenden Elemente aus. Das gelingt, indem man immer in der Mitte des zu durchsuchenden Bereichs einsteigt und prüft, ob das gesuchte Elemente in der unteren oder oberen Hälte liegen muss. Durch dieses schnelle Ausschließen viele Elemente wird die Suche ebenso in O(log n) möglich. Der Preis dafür: die Elemente müssen sortiert sein.

Das Beispiel oben führt die entsprechenden Techniken vor. Der vector wird in falscher Reihenfolge befüllt (könnte aber bspw. auch zufällig sein). Danach durchlaufen wir eine Initialisierungsphase, indem std::sort den vector sortiert. Das geschieht in-place, benötigt also keinen extra Speicher. Dieser Schritt dauert. Im Video über 4 Sekunden. Hier investieren wir quasi den zusätzlichen Aufwand, den wir später beim Suchen einsparen. Danach verwenden wir den Algorithmus std::binary_search, um den nun sortierten vector zu durchsuchen. std::binary_search hat eine kleine Eigenart, die es zu beachten gilt: er nimmt grundsätzlich jede Art von ForwardIterator. Wir könnten den Algorithmus also auch auf eine std::list loslassen. Das Problem: der Standard garantiert O(log n) nur für die Anzahl der Vergleiche. Wenn wir einen normalen ForwardIterator wie von std::list verwenden, dann muss der sich allerdings von einem Vergleich zum nächsten mühsam hochzählen, statt einen Sprung in O(1) zu machen. Damit bekommen wir zwar O(log n) Vergleiche, aber O(n) Zählschritte, die dann das Ergebnis dominieren. Richtig effizient wird std::binary_search also nur mit RandomAccessIterator, wie in std::vector bereitstellt. Hier ist der Sprung zur nächsten Vergleichsstelle in O(1) gemacht und damit vernachlässigbar.

Wofür nun der ganze Aufwand? Ganz einfach: Platzersparnis. std::vector hat quasi keinen Overhead bzgl. des Platzes. Die Elemente liegen alle direkt hintereinander im Speicher (auch das ist vom Standard garantiert). Wir haben also den Aufwand in der Initialisierungsphase für die Ersparnis des Platzes investiert. Lohnt sich natürlich nur, wenn der Anwendungsfall vorsieht, dass selten geschrieben, aber sehr oft gelesen wird. Im Idealfall einmal initialisieren und dann nur noch suchen.