Benchmark

Ziel des Benchmarks ist es, möglichst viele poissonverteilte Zufallszahlen in möglichst kurzer Zeit zu erzeugen. Dazu treten die Algorithmen in den folgenden Geschmacksrichtungen zum Benchmark an:

1. uni: Zählen mit gleichverteilten Zufallsvariablen
   (Knuth)
2. exp: Zählen mit exponentiell verteilten Zufallsvariablen
   (Selbstbau)
3. rou: Verhältnis gleichverteilter Zufallsvariablen
   (Numerical Recipes)

Dazu betrachten wir sowohl Poissonverteilungen mit kleinen als auch mit großen Erwartungswerten. Meine Vermutung ist, dass die Zählmethoden für kleine Erwartungswerte effizient sind (uni, exp), aber die Ratio-of-Uniforms-Methode (rorouu) bei großen Erwartungswerten die Oberhand gewinnt.

Zählen mit gleichverteilten Zufallsvariablen

Siehe Wikipedia. Ganz habe ich den Algorithmus noch nicht verstanden. Sieht aber sehr ähnlich aus, wie die Methode der Addition von exponentiell verteilten Zufallszahlen. Hier gibt es garantiert eine Verbindung.

Zählen mit exponentiell verteilten Zufallsvariablen

Wir addieren exponentiell verteilte Zufallszahlen auf und zählen mit. Sobald die Summe die Länge des Zeitintervalls überschreitet, geben wir die Zahl der Summanden zurück. Einfach aber teuer.

Verhältnis gleichverteilter Zufallsvariablen

Aus den Numerical Recipes. Code wurde übernommen, allerdings derart modifiziert, dass auch für kleine Parameter (< 5) der Poissonverteilung die Ratio-of-Uniforms-Methode angewendet wird. Diese Modifikation wird sich in den Ergebnissen niederschlagen.

Ergebnisse

g++ -O2 benchmark.cpp -I . -o benchmark
./benchmark
Numbers generated per algorithm: 1000000
Expected value: 1
    method       mean   time [s]
       uni      1.000      0.130
       exp      0.998      0.300
       rou      1.036      0.310


Numbers generated per algorithm: 1000000
Expected value: 2
    method       mean   time [s]
       uni      2.001      0.140
       exp      2.000      0.460
       rou      2.008      0.310


Numbers generated per algorithm: 1000000
Expected value: 4
    method       mean   time [s]
       uni      3.999      0.190
       exp      3.999      0.750
       rou      4.000      0.300


Numbers generated per algorithm: 1000000
Expected value: 8
    method       mean   time [s]
       uni      8.000      0.290
       exp      8.000      1.340
       rou      8.001      0.300


Numbers generated per algorithm: 1000000
Expected value: 16
    method       mean   time [s]
       uni     16.002      0.470
       exp     15.996      2.440
       rou     16.000      0.220


Numbers generated per algorithm: 1000000
Expected value: 32
    method       mean   time [s]
       uni     32.007      0.820
       exp     32.001      4.710
       rou     31.996      0.220


Numbers generated per algorithm: 1000000
Expected value: 64
    method       mean   time [s]
       uni     63.982      1.530
       exp     64.009      9.270
       rou     63.995      0.210

Quelltext

benchmark.zip