Wie soll ich die Zufälligkeit testen?

Betrachten Sie eine Methode zum zufälligen Mischen von Elementen in einem Array. Wie würden Sie einen einfachen, aber robusten Komponententest schreiben, um sicherzustellen, dass dies funktioniert?

Ich habe zwei Ideen entwickelt, die beide bemerkenswerte Mängel aufweisen:

• Mische das Array und stelle dann sicher, dass seine Reihenfolge von der vorherigen abweicht. Dies hört sich gut an, schlägt jedoch fehl, wenn die Zufallswiedergabe in derselben Reihenfolge erfolgt. (Unwahrscheinlich, aber möglich.)
• Mische das Array mit einem konstanten Startwert und vergleiche ihn mit der vorgegebenen Ausgabe. Dies beruht darauf, dass die Zufallsfunktion bei gleichem Startwert immer dieselben Werte zurückgibt. Dies ist jedoch manchmal eine ungültige Annahme .

Stellen Sie sich eine zweite Funktion vor, die Würfelwürfe simuliert und eine Zufallszahl zurückgibt. Wie würden Sie diese Funktion testen? Wie würdest du testen, dass die Funktion ...

• Gibt niemals eine Zahl außerhalb der angegebenen Grenzen zurück?
• gibt Zahlen in einer gültigen Verteilung zurück? (Uniform für einen Würfel, normal für viele Würfel.)

Ich bin auf der Suche nach Antworten, die Einblicke in das Testen nicht nur dieser Beispiele, sondern allgemeiner zufälliger Codeelemente bieten. Sind Unit Tests auch hier die richtige Lösung? Wenn nein, welche Art von Tests sind das?

Nur um es allen leichter zu machen, schreibe ich nicht meinen eigenen Zufallsgenerator.

Ich denke nicht, dass Unit-Tests das richtige Werkzeug sind, um die Zufälligkeit zu testen. Ein Komponententest sollte eine Methode aufrufen und den zurückgegebenen Wert (oder Objektstatus) gegen einen erwarteten Wert testen. Das Problem beim Testen der Zufälligkeit ist, dass für die meisten Dinge, die Sie testen möchten, kein erwarteter Wert vorliegt. Sie können mit einem bestimmten Startwert testen, dies testet jedoch nur die Wiederholbarkeit . Es gibt Ihnen keine Möglichkeit zu messen, wie zufällig die Verteilung ist oder ob sie überhaupt zufällig ist.

Glücklicherweise gibt es eine Menge statistischer Tests, die Sie durchführen können, wie zum Beispiel die Diehard Battery of Tests of Randomness . Siehe auch:

1. Wie teste ich einen Pseudozufallszahlengenerator?

   • Steve Jessop empfiehlt, dass Sie eine getestete Implementierung des gleichen RNG-Algorithmus finden, den Sie verwenden, und die Ausgabe mit ausgewählten Seeds mit Ihrer eigenen Implementierung vergleichen.
   • Greg Hewgill empfiehlt die HNO- Reihe statistischer Tests.
   • John D. Cook verweist die Leser auf seinen CodeProject-Artikel Simple Random Number Generation , der eine Implementierung des Kolmogorov-Smirnov-Tests enthält, der in Donald Knuths Band 2, Seminumerical Algorithms, erwähnt wird.
   • Mehrere Personen empfehlen zu testen, ob die Verteilung der generierten Zahlen gleichmäßig ist, den Chi-Quadrat-Test und zu testen, ob der Mittelwert und die Standardabweichung innerhalb des erwarteten Bereichs liegen. (Beachten Sie, dass das Testen der Verteilung allein nicht ausreicht. [1,2,3,4,5,6,7,8] ist eine gleichmäßige Verteilung, aber es ist sicherlich nicht zufällig.)

2. Unit Testing mit Funktionen, die zufällige Ergebnisse liefern

   • Brian Genisio weist darauf hin, dass das Verspotten Ihres RNG eine Option ist, um Ihre Tests wiederholbar zu machen, und stellt C # -Beispielcode bereit.
   • Wiederum deuten mehrere Leute darauf hin, feste Samenwerte für die Wiederholbarkeit und einfache Tests für die gleichmäßige Verteilung, Chi-Quadrat usw. zu verwenden.

3. Unit Testing Randomness ist ein Wiki-Artikel, der über viele der Herausforderungen spricht, die bereits angesprochen wurden, als versucht wurde, das zu testen, was von Natur aus nicht wiederholbar ist. Ein interessantes Stück, das ich daraus gelernt habe, war das Folgende:

   Ich habe winzip als Werkzeug gesehen, um die Zufälligkeit einer Wertedatei zu messen (je kleiner sie komprimiert werden kann, desto weniger zufällig ist sie natürlich).

