(0) exportieren Drucken
Alle erweitern
Erweitern Minimieren
Dieser Artikel wurde noch nicht bewertet - Dieses Thema bewerten.

Zufälligkeit beim Testen

Veröffentlicht: 11. Sep 2006

Von Dr. James McCaffrey

Die Generierung und Verwendung von Zufallstestfalldaten stellt eine wesentliche Fähigkeit beim Testen von Software dar. Obwohl die meisten Testfalldaten aus bestimmten Eingaben im getesteten System und bestimmten erwarteten Werten/Status bestehen, ist es Standard, das System einem Test durch die Eingabe von Zufallstestfalldaten zu unterziehen. In der Regel wird dies durchgeführt, um zu sehen, ob Sie einen Crash verursachen oder einen Ausnahmefehler auslösen können, indem Sie die Anwendung mit vielen verschiedenen Eingaben füttern. Im Artikel dieses Monats lernen Sie vier allgemeine Aufgaben bei der Behandlung von Zufallstestdaten in einer Microsoft ® .NET Framework-Umgebung kennen:

  • Generieren von Pseudozufallszahlen (Knuth-Algorithmus)

  • Analysieren eines Musters auf Zufälligkeit (Wald-Wolfowitz-Test)

  • Zufälliges Wiedergeben einer Liste von Elementen (Fisher-Yates-Algorithmus)

  • Generieren Gaußscher Zahlen (Box-Muller-Algorithmus)

Laden Sie den Code zu diesem Artikel herunter: TestRun2006_09.exe (162 KB)

Betrachten Sie das Beispiel in Abbildung 1. Der erste Teil der Ausgabe enthält die Ergebnisse einer einfachen Generierung von Zahlen, bei der das Random-Objekt von .NET Framework verwendet wird. Auch wenn Sie mit dieser Technik vermutlich schon vertraut sind, soll hier darauf eingegangen werden, wie sich allgemeine Fehlerquellen vermeiden lassen. Im zweiten Teil der Ausgabe wird eine sehr nützliche, doch wenig bekannte Methode der Analyse eines Musters von beliebigen Symbolen auf Zufälligkeit behandelt. Diese Methode ist nicht auf das Testen begrenzt und hat in der Softwareentwicklung allgemein viele Anwendungsmöglichkeiten. Im dritten Teil der Abbildung 1 wird das Ergebnis angezeigt, das Sie beim der zufälligen Wiedergabe einer Liste von Elementen erhalten. Dies ist gar nicht so einfach wie erwartet.

Abbildung 1: Demonstration der Zufälligkeitsmethoden
Abbildung 1 Demonstration der Zufälligkeitsmethoden

Es wird detailliert geschildert, warum viele Implementierungen zur zufälligen Wiedergabe zwar richtig zu sein scheinen, im Grunde jedoch völlig inkorrekt sind. Im letzten Teil der Ausgabe in Abbildung 1 wird das Ergebnis bei der Generierung einer Reihe von Zahlen angezeigt, die gemäß der normalen Glockenkurve verteilt werden. Abgesehen davon, dass es sich hier um eine überaus nützliche Methode handelt, sind die Details bei der Implementierung dieses Algorithmus an sich sehr interessant und werden Ihre persönliche Codierungs-Toolbox bereichern.

Auf dieser Seite

Generierung normalverteilter Zufallszahlen
Analysieren eines Musters auf Zufälligkeit
Zufälliges Wiedergeben einer Liste von Elementen
Generieren normaler/Gaußscher Zahlen
Zusammenfassung
Der Autor

Generierung normalverteilter Zufallszahlen

Die grundlegendste Aufgabe bei der Generierung eines Zufallstestfalls besteht in der Generierung einer Zufallszahl, sei es eine Ganz- oder Gleitkommazahl, in einem bestimmten Bereich. Dies geschieht meist über die Klasse „System.Random“. Betrachten Sie diesen Code:

Random objRan = new Random(5);
int n = objRan.Next(7);
Console.WriteLine("A random int in the range [0,6] is " + n);

n = objRan.Next(3, 13);
Console.WriteLine("A random int in the range [3,12] is " + n);

