Complexity matters

Wieso gibt es eigentlich verschiedene Datenstrukturen, wenn man doch eigentlich auch alles mit Listen oder ähnlichem erschlagen könnte? Das Stichwort lautet "Komplexität": verschiedene Operationen brauchen verschieden lang. Nicht bezüglich der absoluten Zeit, sondern bezüglich der Frage wie schnell die Laufzeit einer Operation mit der Anzahl an Elementen in der Datenstruktur wächst.

Video

Quellcode

#include <iostream>
#include <set>
#include <vector>
#include <boost/date_time/posix_time/posix_time.hpp>

int main()
{
  int retries = 1000;
  
  for (int max = 1; max < 1048577;  max *= 2) {
    std::set<int> iset;
    std::vector<int> ivec;
    
    std::cerr << "@" << max << " Elemente:\n";
    
    for (int i = 0; i < max; ++i) {
      iset.insert(i);
      ivec.push_back(i);
    }
    
    boost::posix_time::ptime before1 = boost::posix_time::microsec_clock::local_time();
    for (int j = 0; j < retries; ++j) {
      int x = *iset.find(j*max/retries-1);
    }
    boost::posix_time::ptime after1 = boost::posix_time::microsec_clock::local_time();
    std::cerr << "   std::set: ø" << 
		 static_cast<double>((after1-before1).total_microseconds())/retries << 
		 " µs pro Suche\n";

    boost::posix_time::ptime before2 = boost::posix_time::microsec_clock::local_time();
    for (int j = 0; j < retries; ++j) {
      int x = *std::find(ivec.begin(), ivec.end(), j*max/retries-1);
    }
    boost::posix_time::ptime after2 = boost::posix_time::microsec_clock::local_time();
    std::cerr << "   std::vector: ø" << 
		 static_cast<double>((after2-before2).total_microseconds())/retries << 
		 " µs pro Suche\n";
  }
}

Erklärung

C++ bietet in der Standardbibliothek einen Algorithmus namens std::find: zwei Iteratoren und ein Vergleichswert als Parameter und man kann in allem, was Iteratoren bietet, nach Werten suchen. Warum also extra ein std::set::find? Ganz einfach: da std::find nichts über die Datenstruktur hinter den beiden Iteratoren weiß, ist es ganz einfach implementiert:

template <typename IterT, typename ValueT> IterT std::find(IterT begin, IterT end, ValueT const &value)
{
    while (begin != end) {
       if (*begin == value) {
           return begin;
       }
       ++begin;
    }
    return end;
}

Simpel, aber möglicherweise ineffizient. Solange man aber keine zusätzlichen Informationen über die zugrundeliegende Datenstruktur (bspw. Sortierung) hat, geht's nunmal nicht anders. Damit ist std::find ein klassisches Beispiel für einen O(n)-Algorithmus: im Mittel wird der gesuchte Wert nach n/2 Schritten gefunden (mit n == Anzahl der Elemente im zugrundeliegenden Bereich). Verdoppelt man also n, dann verdoppelt sich auch die Anzahl der Suchschritte.

Ganz anders std::set::find: die Datenstruktur weiß natürlich, dass sie die zugrundliegenden Elemente in einem Rot-Schwarz-Baum sortiert hat. Daher kann sie viel effizienter suchen und kommt mit maximal log2(n) Schritten aus - ein perfektes Beispiel für einen O(log n)-Algorithmus. Das sieht anfangs nicht so besonders dramatisch aus. Wie man aber am Bild unten sehen kann: mit steigender Elementanzahl driften die beiden Varianten massiv auseinander. Bei etwas mehr als 1 Million Elementen ist der Unterschied schon weit über 1:1000. Hierbei geht es wohlgemerkt um eine einzelne Suche. Bei O(n) verlängert sich eben jeder einzelne Suchschritt massiv. Da man tendenziell mit mehr Elementen in einer Datenstruktur auch mehr Lookups macht (wozu sollte man sonst so viele speichern?), potenziert sich das Problem auch noch: nicht nur dauert jeder einzelne Aufruf länger, insgesamt macht man (möglicherweise) auch noch mehr Aufrufe. Quasi ein Rezept für die Katastrophe.

Laufzeit eines Lookups von std::find (rot) ggü. std::set::find (blau). Die x-Achse zeigt die Anzahl der Elemente in der Datenstruktur, die y-Achse die Zeitdauer pro Lookup in µs.