1. Testen Sie Ihren Algorithmus

Für die erste Frage würde ich eine gefälschte Klasse erstellen, in die Sie eine Folge von Zufallszahlen eingeben, für die Sie das Ergebnis Ihres Algorithmus kennen. Auf diese Weise stellen Sie sicher, dass der Algorithmus, den Sie auf Ihre Zufallsfunktion aufbauen, funktioniert. Also etwas in der Art von:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Prüfen Sie, ob Ihre Zufallsfunktion sinnvoll ist

Zum Komponententest sollten Sie einen Test hinzufügen, der mehrmals ausgeführt wird und die Ergebnisse bestätigt

• befinden sich innerhalb der von Ihnen festgelegten Grenzen (ein Würfelwurf liegt also zwischen 1 und 6) und
• Zeigen Sie eine vernünftige Verteilung (führen Sie mehrere Testläufe durch und prüfen Sie, ob die Verteilung innerhalb von x% der von Ihnen erwarteten Werte liegt. ZB sollten Sie für den Würfelwurf einen 2Anstieg zwischen 10% und 20% (1/6 = 16,67%) der erwarteten Werte sehen Zeit gegeben, dass Sie es 1000-mal gewürfelt haben).

3. Integrationstest für den Algorithmus und die Zufallsfunktion

Wie oft würden Sie erwarten, dass Ihr Array in der ursprünglichen Sortierung sortiert wird? Sortieren Sie ein paar hundert Mal und stellen Sie sicher, dass sich die Sortierung nur in x% der Fälle nicht ändert.

Dies ist eigentlich schon ein Integrationstest, Sie testen den Algorithmus zusammen mit der Zufallsfunktion. Sobald Sie die echte Zufallsfunktion verwenden, kommen Sie nicht mehr mit einzelnen Testläufen durch.

Aus Erfahrung (ich habe einen genetischen Algorithmus geschrieben) würde ich sagen, dass die Kombination des Einheitentests Ihres Algorithmus, des Verteilungstests Ihrer Zufallsfunktion und des Integrationstests der richtige Weg ist.

Ein Aspekt von PRNGs, der vergessen zu sein scheint, ist, dass alle seine Eigenschaften statistischer Natur sind: Sie können nicht erwarten, dass das Mischen eines Arrays zu einer anderen Permutation führt als die, mit der Sie begonnen haben. Wenn Sie ein normales PRNG verwenden, ist das einzige, was Sie garantiert haben, dass es (hoffentlich) kein einfaches Muster verwendet und dass es eine gleichmäßige Verteilung unter den zurückgegebenen Zahlen hat.

Bei einem ordnungsgemäßen Test für ein PRNG muss es mindestens 100 Mal ausgeführt und anschließend die Verteilung der Ausgabe überprüft werden (eine direkte Antwort auf den zweiten Teil der Frage).

Die Antwort auf die erste Frage ist fast dieselbe: Führen Sie den Test ungefähr 100 Mal mit {1, 2, ..., n} aus und zählen Sie, wie oft sich jedes Element an jeder Position befunden hat. Sie sollten alle ungefähr gleich sein, wenn die Mischmethode eine gute ist.

Eine ganz andere Sache ist das Testen von PRNGs für Kryptografie. Dies ist eine Sache, in der Sie sich wahrscheinlich nicht aufhalten sollten, es sei denn, Sie wissen wirklich, was Sie tun. Es ist bekannt, dass Leute gute Kryptosysteme mit nur wenigen "Optimierungen" oder geringfügigen Änderungen zerstören (sprich: katastrophale Löcher öffnen).

EDIT: Ich habe die Frage, die Top-Antwort und meine eigene gründlich durchgelesen. Während die Punkte, die ich mache, noch stehen, würde ich die Antwort von Bill The Lizard unterstützen. Unit-Tests sind boolescher Natur - sie schlagen entweder fehl oder sie sind erfolgreich und eignen sich daher nicht zum Testen der Eigenschaften eines PRNG (oder einer PRNG-Methode), da jede Antwort auf diese Frage quantitativ wäre eher als polar.

Dazu gibt es zwei Teile: Testen der Randomisierung und Testen von Dingen, die die Randomisierung verwenden.

Das Testen der Randomisierung ist relativ einfach. Sie überprüfen, ob die Periode des Zufallszahlengenerators Ihren Erwartungen entspricht (für einige Stichproben mit ein paar zufälligen Startwerten innerhalb eines bestimmten Schwellenwerts) und ob die Verteilung der Ausgabe auf eine große Stichprobengröße Ihren Erwartungen entspricht es muss sein (innerhalb einer Schwelle).