Es wird ein Random-Objekt instanziiert und ein Ausgangswert eingefügt (in diesem Beispiel ist dieser auch „Seed Value“ genannter Wert 5). Dieser Wert legt den Ausgangspunkt einer Zahlenfolge fest, die viele Merkmale mit echten Zufallszahlen gemeinsam haben. Da die Abfolge deterministisch ist (die Zahlen werden von einer mathematischen Formel generiert, die als Eingabe den Ausgangswert oder vorangehende Zahlen in der Abfolge verwendet), handelt es sich bei den von „System.Random“ generierten Zahlen im Grunde um Pseudozufallszahlen, sie werden jedoch in informellen Verwendungen oder in Fällen mit einem unklaren Kontext, wie im vorliegenden Fall, in der Regel als Zufallszahlen bezeichnet. Der Ausgangswert wurde willkürlich gewählt. Wenn der überladene Random-Konstruktor verwendet wird, der keinen Ausgangswert annimmt, wird ein Wert genommen, der sich von der Systemuhr ableitet. Falls Sie Ihre Abfolge von Zufallszahlen in nachfolgenden Testläufen neu erstellen müssen, was meistens der Fall ist, sollten Sie einen Ausgangswert angeben. Die Erörterung von Ausgangswerten für die Generierung von Pseudozufallszahlen, ein wichtiges und komplexes Thema, geht leider über den Rahmen dieses Artikels hinaus.

Am einfachsten lässt sich eine Zufallsganzzahl durch Aufrufen der Methode „Random.Next“ generieren, indem ein einziges Ganzzahlargument eingefügt wird. Der zurückgegebene Wert ist dann die nächste Ganzzahl in der Liste der Pseudozufallszahlen, die größer als oder gleich 0 und kleiner als das Argument ist. Bei dem folgenden Aufruf wird deshalb eine Zahl zwischen 0 und 9 (einschließlich) zurückgegeben, nicht zwischen 0 und 10 (einschließlich):

int n = objRan.Next(10);

Eine Überladung der Random.Next-Methode akzeptiert zwei Ganzzahlargumente und gibt eine Ganzzahl zurück, die größer oder gleich dem ersten Argument und kleiner als das zweite Argument ist. Bei einer Simulierung der Testfalldaten, die dem Ergebnis beim normalen Fall eines Würfels mit sechs Seiten entsprechen, könnte ein Aufruf mit dem Ziel, eine Zufallszahl zwischen 1 und 6 (einschließlich) zu erhalten, folgendermaßen aussehen:

int roll = objRan.Next(1, 7);

Das Erstellen eines aus einem Array willkürlich ausgewählten Elements ist einfach:

string[] items = new string[] { "alpha", "beta", "gamma", "delta" };
Console.WriteLine("A random member of { 'alpha', 'beta', " +
    "'gamma', 'delta' } is " +
    items[objRan.Next(items.Length)] );

Wenn die Größe des Arrays N ist, ergibt der Aufruf „objRan.Next(N)“ einen Rückgabewert, der eine Ganzzahl im Bereich [0, N-1] darstellt, was genau den Indexwerten des Arrays entspricht. Beachten Sie, dass diese Methode außerdem auf ArrayList-Objekte und prinzipiell auf jede 0-basierte indizierte Auflistung angewendet werden kann.

Im Hintergrund verwenden die überladenen Random.Next-Methoden die Knuth-Methode zur Generierung von Pseudozufallszahlen. Diese Methode wird auch als die „subtraktive Methode“ bezeichnet. Knuth hat diesen Algorithmus in „Seminumerical Algorithms“, Band 2 von The Art of Computer Programming (Addison-Wesley, 1981) veröffentlicht. Das Generieren von normalverteilten Pseudozufallszahlen ist ziemlich komplex, doch erfreulicherweise übernimmt das .NET Framework das Implementieren des Knuth-Algorithmus für Sie.

Ungefähr zeitgleich mit der Entwicklung von .NET Framework entdeckten Matsumoto und Nishimura einen neuen Algorithmus zur Generierung von Pseudozufallszahlen. Dieser Algorithmus, der gemeinhin als der Mersenne-Twister bekannt ist, hat ältere Algorithmen zur Generierung von Pseudozufallszahlen aufgrund seiner allgemein besseren Leistung und mathematischen Merkmale schnell ersetzt. Siehe „Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator“ in ACM Transactions on Modeling and Computer Simulation, Band 8, Nr. 1, Januar 1998.

