Definiton des Interfaces

/* generator for gaussian deviates (Box-Mueller) */ #include "RndUniform.h" class RndBox { public: RndBox(); /* move to the next element of the pseudo random sequence */ void next(); /* pseudo random deviate from the gaussian distribution */ double lastGaussian() const; private: void generate(); void randPoint(); double randUniv(); double x, y, product, first, second; bool available; RndUniform random; };

Implementation

Die Implementation muss das Interface kennen, steht aber typischerweise in einer eigenen Implementationsdatei:

#include "RndBox.h" #include <cmath> RndBox::RndBox() : available(false) { } void RndBox::next() { if (available) available = false; else generate(); } double RndBox::lastGaussian() const { return available ? first : second; } /* generate two pseudo random deviates from a gaussian distribution */ void RndBox::generate() { randPoint(); double p = std::sqrt((-2 * std::log(product)) / product); available = true; first = p * x; second = p * y; } /* point from a uniform distribution on the area of the unit circle */ void RndBox::randPoint() { do { x = randUniv() * 2 - 1; y = randUniv() * 2 - 1; product = x * x + y * y; } while (product > 1.0); } /* internal wrapper for uniform distribution on unit interval */ double RndBox::randUniv() { random.next(); return random.lastUniform(); }

Na, würde es jemanden reizen eine STL Implementation beizusteuern?

Überschlagsmäßig würde das wohl so aussehen:

template <class RandomSource> class NumberCacheIterator { operator-> // ... operator++ // ... operator* // ... }

Welchen Vorteil soll eine Implementation als Template gegenüber einer Implementation mit einer abstrakten Basisklasse haben, von der der konkrete Batch-Generator abgeleitet ist? Die faktische Definition von Interfaces durch Template-Parameter ist eher eine Schwäche als eine Stärke von C++.

Man wird dadurch nicht zu einer virtuellen Funktion gezwungen. Siehe auch SoftwareOptimierung Regel 1.

Nebenbei: Kennt jemand einen zweiten Algorithmus, der Zufallszahlen aus einer Verteilung paarweise oder tupelweise erzeugt und für den es sich lohnen würde, einen allgemeinen Cache zu implementieren, weil diese sinnvoll auch einzeln verbraucht werden können?

In TheArtOfComputerProgramming implementiert DonKnuth einen "lagged Fibonacci RNG" mit einer Funktion, die beliebig große Arrays mit Zufallszahlen füllt, jedoch mindestens 100. Außerdem empfiehlt er zur Verbesserung der Eigenschaften der Zufallszahlen, von je 1009 Zahlen nur die ersten 100 zu benutzen. Eine Implementierung in einem großen Array liegt nahe.

Die STL benutzt Templates und Iteratoren, aber das macht C++-Code, der Templates und Iteratoren benutzt, noch nicht zu einer STL-Implementation. Die Idee hinter der STL ist, eine Darstellung von Standard-Algorithmen und Standard-Datenstrukturen zu finden, die diese entkoppelt.

Datenstrukturen sollen ohne Änderungen am Code der Implementation eines Algorithmus austauschbar werden. Dies ist zumindest teilweise gelungen. Als Beispiel für eine nicht gelungene Entkopppelung mag std::list::sort dienen. Die Abstraktion der Schnittstelle eines Pseudozufallszahlengenerators mit überladenen Operatoren operator++ und unärem operator* ist möglich, aber um operator-- wirklich vernünftig zu implementieren schafft man einen Überbau, der erst einmal durch ein sinnvolles Anwendungsbeispiel gerechtfertigt sein sollte.

Ja, da war ich etwas übereifrig mit dem operator--.

Die Zeiger-Abstraktion für Iteratoren ist im Fall der STL dadurch gerechtfertigt, dass so Algorithmen auch auf eingebaute Arrays angendet werden können.

Wenn solche Iteratoren auf einer Zufallszahlenfolge in Standardalgorithmen eingesetzt werden sollen, wie z.B.

std::vector<double> X; BoxGenerator<double> Z(U); std::copy(Z.begin(), Z.generate(8192), std::back_inserter(X));

oder vielleicht

BoxGenerator<double> Z(U, 7); double chi = std::accumulate(Z.begin(), Z.end(), add_squared);

kann die Logik aber nicht alleine im Iterator liegen. Die Darstellung einer zu lesenden Folge in der STL ist immer ein Iteratorpaar. --KurtWatzka

Dann sind aber die Algorithmen der STL nicht auf einen solchen Behälter anwendbar, und damit ist es auch nicht so sinnvoll, die Zeiger-Abstraktion der STL für einen Zufallszahlengenerator zu verwenden. Man wird ja wohl über einen solchen Iterator nicht in die Pseudozufallszahlenfolge schreiben, sondern aus ihr lesen wollen. --kw