Das Testen von Dingen, die Randomisierung verwenden, erfolgt am besten mit einem deterministischen Pseudozufallszahlengenerator. Da die Ausgabe der Randomisierung basierend auf dem Startwert (seinen Eingaben) bekannt ist, können Sie den Komponententest wie gewohnt basierend auf den Eingaben und den erwarteten Ausgaben durchführen. Wenn Ihr RNG nicht deterministisch ist, verspotten Sie es mit einem deterministischen (oder einfach nicht zufälligen). Testen Sie die Randomisierung unabhängig von dem Code, der sie verwendet.

Lassen Sie es ein paar Mal laufen und visualisieren Sie Ihre Daten .

Hier ist ein Beispiel für ein Shuffle von Coding Horror . Sie können sehen, dass der Algorithmus in Ordnung ist oder nicht:

Es ist leicht zu erkennen, dass jeder mögliche Artikel mindestens einmal zurückgegeben wird (die Grenzen sind in Ordnung) und dass die Verteilung in Ordnung ist.

Allgemeine Hinweise, die ich für den Umgang mit Code mit zufälliger Eingabe als nützlich erachtet habe: Überprüfen Sie die Kantenfälle der erwarteten Zufälligkeit (Max- und Min-Werte sowie die Max + 1- und Min-1-Werte, falls zutreffend). Überprüfen Sie Orte (an, über und unter), an denen Zahlen Wendepunkte haben (dh -1, 0, 1 oder größer als 1, kleiner als 1 und nicht negativ für Fälle, in denen ein Bruchwert die Funktion durcheinander bringen könnte). Überprüfen Sie einige Stellen außerhalb der zulässigen Eingabe. Überprüfen Sie einige typische Fälle. Sie können auch eine Zufallseingabe hinzufügen. Bei einem Komponententest mit dem unerwünschten Nebeneffekt, dass nicht bei jedem Test derselbe Wert getestet wird (ein Startwert-Ansatz kann jedoch funktionieren), testen Sie die ersten 1.000 Zufallszahlen aus dem Startwert S oder so).

Um die Ausgabe einer Zufallsfunktion zu testen, ist es wichtig, das Ziel zu identifizieren. Ist es das Ziel bei Karten, die Einheitlichkeit des 0-1-Zufallsgenerators zu testen, um festzustellen, ob alle 52 Karten im Ergebnis erscheinen, oder ein anderes Ziel (vielleicht alle diese und mehr)?

Im konkreten Beispiel müssen Sie davon ausgehen, dass Ihr Zufallszahlengenerator undurchsichtig ist (genau wie es keinen Sinn macht, das Betriebssystem syscall oder malloc zu testen, es sei denn, Sie schreiben Betriebssysteme). Es mag nützlich sein, den Zufallsgenerator zu messen, aber Ihr Ziel ist es nicht, einen Zufallsgenerator zu schreiben, nur um zu sehen, dass Sie jedes Mal 52 Karten erhalten und dass sich die Reihenfolge ändert.

Das ist ein langer Weg zu sagen, dass es hier wirklich zwei Testaufgaben gibt: Prüfen, ob der RNG die richtige Verteilung erzeugt, und Prüfen, ob Ihr Karten-Shuffle-Code diesen RNG verwendet, um zufällige Ergebnisse zu erzeugen. Wenn Sie die RNG schreiben, verwenden Sie statistische Analysen, um Ihre Verteilung zu beweisen. Wenn Sie den Kartenmischer schreiben, stellen Sie sicher, dass jede Ausgabe 52 nicht wiederholte Karten enthält (dies ist ein besserer Fall für den von Ihnen verwendeten Test durch Inspektion die RNG).

Sie können sich auf sichere Zufallsgeneratoren verlassen

Ich hatte gerade einen schrecklichen Gedanken: Sie schreiben doch nicht Ihren eigenen Zufallsgenerator, oder?

Unter der Annahme, dass dies nicht der Fall ist, sollten Sie den Code testen, für den Sie verantwortlich sind , und nicht den Code anderer Personen (z. B. die SecureRandomImplementierung für Ihr Framework).

Testen Sie Ihren Code

Um zu testen, ob Ihr Code korrekt reagiert, ist es normal, eine Methode mit geringer Sichtbarkeit zu verwenden, um die Zufallszahlen zu erzeugen, damit sie von einer Komponententestklasse leicht überschrieben werden können. Diese überschriebene Methode verschleiert den Zufallszahlengenerator effektiv und gibt Ihnen die vollständige Kontrolle darüber, was wann produziert wird. Folglich können Sie Ihren Code, der das Ziel von Unit-Tests ist, vollständig ausüben.