Das Generieren einer Pseudozufallsgleitkommazahl ähnelt der Generierung einer Pseudozufallsganzzahl. Betrachten Sie diesen Code:

double x = (6.25 * objRan.NextDouble()) + 1.50;
Console.WriteLine("A random double in the range [1.50,7.75) is " +
                  x.ToString("0.00"));

Der Aufruf von „Random.NextDouble“ gibt eine Zahl zurück, die größer oder gleich 0,0 und kleiner als 1,0 ist. Zur Generierung einer Zahl vom Typ Gleitkommazahl im Bereich [low, high), wobei die Bracket-Parens-Schreibweise größer als oder gleich „low“ und kleiner als „high“ bedeutet, können Sie die folgende Miniformel verwenden:

double result = ((high-low) * objRan.NextDouble()) + low;

Da die meisten Gleitkommazahlen mit Ausnahme von 0,0 Annäherungen darstellen, können Sie eigentlich keine Zahl vom Typ Gleitkommazahl im inklusiven Bereich [low, high] generieren und müssen dafür einen exklusiven Bereich [low, high) verwenden. Diese Formel ist fast identisch mit der in der Überladung von „Next“ verwendeten Formel, die einen Ganzzahlbereich zulässt – mit dem Unterschied, dass das Ergebnis in eine Ganzzahl umgewandelt wird.

Analysieren eines Musters auf Zufälligkeit

Gelegentlich muss das Muster einer Testfalleingabe oder -ausgabe auf Anzeichen dafür überprüft werden, dass die Daten nach dem Zufallsprinzip generiert wurden (um z. B. zu überprüfen, ob in einer Glückspielsimulation tatsächlich willkürliche Ergebnisse ausgegeben werden). Dafür gibt es mehrere statistische Methoden, doch die einfachste Methode ist der Wald-Wolfowitz-Test. Dieser Test wird manchmal auch ein „One-Sample-Run-Test“ genannt (wobei „Run“ für eine kontinuierliche Serie derselben Zahl oder desselben Zeichens steht). Der Wald-Wolfowitz-Test gilt für eine Abfolge von zwei Symbolen, zum Beispiel:

A B B A A A B B B A B B

Das Prinzip besagt, dass für eine beliebige Anzahl von zwei Symboltypen in einem Muster, falls diese Symbole zufällig generiert wurden (d.  h. in diesem Beispiel, dass jede Position im Muster mit einer Wahrscheinlichkeit von 50 % ein A oder ein B sein kann), eine erwartete Anzahl von Runs im Muster berechnet werden kann. Ein Muster-Run ist eine Abfolge, bei der die Symboltypen gleich sind. Das oben angegebene Muster enthält also sechs Runs: A, BB, AAA, BBB, A, BB. Wenn die tatsächliche Anzahl von Runs in einem Muster entweder zu groß oder zu klein ist, dann liegt ein Beweis dafür vor, dass dieses Muster nicht nach dem Zufallsprinzip generiert wurde.

Obwohl der Wald-Wolfowitz-Test nur für Muster mit nur zwei Symbolen gilt, können Sie willkürliche Muster oft in eine Wald-Wolfowitz-Form übertragen. Wenn Sie zum Beispiel eine Abfolge von Ganzzahlen wie {7, 9, 3, 4, 1, 6} vorliegen haben, dann können Sie den Durchschnitt (5,0) berechnen und dann die Abfolge auf die Symbole H und L übertragen, wobei H für eine Zahl größer als der Durchschnitt und L für eine Zahl kleiner als der Durchschnitt steht: H H L L L H. Wenn Sie komplexere Muster analysieren müssen, können Sie Tests, wie z. B. den Chi-Quadrat-Test oder den Kolmogorov-Test, verwenden.

Angenommen, n1 ist die Zahl vom ersten Symboltyp, und n2 ist die Zahl vom zweiten Symboltyp. Die erwartete Anzahl von Runs, µ, in einem zufallsgenerierten Muster ist:

µ = 1 + ((2*n1*n2) / (n1 + n2))

und die Varianz, α2, ist angegeben durch:

α2 = ((2*n1*n2) * (2*n1*n2 - n1 - n2)) / ((n1 + n2)2 * (n1 + n2 - 1))

