Testen auf zufälligen Wert - Gedanken zu diesem Ansatz?
OK, ich habe an einem zufälligen Bildauswahl- und Warteschlangensystem gearbeitet (damit Sie nicht die gleichen Bilder zu oft sehen).
Alles lief gut (so weit mein crappy code reicht) bis Ich bekam das zufällige Bit. Ich wollte es testen, aber wie testen Sie es? Es gibt keine Debug.Assert(i.IsRandom) (leider): D
Also, ich habe mein Gehirn darauf gerichtet, nachdem ich es mit etwas Tee gegossen hatte und kam auf das Folgende, ich habe mich nur gefragt, ob ich deine Gedanken haben könnte?
- Im Grunde wusste ich, dass das random -Bit das Problem war, also habe ich das auf einen Delegaten übertragen (der dann an den Objektkonstruktor übergeben würde).
- Ich habe dann eine Klasse erstellt, die fast dieselbe Logik wie der live -Code aufweist, sich aber an den in einer privaten Variablen ausgewählten Wert erinnert.
- Ich habe dann diesen Delegierten in die Live-Klasse geworfen und dagegen getestet:
d. h.
%Vor%Aber ich konnte nicht anders, als zu denken, verschwendete ich meine Zeit? Ich habe das durch viele Wiederholungen laufen lassen, um zu sehen, ob es irgendwann umgefallen ist usw.
Glaubst du, ich verschwende meine Zeit damit? Oder könnte ich damit durchkommen: 
GateKillers Antwort erinnerte mich daran:
Aktualisierung zu klären
- Ich sollte hinzufügen, dass ich im Grunde niemals dasselbe Ergebnis mehr als X-mal aus einem Pool der Y-Größe sehen möchte.
- Das Hinzufügen des Testcontainers erlaubte mir im Grunde zu sehen, ob eines der vorher ausgewählten Bilder "zufällig" ausgewählt wurde.
- Ich denke technisch gesehen ist die Sache hier nicht im RNG getestet (da ich diesen Code nie geschrieben habe), aber die Tatsache, dass ich random erwarte, resultiert aus einem begrenzten Pool, und ich möchte sie verfolgen .
19 Antworten
Es gibt eine praktische Liste statistischer Zufälligkeit Tests und verwandte Forschung zu Wikipedia. Beachten Sie, dass Sie nicht sicher wissen werden, dass eine Quelle mit den meisten von ihnen wirklich zufällig ist, Sie haben nur einige Möglichkeiten ausgeschlossen, in denen es leicht vorhersehbar sein kann.
Wenn Sie über einen festen Satz von Elementen verfügen und diese nicht zu oft wiederholt werden sollen, mischen Sie die Sammlung nach dem Zufallsprinzip. Dann werden Sie sicher sein, dass Sie nie das gleiche Bild zweimal hintereinander sehen werden. Sie haben das Gefühl, Top 20 Radio zu hören usw. Sie werden die Sammlung komplett durchlaufen, bevor Sie wiederholen.
%Vor%Wenn Sie zu viele Objekte zum Sammeln und Mischen auf einmal haben (zehntausende von Bildern in einem Repository), können Sie das gleiche Verfahren zum Teilen und Überwinden verwenden. Mischen Sie Gruppen von Bildern, mischen Sie dann jede Gruppe.
Ein etwas anderer Ansatz, der so klingt, als ob er auf Ihre überarbeitete Problembeschreibung zutrifft, ist, dass Ihre "Bildauswahl" -Implementierung ihre jüngste Auswahlhistorie in einer Warteschlange von höchstens Y length behält. Bevor ein Bild zurückgegeben wird, prüft es, ob es bereits in der Warteschlange X ist, und wenn dies der Fall ist, wählt es zufällig ein anderes aus, bis es ein passendes gefunden hat.
Wenn Sie wirklich nach der Qualität des Zufallszahlengenerators fragen, muss ich das Statistikbuch öffnen.
Es ist unmöglich zu testen, ob ein Wert wirklich zufällig ist oder nicht. Das Beste, was Sie tun können, ist, den Test einige Male durchzuführen und zu testen, ob Sie eine angemessene Verteilung erhalten haben, aber wenn die Ergebnisse wirklich zufällig sind, hat auch dies eine (sehr geringe) Chance zu versagen.
Wenn Sie White-Box-Tests durchführen und Ihren zufälligen Startwert kennen, können Sie das erwartete Ergebnis tatsächlich berechnen, aber Sie benötigen möglicherweise einen separaten Test, um die Zufälligkeit Ihres RNG zu testen.
Die Generierung von Zufallszahlen ist zu wichtig, um dem Zufall überlassen zu werden. - Robert R. Coveyou
Um das psychologische Problem zu lösen:
Ein anständiger Weg, scheinbare Wiederholungen zu vermeiden, besteht darin, einige Elemente aus dem ganzen Satz zufällig auszuwählen und Duplikate zu verwerfen. Spielen Sie diese und wählen Sie noch ein paar aus. Wie viele "ein paar" sind, hängt davon ab, wie schnell Sie sie spielen und wie groß der ganze Satz ist, aber zum Beispiel eine Wiederholung innerhalb der größeren von "20" zu vermeiden, und "5 Minuten" könnte OK sein. Testen Sie den Benutzer - als Programmierer werden Sie von Slideshows genug haben, dass Sie kein guter Testgegenstand sind.
Um Randomisierungscode zu testen, würde ich sagen:
Schritt 1: Geben Sie an, wie der Code die zufälligen Zufallszahlen den Auswahlmöglichkeiten in Ihrer Domain zuordnen soll, und stellen Sie sicher, dass Ihr Code die Ausgabe des Zufallszahlengenerators korrekt verwendet. Testen Sie dies, indem Sie den Generator verspotten (oder ihn mit einem bekannten Testwert säen, wenn es sich um einen PRNG handelt).
Schritt 2: Stellen Sie sicher, dass der Generator für Ihre Zwecke ausreichend zufällig ist. Wenn Sie eine Bibliotheksfunktion verwendet haben, lesen Sie dazu die Dokumentation. Wenn du dein eigenes geschrieben hast, warum?
Schritt 3 (nur für fortgeschrittene Statistiker): Führen Sie statistische Tests für die Zufälligkeit am Ausgang des Generators durch. Stellen Sie sicher, dass Sie wissen, wie hoch die Wahrscheinlichkeit eines falschen Fehlers beim Test ist.
Es gibt ganze Bücher, die man über Zufälligkeit schreiben und bewerten kann, wenn etwas erscheint, um zufällig zu sein, aber ich werde dir die Seiten der Mathematik sparen. Kurz gesagt, Sie können einen Chi-Quadrat-Test verwenden, um festzustellen, wie gut und scheinbar "zufällig" "Verteilung passt, was Sie erwarten.
Wenn Sie Perl verwenden, können Sie das Modul Statistics :: ChiSquare verwenden, um das Problem zu lösen arbeite für dich.
Wenn Sie jedoch sicherstellen möchten, dass Ihre Bilder gleichmäßig verteilt sind, werden Sie wahrscheinlich nicht wollen, dass sie wirklich zufällig sind. Stattdessen würde ich vorschlagen, dass Sie Ihre gesamte Liste von Bildern aufnehmen, diese Liste mischen und dann ein Element daraus entfernen, wenn Sie ein "zufälliges" Bild benötigen. Wenn die Liste leer ist, erstellen Sie sie neu, mischen sie neu und wiederholen.
Diese Technik bedeutet, dass bei einer Reihe von Bildern jedes einzelne Bild nicht mehr als einmal pro Iteration durch Ihre Liste angezeigt werden kann. Ihre Bilder können nicht anders, als gleichmäßig verteilt zu sein.
Alles Gute,
Paul
Was die Random und ähnliche Funktionen Ihnen geben, sind Pseudozufallszahlen, eine Reihe von Zahlen, die durch eine Funktion erzeugt werden. Gewöhnlich geben Sie dieser Funktion ihren ersten Eingabeparameter (a.k.a. die "Saat"), der verwendet wird, um die erste "zufällige" Zahl zu erzeugen. Danach wird jeder letzte Wert als Eingangsparameter für die nächste Iteration des Zyklus verwendet. Sie können den Wikipedia-Artikel über "Pseudozufallszahlengenerator" überprüfen, die Erklärung dort ist sehr gut.
All diese Algorithmen haben etwas gemeinsam: Die Reihe wiederholt sich nach einer Reihe von Iterationen . Denken Sie daran, dass es sich hierbei nicht um wirklich zufällige Zahlen handelt, sondern nur um Zahlenfolgen, die zufällig erscheinen. Um einen Generator über einen anderen zu wählen, müssen Sie sich fragen: Wofür wollen Sie das?
Wie testen Sie die Zufälligkeit? In der Tat kannst du. Dafür gibt es viele Tests. Das erste und einfachste ist natürlich, Ihren Pseudozufallszahlengenerator eine enorme Anzahl von Malen zu betreiben und die Häufigkeit zu kompilieren, mit der jedes Ergebnis erscheint. Am Ende sollte jedes Ergebnis einige Male sehr nahe bei (Anzahl der Iterationen) / (Anzahl der möglichen Ergebnisse) erschienen sein. Je größer die Standardabweichung, desto schlechter ist Ihr Generator.
Die zweite ist: Wie viele Zufallszahlen verwendest du gerade? 2, 3? Nehmen Sie sie paarweise (oder Tripplets) und wiederholen Sie den vorherigen Versuch: Nach einer sehr langen Anzahl von Iterationen sollte jedes erwartete Ergebnis mindestens einmal aufgetreten sein und die Häufigkeit, mit der jedes Ergebnis aufgetreten ist, sollte nicht allzu weit davon entfernt sein das erwartete. Es gibt einige Generatoren, die gut funktionieren, wenn du eine oder zwei gleichzeitig nimmst, aber spektakulär scheitern, wenn du 3 oder mehr nimmst (RANDU irgendjemand?).
Es gibt noch andere, komplexere Tests: einige beinhalten das Zeichnen der Ergebnisse in einer logarithmischen Skala oder auf einer Ebene mit einem Kreis in der Mitte und dann Zählen, wie viel von den Plots hinein fiel, andere ... Ich glaube, diese 2 oben sollte die meiste Zeit ausreichen (es sei denn, Sie sind ein flinker Mathematiker).
Zufällig ist zufällig. Selbst wenn das gleiche Bild 4 Mal in Folge auftaucht, könnte es immer noch als zufällig angesehen werden.
Meine Meinung ist, dass alles, was zufällig ist, nicht richtig getestet werden kann.
Sicher, Sie können versuchen, es zu testen, aber es gibt so viele Kombinationen, um zu versuchen, dass Sie besser dran sind, sich auf den RNG zu verlassen und eine große Handvoll Fälle zu überprüfen.
Nun, das Problem ist, dass Zufallszahlen per Definition können wiederholt werden (weil sie ... warten Sie darauf: zufällig). Vielleicht möchten Sie die letzte Zufallszahl speichern und die berechnete mit der vergleichen, und wenn Sie gleich sind, berechnen Sie einfach eine andere ... aber jetzt sind Ihre Zahlen weniger zufällig (Ich weiß, dass es keine solche gibt Ding als "mehr oder weniger" Zufälligkeit, aber lassen Sie mich den Begriff gerade dieses Mal verwenden, weil sie garantiert sind, sich nicht zu wiederholen.
Wie auch immer, du solltest niemals so viele Gedanken über Zufallszahlen geben. :)
Wie andere betont haben, ist es unmöglich, wirklich auf Zufälligkeit zu prüfen. Sie können (und sollten) die Zufälligkeit einer bestimmten Methode enthalten und dann Komponententests für jede andere Methode schreiben. Auf diese Weise können Sie alle anderen Funktionen testen, vorausgesetzt, Sie können eine Zufallszahl aus diesem letzten Teil erhalten.
Jeder gute Pseudozufallszahlengenerator lässt Sie den Generator säen. Wenn Sie den Generator mit der gleichen Nummer seed, wird der Strom von Zufallszahlen identisch sein. Warum also nicht Ihren Zufallsgenerator generieren und dann Ihre Komponententests basierend auf diesem bestimmten Zahlenstrom erstellen?
Um eine Reihe sich nicht wiederholender Zufallszahlen zu erhalten:
- Erstellen Sie eine Liste von Zufallszahlen.
- Fügen Sie jeder Zufallszahl eine Folgenummer hinzu
- Sortiere die Sequenzliste nach der ursprünglichen Zufallszahl
- Verwenden Sie Ihre Sequenznummer als neue Zufallszahl.
Testen Sie nicht die Zufälligkeit, testen Sie, ob die Ergebnisse, die Sie erhalten, wünschenswert sind (oder versuchen Sie eher, unerwünschte Ergebnisse ein paar Mal zu erhalten, bevor Sie akzeptieren, dass Ihre Ergebnisse wahrscheinlich wünschenswert sind). Es ist unmöglich sicherzustellen, dass Sie nie unerwünschte Ergebnisse erhalten, wenn Sie eine zufällige Ausgabe testen, aber Sie können zumindest die Wahrscheinlichkeit erhöhen, dass Sie bemerken, dass es passiert.
Ich würde entweder N Pools der Y-Größe nehmen, nach Ergebnissen suchen, die mehr als X-mal vorkommen, oder einen Pool der Größe N * Y nehmen und jede Gruppe der Y-Größe auf jedes Ergebnis prüfen, das mehr als X erscheint Zeiten (1 bis Y, 2 bis Y + 1, 3 bis Y + 2, usw.). Was N ist, hängt davon ab, wie zuverlässig der Test sein soll.
Zufallszahlen werden aus einer Verteilung generiert. In diesem Fall sollte jeder Wert die gleiche Wahrscheinlichkeit haben, zu erscheinen. Wenn Sie eine unendliche Menge an Randoms berechnen, erhalten Sie die genaue Verteilung.
In der Praxis rufen Sie die Funktion mehrmals auf und überprüfen Sie die Ergebnisse. Wenn Sie N Bilder erwarten, berechnen Sie 100 * N Randoms, und zählen Sie dann, wie viele der erwarteten Zahlen gefunden wurden. Die meisten sollten 70-130 mal erscheinen. Führen Sie den Test mit verschiedenen Random-Seeds erneut aus, um festzustellen, ob die Ergebnisse unterschiedlich sind.
Wenn Sie feststellen, dass der Generator, den Sie jetzt verwenden, nicht gut genug ist, können Sie leicht etwas finden. Google für "Mersenne Twister" - das ist viel zufälliger als Sie jemals brauchen.
Um zu vermeiden, dass Bilder wieder erscheinen, brauchen Sie etwas weniger Zufälliges. Ein einfacher Ansatz wäre es, nach den unerlaubten Werten zu suchen, falls diese neu berechnet werden.
Obwohl Sie nicht auf Zufälligkeit testen können, können Sie das für die Korrelation oder Verteilung einer Zahlenfolge testen.
Schwer zu testendes Ziel: Jedes Mal, wenn wir ein Bild benötigen, wählen Sie 1 von 4 Bildern zufällig aus.
Leicht zu testendes Ziel: Für jedes 100 Bild, das wir auswählen, muss jedes der 4 Bilder mindestens 20 Mal erscheinen.
Ich stimme Adam Rosenfield zu. Für die Situation, über die Sie sprechen, ist die einzige Sache, für die Sie nützlich sein können, die Verteilung über den Bereich.
Die Situation, auf die ich normalerweise stoße, ist, dass ich Pseudozufallszahlen mit dem PRNG meiner Lieblingssprache erzeuge und sie dann in den gewünschten Bereich manipuliere. Um zu überprüfen, ob meine Manipulationen die Verteilung beeinflusst haben, erzeuge ich eine Menge von Zahlen, manipuliere sie und überprüfe dann die Verteilung der Ergebnisse.
Um einen guten Test zu erhalten, sollten Sie mindestens ein paar Größenordnungen mehr Zahlen erzeugen, als Ihr Bereich hält. Je mehr Werte Sie verwenden, desto besser ist der Test. Offensichtlich, wenn Sie eine wirklich große Reichweite haben, wird dies nicht funktionieren, da Sie viel zu viele Zahlen erzeugen müssen. Aber in Ihrer Situation sollte es gut funktionieren.
Hier ist ein Beispiel in Perl, das veranschaulicht, was ich meine:
%Vor%Wenn der Abstand zwischen den minimalen und maximalen Vorkommen gering ist, ist Ihre Verteilung gut. Wenn es breit ist, dann ist Ihre Distribution möglicherweise schlecht. Sie können diese Methode auch verwenden, um zu überprüfen, ob Ihr Bereich abgedeckt wurde und ob Werte verpasst wurden.
Auch hier gilt: Je mehr Zahlen Sie generieren, desto aussagekräftiger sind die Ergebnisse. Ich neige dazu, klein anzufangen und zu arbeiten, was auch immer meine Maschine in einer angemessenen Zeit, z. fünf Minuten.
Angenommen, Sie testen einen Bereich für die Zufälligkeit innerhalb von ganzen Zahlen. Eine Möglichkeit, dies zu überprüfen, besteht darin, gajillion (gut, vielleicht 10.000 oder so) "zufällige" Zahlen zu erstellen und deren Auftreten in einem Histogramm darzustellen.
%Vor%Das obige zeigt eine 'relativ' Normalverteilung.
Wenn es schiefer aussah, zum Beispiel:
%Vor%Dann können Sie sehen, dass es weniger Zufälligkeit gibt. Wie andere bereits erwähnt haben, gibt es auch die Frage der Wiederholung.
Wenn Sie eine binäre Datei mit etwa 10.000 Zufallszahlen aus Ihrem Generator schreiben würden, sagen Sie eine zufällige Zahl von 1 bis 1024 und versuchen Sie, diese Datei mit einer Komprimierung (zip, gzip, etc.) zu komprimieren die zwei Dateigrößen. Wenn es eine Menge Komprimierung gibt, ist es nicht besonders zufällig. Wenn sich die Größe nicht wesentlich ändert, dann ist es 'ziemlich zufällig'.
Warum das funktioniert
Die Komprimierungsalgorithmen suchen nach Mustern (Wiederholung und anders) und reduzieren diese in gewisser Weise. Eine Möglichkeit, diese Komprimierungsalgorithmen zu betrachten, ist ein Maß für die Menge an Informationen in einer Datei. Eine hochkomprimierte Datei hat wenig Information (z. B. Zufälligkeit), und eine wenig komprimierte Datei hat viele Informationen (Zufälligkeit)
Tags und Links unit-testing testing random automated-tests