Natürlich werden Sie die Randbedingungen überprüfen und sicherstellen, dass das Mischen genau so erfolgt, wie es Ihr Algorithmus bei entsprechenden Eingaben vorschreibt.

Testen des sicheren Zufallszahlengenerators

Wenn Sie sich nicht sicher sind, ob der sichere Zufallszahlengenerator für Ihre Sprache nicht wirklich zufällig oder fehlerhaft ist (Werte außerhalb des gültigen Bereichs usw.), müssen Sie eine detaillierte statistische Analyse der Ausgabe über mehrere hundert Millionen Iterationen durchführen. Tragen Sie die Häufigkeit des Auftretens jeder Zahl ein und sie sollte mit gleicher Wahrscheinlichkeit angezeigt werden. Wenn die Ergebnisse in die eine oder andere Richtung abweichen, sollten Sie Ihre Ergebnisse den Gerüstdesignern melden. Sie werden definitiv daran interessiert sein, das Problem zu beheben, da sichere Zufallszahlengeneratoren für viele Verschlüsselungsalgorithmen von grundlegender Bedeutung sind.

Nun, Sie werden nie zu 100% sicher sein. Das Beste, was Sie tun können, ist, dass es wahrscheinlich ist, dass die Zahlen zufällig sind. Wählen Sie eine Wahrscheinlichkeit - sagen Sie, dass eine Stichprobe von Zahlen oder Gegenständen bei einer Million Stichproben innerhalb einer Fehlerspanne x-mal auftaucht. Führen Sie das Ding eine Million Mal aus und prüfen Sie, ob es innerhalb des Spielraums liegt. Glücklicherweise machen Computer so etwas einfach.

Um zu testen, ob eine Quelle von Zufallszahlen etwas erzeugt, das zumindest den Anschein von Zufälligkeit hat, würde ich den Test eine ziemlich große Folge von Bytes erzeugen lassen, sie in eine temporäre Datei schreiben und dann in Fourmilabs Werkzeug ent schälen . Geben Sie den Schalter -t (kurz) ein, damit eine einfach zu analysierende CSV generiert wird. Überprüfen Sie dann die verschiedenen Zahlen, um festzustellen, ob sie "gut" sind.

Um zu entscheiden, welche Zahlen gut sind, verwenden Sie eine bekannte Zufallsquelle , um Ihren Test zu kalibrieren. Der Test sollte fast immer bestanden werden, wenn ein guter Satz von Zufallszahlen vorliegt. Da selbst bei einer wirklich zufälligen Sequenz die Wahrscheinlichkeit besteht, dass eine Sequenz generiert wird, die nicht zufällig zu sein scheint, können Sie keinen Test erhalten, dessen Bestehen sicher ist. Sie wählen nur Schwellenwerte aus, die es unwahrscheinlich machen, dass eine zufällige Sequenz zu einem Testfehler führt. Macht Zufall nicht Spaß?

Hinweis: Sie können keinen Test schreiben, der zeigt, dass ein PRNG eine "zufällige" Sequenz generiert. Sie können nur einen Test schreiben, der bei Bestehen eine gewisse Wahrscheinlichkeit anzeigt, dass die vom PRNG generierte Sequenz "zufällig" ist. Willkommen zur Freude am Zufall!

Fall 1: Shuffle testen:

Betrachten Sie ein Array [0, 1, 2, 3, 4, 5], mischen Sie es, was kann schief gehen? Das übliche Zeug: a) überhaupt kein Mischen, b) Mischen von 1-5, aber nicht von 0, Mischen von 0-4, aber nicht von 5, Mischen und immer das gleiche Muster erzeugen, ...

Ein Test, um sie alle zu fangen:

Mische 100 Mal, addiere die Werte in jeden Slot. Die Summe jedes Steckplatzes sollte dem jeweils anderen Steckplatz ähnlich sein. Avg / Stddev kann berechnet werden. (5 + 0) /2 = 2,5, 100 * 2,5 = 25. Der erwartete Wert liegt beispielsweise bei 25.

Wenn die Werte außerhalb des zulässigen Bereichs liegen, besteht eine geringe Wahrscheinlichkeit, dass Sie ein falsches Negativ erhalten haben. Sie können berechnen, wie groß diese Chance ist. Wiederholen Sie den Test. Nun - natürlich gibt es eine kleine Chance, dass der Test zweimal hintereinander fehlschlägt. Aber Sie haben keine Routine, die Ihre Quelle automatisch löscht, wenn der Komponententest fehlschlägt, oder? Führen Sie es erneut aus!

Kann es 3 mal hintereinander scheitern? Vielleicht solltest du dein Glück im Lotto versuchen.

Fall 2: Wirf einen Würfel

Die Würfelfrage ist die gleiche Frage. Wirf die Würfel 6000 Mal.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;