Diese beiden Formeln stammen aus der Wahrscheinlichkeitstheorie. Sie können anhand des Durchschnitts und der Varianz ermitteln, wie wahrscheinlich ein bestimmtes Muster das Ergebnis eines Zufallsvorgangs ist. Angenommen, Sie fangen mit einem Muster von zwei Symbolen an, ausgedrückt als eine Zeichenfolge:

string s = "XOOOXXXXOXXXXXXXOOOOXXXXXXXXXX";

Obwohl Sie die Anzahl von X und O und die Anzahl der Runs im Muster manuell berechnen können, ist es einfacher, wenn das Programm dies erledigt. Zuerst stellen Sie die beiden Symboltypen in der Musterzeichenfolge fest:

char kind1 = s[0], kind2 = s[0];
for (int i = 0; i < s.Length && kind1 == kind2; ++i) 
{
    if (s[i] != kind1) kind2 = s[i];
}

Sie weisen das erste Zeichen der Musterzeichenfolge dem ersten Symboltyp zu, und dann untersuchen Sie die Musterzeichenfolge, bis Sie einen zweiten Symboltyp finden. Anschließend führen Sie zwei einfache Fehlerkontrollen durch, um sicherzustellen, dass Sie mindestens zwei verschiedene Zeichen im Muster festgestellt haben und dass nicht mehr als zwei Zeichen im Muster vorhanden sind:

if (kind2 == kind1)
    throw new Exception("String must have two different types");

for (int i = 0; i < s.Length; ++i)
    if (s[i] != kind1 && s[1] != kind2)
        throw new Exception("String may only have two types");

Falls die Leistungsfähigkeit ein Grund zur Sorge ist, können diese drei Durchläufe durch die Musterzeichenfolge in nur einem Durchlauf ausgeführt werden, was lediglich die Übersichtlichkeit etwas beeinträchtigt.

Nun kann die Zählung der jeweiligen Symboltypen und der Runs in der Musterzeichenfolge erfolgen:

int n1 = 0, n2 = 0, runs = 1;
for (int i = 0; i < s.Length-1; ++i)
{
    if (s[i] == kind1) ++n1;
    else if (s[i] == kind2) ++n2;
    if (s[i+1] != s[i]) ++runs;
}
if (s[s.Length-1] == kind1) ++n1;
else if (s[s.Length-1] == kind2) ++n2;

Sie untersuchen das Muster, beginnend beim ersten Zeichen, bis zum vorletzten Zeichen. Falls das aktuelle Zeichen mit dem Symboltyp übereinstimmt, den Sie zuvor ermittelt haben, inkrementieren Sie den entsprechenden Zähler. Zur Berechnung der Runs in einem Muster nutzen Sie die Tatsache, dass ein Run durch eine Veränderung des Symboltyps gekennzeichnet ist. Wenn das aktuelle Zeichen vom nächsten Zeichen abweicht, wissen Sie, dass ein weiterer Run vorliegt, und inkrementieren den Run-Zähler. Da Sie am vorletzten Zeichen in der Musterzeichenfolge aufgehört haben, beenden Sie den Vorgang, indem Sie das letzte Zeichen untersuchen. Außerdem beginnen Sie die Runs bei Eins statt bei Null, da alle Muster definitionsgemäß mindestens einen Run enthalten.

Der Wald-Wolfowitz-Test gilt nur dann, wenn die Anzahl der jeweiligen Symboltypen im analysierten Muster größer oder gleich acht ist, also kontrollieren Sie dies:

if (n1 < 8 || n2 < 8)
    throw new Exception("n1 and n2 must both be 8 or greater for " +
                        "this test to be meaningful");

An dieser Stelle der Analyse haben Sie die Anzahl der beiden Symboltypen und die tatsächliche Anzahl der Runs im Muster ermittelt. Nun berechnen Sie die erwartete Anzahl der Runs im Muster, falls die beiden Symboltypen nach dem Zufallsprinzip generiert wurden:

double expectedRuns = 1 + ((2.0*n1*n2) / (n1 + n2));

Anschließend berechnen Sie die Varianz der Anzahl von Runs, falls zufallsgeneriert, wie folgt:

double varianceNumerator = (2.0*n1*n2) * (2.0*n1*n2 - N);
double varianceDenominator = (double)((N*N)*(N-1));
double variance = varianceNumerator / varianceDenominator;

Im nächsten Schritt der Analyse wird eine normalisierte z-Teststatistik berechnet:

double z = (R - expectedRuns) / Math.Sqrt(variance);

Die z-Statistik ist gleich der tatsächlichen Anzahl von Runs im Muster minus die erwartete Anzahl von Runs im Muster, geteilt durch die Standardabweichung der erwarteten Anzahl von Runs (bei der es sich um die Quadratwurzel der Varianz handelt). Das Interpretieren der normalisierten Anzahl von Runs in einem Muster ist einfacher als das Interpretieren der tatsächlichen Anzahl von Runs. Der Interpretationscode ist einfach, doch konzeptionell etwas raffiniert. Er fängt folgendermaßen an:

if (z < -2.580 || z > 2.580)
{
    Console.Write("Strong evidence (1%) pattern is not random: ");
    Console.WriteLine(z < -2.580 ? "Too few runs." : Too many runs.");
}

Zuerst wird ein so genannter zweiseitiger Test auf dem Ein-Prozent-Signifikanzniveau durchgeführt. Falls die normalisierte Teststatistik in der absoluten Größenordnung größer als 2.580 ist, dann heißt das, vage ausgedrückt, Folgendes: Die Wahrscheinlichkeit, dass das analysierte Muster zufallsgeneriert wurde, ist kleiner als ein Prozent. Der Wert 2.580 stammt aus statistischen Tabellen. Falls die Teststatistik negativ ausfällt, ist die tatsächliche Anzahl von Runs kleiner als die erwartete Anzahl von Runs und umgekehrt. In Abbildung 2 wird außerdem nach schwächeren Anzeichen dafür gesucht, dass es sich nicht um ein zufälliges Muster handelt. Beachten Sie, dass Sie nie mit Sicherheit behaupten können, dass ein bestimmtes Muster zufallsgeneriert wurde. Sie können durch Tests nur feststellen, ob statistische Beweise dafür vorhanden sind, dass das Muster nicht zufallsgeneriert wurde.

Zufälliges Wiedergeben einer Liste von Elementen

Sehen Sie sich nun die zufällige Wiedergabe einer Liste von Elementen an. Dies ist dann nützlich, wenn Sie eine Sammlung von Testfalleingaben haben und sie alle in ein zu testendes System in einer zufälligen Reihenfolge eingeben möchten. Sie können sich die zufällige Wiedergabe einer Liste wie die Generierung einer zufälligen Permutation der Elemente vorstellen. Dieses unerwartet komplexe Problem wurde zum Gegenstand zahlreicher Forschungsarbeiten. Der beste Algorithmus zur zufälligen Wiedergabe mit allgemeinem Verwendungszweck ist der Fisher-Yates-Algorithmus. Er wird manchmal auch „Knuth-Shuffle“ genannt. Dieser Algorithmus ist sehr einfach. Angenommen, Sie haben ein Array von Elementen:

string[] animals = new string[] { 
    "ant", "bat", "cow", "dog", "elk", "fox" };

Die zufällige Wiedergabe dieser Liste von Elementen mithilfe der am häufigsten verwendeten Form des Fisher-Yates-Algorithmus sieht folgendermaßen aus:

for (int i = 0; i < animals.Length; i++)
{
    int r = objRan.Next(i, animals.Length);
    string temp = animals[r];
    animals[r] = animals[i];
    animals[i] = temp;
}

Sie iterieren durch jeden zufällig wiederzugebenden Index des Arrays. Sie wählen eine Zufallsstelle zwischen dem aktuellen Index und dem Ende des Arrays und tauschen die Elemente am aktuellen und am tatsächlichen Index aus. Unkorrekte Algorithmen zur zufälligen Wiedergabe kommen sehr häufig vor. Der folgende ist besonders raffiniert. Betrachten Sie diesen Versuch:

for (int i = 0; i < animals.Length; i++)
{
    // int r = objRan.Next(i, animals.Length); // correct
    int r = objRan.Next(0, animals.Length);    // incorrect
    string temp = animals[r];
    animals[r] = animals[i];
    animals[i] = temp;
}

Dieser Code wird zwar erstellen und ausführen, doch die daraus resultierende neu angeordnete Liste wird bestimmte Anordnungen von Elementen bevorzugen. Um dies zu illustrieren, nehmen Sie an, dass die zufällig wiederzugebende Originalliste nur drei Elemente enthält, {ABC}. Das Ziel bei der zufälligen Wiedergabe ist die Erstellung einer Zufallsanordnung der drei Elemente, bei der jede Anordnung die gleiche Wahrscheinlichkeit hat. Die Tabelle in Abbildung 3 führt alle 27 möglichen Ergebnisse bei Verwendung des inkorrekten, oben angegebenen Algorithmus auf.

Die erste Zeile der Tabelle in Abbildung 3 bedeutet, dass bei der ersten Iteration durch die zufällige Wiedergabeschleife der Wert von „i“ 0 und „r“, der Zufallsindex, 0 ist. Da die anfängliche Liste {ABC} lautet, ist sie nach dem Austausch gleich geblieben und lautet nach wie vor {ABC}. Bei der zweiten Iteration ist „i“ 1 und der Zufallsindex 0. Nach dem Austausch lautet die Liste nun {BAC}. Bei der letzten Iteration ist „i“ 3 und der Zufallsindex 0. Nach dem Austausch lautet die endgültige Anordnung {CAB}. Es gibt sechs Möglichkeiten für die endgültige Anordnung der drei Elemente. Wenn Sie berechnen, wie oft jedes Ergebnis in der Tabelle in Abbildung 4 vorkommt, erhalten Sie:

{ABC} = 4 times
{ACB} = 5 times
{BAC} = 5 times
{BCA} = 5 times
{CAB} = 4 times
{CBA} = 4 times

Anders ausgedrückt, nicht alle Anordnungen sind gleichermaßen wahrscheinlich. Beachten Sie außerdem, dass A an erster Stelle 9 Mal, B an erster Stelle 10 Mal and C an erster Stelle 8 Mal vorkommt. Wenn Sie diesen inkorrekten Algorithmus zur zufälligen Wiedergabe in einer Glücksspielsimulation verwendet hätten, hätten Sie ein großes Problem.

Mit dem korrekten Algorithmus zur zufälligen Wiedergabe erhalten Sie die in Abbildung 4 dargestellten möglichen Ergebnisse (dabei ist zu beachten, dass ein r-Wert niemals kleiner ist als ein i-Wert). Diesmal ist die Wahrscheinlichkeit, die sechs möglichen endgültigen Anordnungen der drei Elemente zu erzielen, gleichermaßen hoch – ebenso wie die Wahrscheinlichkeit, dass ein Buchstabe an einer bestimmten Stelle erscheint. Beachten Sie außerdem, dass der dritte Durchlauf nicht nötig ist, da er immer nur den letzten Wert im Array selbst austauscht. Das heißt also, dass die Schleife im korrekten Algorithmus bis zu „animals.Length - 1“ statt bis „animals.Length“ gehen kann.

Generieren normaler/Gaußscher Zahlen

Bei der vierten Methode, die in diesem Artikel vorgestellt wird, geht es um die Generierung von Zahlen aus einer Glockenverteilung, im Allgemeinen Normalverteilung oder Gaußverteilung genannt.

Angenommen, Sie möchten Eingabedaten für einen Testfall generieren, die den Körpergrößen einer Gruppe von Personen entspricht. Eine sehr intelligente Methode für die Generierung von normalverteilten Pseudozufallszahlen stellt der Box-Muller-Algorithmus dar. Der Code, mit dem die Ausgabe in Abbildung 1 erstellt wurde, beginnt mit:

Gaussian g = new Gaussian();
double ht;
int outliers = 0;
Console.WriteLine("Generating 100 random heights from a " +
                  "normal/Gaussian population with " +
                  "mean = 68.0 in. and sd = 6.0 in. ->");

Sie instanziieren ein programmdefiniertes Gaußsches Objekt. Dieses Objekt leistet alle Arbeit und verwendet den Box-Muller-Algorithmus. Die Variable „ht“ enthält einen normalverteilten Wert. Außerdem initialisieren Sie einen Zähler, um die Ausreißerwerte, die weit über oder weit unter der Durchschnittsgröße liegen, zu verfolgen. Das Verfolgen der Ausreißer gibt Ihnen eine rudimentäre Möglichkeit sicherzustellen, dass die Zufallsgrößen tatsächlich normal verteilt werden. Abbildung 5 listet den Code auf, der die Zufallsgrößen generiert und anzeigt.

Sie drucken alle 10 Werte eine neue Zeile aus, indem Sie den Moduloperator (%) verwenden, nur um die Ausgabe übersichtlicher zu machen. Die Zufallsgröße aus einer normalen Verteilung mit einem Durchschnitt von 68,0 Zoll und einer Standardabweichung von 6,0 Zoll wird durch den Aufruf der Methode „Gaussian.NextGaussian2“ zurückgegeben. Diese Methode wird weiter unten ausführlicher beschrieben. Sie verfolgen die Außenreißer mit, indem Sie auf Werte Acht geben, die kleiner als 56,0 Zoll oder größer als 80,0 Zoll sind. Dies sind die Werte, die zwei Standardabweichungen (6,0 * 2 = 12,0 Zoll) unter oder über dem Durchschnittswert von 68,0 Zoll liegen. Statistisch gesehen gibt es eine 5-prozentige Wahrscheinlichkeit, dass ein zufallsgenerierter Wert außerhalb von plus oder minus zwei Standardabweichungen vom Durchschnitt liegt. Wenn Sie also wie im vorliegenden Fall 100 Zufallsgrößen generieren, sind ungefähr 5 Ausreißer zu erwarten. Wenn Sie viel mehr oder viel weniger als fünf Ausreißer erhalten, müssen Sie den Code noch einmal überprüfen. Beachten Sie, dass im Muster-Run in Abbildung 1 genau fünf Ausreißer enthalten sind, was gewissermaßen bestätigt, dass die zufallsgenerierten Körpergrößendatenpunkte tatsächlich normalverteilt sind.

Das dem Box-Muller-Algorithmus zugrunde liegende Prinzip ist großartig, das Ergebnis dagegen relativ einfach. Mit zwei gleichverteilten Zufallszahlen, U1 und U2, im Bereich [0,1) (so wie im ersten Teil beschrieben) können Sie mit einer der folgenden beiden Gleichungen eine normalverteilte Zufallszahl, Z, berechnen:

Z = R * cos( θ )
or
Z = R * sin( θ )

Wobei

R = sqrt(-2 * ln(U2))
and
θ = 2 * π * U1

Der Normalwert Z hat einen Durchschnittswert gleich 0 und eine Standardabweichung gleich 1, und Sie können Z mit der folgenden Gleichung auf einen statistischen Wert X mit dem Durchschnittswert m und der Standardabweichung sd übertragen:

X = m + (Z * sd)

In Abbildung 6 wird die einfachste Möglichkeit zur Implementierung einer Gaußschen Klasse mit einer „NextGaussian“-Methode dargestellt.

Es wurde die Version „Math.Cos“ verwendet, es hätte aber genauso gut die Version „Math.Sin“ verwendet werden können. Diese Implementierung funktioniert zwar, ist jedoch ziemlich ineffizient. Da der Box-Muller-Algorithmus einen normalverteilten Z-Wert mit der sin- oder cos-Funktion berechnen kann, liegt es nahe, zwei Z-Werte gleichzeitig zu berechnen, den zweiten Z-Wert zu speichern und dann den gespeicherten Wert bei einem zweiten Aufruf der NextGaussian-Methode abzurufen. Diese Art der Implementierung ist in Abbildung 7 dargestellt.

Diese Vorgehensweise funktioniert zwar gut, weist jedoch ebenfalls eine gewisse Ineffizienz auf. Die Berechnung mithilfe der Methoden „Math.Sin“, „Math.Cos“ und „Math.Log“ verringert die Leistung. Eine sehr raffinierte Verbesserung der Effizienz lässt sich durch einen mathematischen Trick erzielen. Bei der Überprüfung der Definitionen von R und θ kann man feststellen, dass sie den Polarkoordinaten eines Zufallspunkts innerhalb eines Einheitskreises entsprechen. Der mathematische Trick besteht darin, die Koordinaten eines Zufallspunkts innerhalb des Einheitsquadrats zu berechnen (so kann der Aufruf der Math.Sin- und Math.Cos-Methoden vermieden werden) und festzustellen, ob dieser Zufallspunkt in den Einheitskreis fällt. Falls dies der Fall ist, können Sie die Koordinaten verwenden. Falls nicht, berechnen Sie eine neue Reihe von Zufallskoordinaten und starten einen neuen Versuch. Etwa 78 Prozent der zufallsgenerierten Koordinaten werden innerhalb des Einheitskreises liegen, wodurch eine bessere Leistung erzielt wird. Dies geht offensichtlich auf Kosten der Übersichtlichkeit.

Der Trick mit dem Einheitsquadrat wird in Abbildung 8 dargestellt. Der grundlegende Box-Muller-Algorithmus wählt einen Punkt mit den Polarkoordinaten (R, θ) aus, der garantiert im Einheitskreis liegt. Wahlweise können Sie Rechteckskoordinaten im Einheitsquadrat wählen, das den Einheitskreis einschließt. Der Punkt (x1, y1) befindet sich innerhalb des Einheitskreises, der Punkt (x2, y2) fällt jedoch außerhalb des Einheitskreises. Eine Implementierung der Vorgehensweise mittels des Einheitsquadrats wird in Abbildung 9 dargestellt.

Abbildung 8: Einheitsquadrat-Trick
Abbildung 8 Einheitsquadrat-Trick

Beim Softwaretesten ist die Leistung selten ein großes Problem, sodass alle drei oben vorgeführten Implementierungen akzeptabel sind. Bei der Softwareentwicklung jedoch, insbesondere bei Simulationen, kann die Leistung ein großes Problem darstellen. Auch wenn der Box-Muller-Algorithmus sowohl effizient als auch relativ einfach zu implementieren ist, gibt es alternative Algorithmen, zum Generieren von normalen/Gaußschen Pseudozufallszahlen. Eine der hocheffizienten Alternativen nennt sich die „Ziggurat Method“.

Zusammenfassung

Abschließend folgt eine kurze Zusammenfassung. Die Fähigkeit, Zufallseingabedaten für einen Testfall zu generieren, ist eine wichtige Fähigkeit beim Testen von Software. Das .NET Framework enthält eine System.Random-Klasse, die Sie zur Generierung von normalverteilten Ganz- oder Gleitkommazahl-Pseudozufallszahlen in einem bestimmten Bereich verwenden können. Die größte Fehlerquelle dabei kann vermieden werden, indem Sie sicherstellen, dass die Endpunkte des Bereichs korrekt angegeben sind.

Der Wald-Wolfowitz-Test kann zur Analyse eines zwei Symbole enthaltenden Musters eingesetzt werden, um den Beweis zu führen, dass das Muster nach dem Zufallsprinzip generiert wurde. Mit diesem Test können Sie Ihre Eingabe in einem Zufallstestfall oder die Ausgabe eines zu testenden Systems analysieren.

Der beste Algorithmus zur zufälligen Wiedergabe mit allgemeinem Verwendungszweck ist der Fisher-Yates-Algorithmus. Es handelt sich um einen sehr einfachen Algorithmus, und es ist selten notwendig, eine andere Methode zu verwenden. Es muss jedoch festgehalten werden, dass sogar eine kleine Abweichung vom korrekten Algorithmus einen Algorithmus erzeugen kann, der zwar korrekt zu sein scheint, doch völlig fehlerhaft ist.

Sie können den Box-Muller-Algorithmus zur Generierung von Pseudozufallszahlen mit einer Normalverteilung einsetzen. Die dem Box-Muller-Algorithmus zugrunde liegende Mathematik ist sehr tiefgründig, doch die Implementierung überraschend kurz. Der Box-Muller-Algorithmus kann auf mehrere Arten implementiert werden, wobei Effizienz und Übersichtlichkeit gegeneinander abgewogen werden müssen.

Senden Sie Ihre Fragen und Kommentare, die Sie an James richten möchten, an  testrun@microsoft.com.

Der Autor

Dr. James McCaffrey arbeitet für Volt Information Sciences Inc. und organisiert technische Schulungen für Softwareentwickler von Microsoft. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem Internet Explorer und MSN Search. Sie erreichen James unter jmccaffrey@volt.com oder v-jammc@microsoft.com.

Ausgabe von September 2006 des MSDN-Magazins.

Fanden Sie dies hilfreich?
(1500 verbleibende Zeichen)
Vielen Dank für Ihr Feedback.
Anzeigen:
© 2014 Microsoft. Alle Rechte vorbehalten.