Testen für Random Value - Gedanken zu diesem Ansatz?

Question

OK, ich habe auf einer zufällige Bildauswahl und Warteschlangensystem gearbeitet (so sehen Sie nicht die gleichen Bilder zu oft).

Alle swimmingly würde (so weit wie mein crappy Code der Fall ist) bis Ich habe mit dem Random-Bit. Ich wollte es testen, aber wie testen Sie es? Es gibt keine Debug.Assert(i.IsRandom) (leider): D

So habe ich mein Gehirn auf sie, nachdem sie mit etwas Tee gießen, und kam mit der folgenden, ich habe mich nur gefragt, ob ich Ihre Gedanken haben könnte?

• Im Grunde wusste, dass ich die zufällig Bit das Problem war, so dass ich zerrissen, dass zu einem Delegierten aus (die dann an die Objekte Konstruktor übergeben wird).
• Ich habe dann eine Klasse, die so ziemlich die gleiche Logik wie das führt leben Code, aber erinnert sich der Wert in einer privaten Variable ausgewählt.
• Ich warf dann die Delegierten auf die Live-Klasse und getestet gegen das:

d.

Debug.Assert(myObj.RndVal == RndIntTester.ValuePassed);

Aber ich konnte nicht umhin zu denken, wurde ich meine Zeit? Ich lief, dass durch viele Wiederholungen zu sehen, ob es jederzeit etc fiel.

Glaubst du, ich meine Zeit mit diesem zu verschwenden? Oder habe ich komme mit:

Gatekiller Antwort mich daran erinnert:

Update auf Clarify

• Ich sollte hinzufügen, dass ich im Grunde nie das gleiche Ergebnis mehr als X einige Male aus einem Pool von Y-Größe.
sehen wollen
• Die Zugabe des Testbehälters grundsätzlich erlaubt mir, wenn eine der zuvor ausgewählten Bilder zu sehen „zufällig“ ausgewählt wurden.
• ich denke, technisch hier die Sache in getesteten nicht die RNG aber die Tatsache, (da ich nie, dass Code geschrieben hat), die ich erwarte zufällig ergibt sich aus einem begrenzten Pool, und ich möchte, dass sie verfolgen .

Answer 1

Test von der Anforderung: „so sehen Sie nicht die gleichen Bilder zu oft“

Fordern Sie insgesamt 100 Bilder. Haben Sie zu oft ein Bild sehen?

Answer 2

Es ist eine praktische Liste der statistische Zufälligkeit Tests und Forschung auf Wikipedia verwendet. Beachten Sie, dass Sie nicht sicher wissen, dass eine Quelle mit den meisten von ihnen wirklich zufällig ist, werden Sie nur haben einige Möglichkeiten ausgeschlossen, in dem es leicht vorhersehbar sein kann.

Answer 3

Wenn Sie eine feste Gruppe von Elementen haben, und Sie wollen nicht, sie zu oft wiederholen, mischte die zufällig Sammlung. Dann werden Sie sicher sein, dass Sie nie das gleiche Bild zweimal hintereinander sehen, fühlt sich wie 20 Radio Top hören, usw. Sie werden einen vollständigen Durchlauf durch die Sammlung, bevor wiederholen.

Item[] foo = …
for (int idx = foo.size(); idx > 1; --idx) {
  /* Pick random number from half-open interval [0, idx) */
  int rnd = random(idx); 
  Item tmp = foo[idx - 1];
  foo[idx - 1] = foo[rnd];
  foo[rnd] = tmp;
}

Wenn Sie zu viele Elemente haben zu sammeln und mischen alles auf einmal (10s von Tausenden von Bildern in einem Repository), können Sie einige Teile-und-herrschten auf den gleichen Ansatz hinzuzufügen. Shuffle Gruppen von Bildern, dann jede Gruppe mischen.

Ein etwas anderer Ansatz, der klingt wie es um Ihre überarbeitete Problemstellung anwenden könnte, ist Ihre „Bild Selektor“ Implementierung hält ihre letzte Auswahlhistorie in einer Warteschlange von höchstens Y Länge zu haben. Bevor Sie ein Bild zurückkehrt, überprüft er, ob seine in den X mal Warteschlange bereits, und wenn ja, ist es eine andere zufällig auswählt, bis sie einen finden, der vergeht.

Wenn Sie wirklich fragen, über die Prüfung der Qualität der Zufallszahlengenerator, ich werde das Statistik Buch öffnen müssen.

Answer 4

Es ist unmöglich, zu testen, ob ein Wert wirklich zufällig ist oder nicht. Das Beste, was Sie tun können, ist der Test eine große Anzahl von Malen und Test durchführen, die Ihnen eine angemessene Verteilung bekommen, aber wenn die Ergebnisse wirklich zufällig sind, auch dies hat eine (sehr kleine) Chance des Scheiterns.

Wenn Sie weißen Box-Test tun, und wissen Sie zufällig Samen, dann kann man tatsächlich das erwartete Ergebnis berechnen, aber Sie können einen separaten Test müssen die Zufälligkeit des RNG zu testen.

Answer 5

  

Die Erzeugung von Zufallszahlen   zu wichtig, dem Zufall überlassen werden. - Robert R. Coveyou

das psychologische Problem zu lösen:

Eine anständige Art und Weise offensichtlich Wiederholungen zu verhindern, ist ein paar Dinge, die zufällig aus dem vollen Satz zu wählen, verwirft Duplikate. Spielen Sie diejenigen, wählen Sie dann eine andere wenige. Wie viele ist „ein paar“ hängt davon ab, wie schnell Du sie gerade spielen und wie groß der volle Satz ist, sondern beispielsweise eine Wiederholung innerhalb der größeren von „20“ und „5 Minuten“ zu vermeiden könnte in Ordnung sein. Haben Benutzertests -. Als Programmierer Sie werden so krank von Diashows Sie nicht ein gutes Testobjekt

Randomisierung Code zu testen, würde ich sagen:

Schritt 1: Festlegen, wie der Code muss die rohen Zufallszahl zu Entscheidungen in Ihrem Domain-Karte, und stellen Sie sicher, dass Ihr Code korrekt die Ausgabe des Zufallszahlengenerators verwendet. Testen Sie dies durch den Generator Mocking (oder es mit einem bekannten Testwert Impfen, wenn es ein PRNG ist).

Schritt 2: Stellen Sie sicher, dass der Generator für Ihre Zwecke ausreichend zufällig ist. Wenn Sie eine Library-Funktion verwendet wird, tun Sie dies, indem Sie die Dokumentation zu lesen. Wenn Sie Ihre eigene schrieb, warum?

Schritt 3 (Fortgeschrittene Statistiker nur) einige statistische Tests auf Zufälligkeit auf den Ausgang des Generators führen. Stellen Sie sicher wissen, was die Wahrscheinlichkeit eines falschen Fehler auf dem Test.

Answer 6

Es gibt ganze Bücher man über Zufälligkeit schreiben und zu überprüfen etwas erscheint zufällig sein, aber ich werde Ihnen die Seiten der Mathematik speichern. Kurz gesagt, können Sie eine Chi-Quadrat-Test als eine Möglichkeit, zu bestimmen, wie gut ein scheinbar „zufällig“ Verteilung passt, was Sie erwarten.

Wenn Sie Perl verwenden, können Sie die Statistik verwenden :: Chi-Quadrat Modul die harte Arbeit für Sie.

zu tun

Allerdings, wenn Sie sicherstellen möchten, dass Ihre Bilder gleichmäßig sind verteilt , dann werden Sie wahrscheinlich nicht wollen, dass sie wirklich zufällig sein. Stattdessen würde ich vorschlagen, dass Sie Ihre gesamte Liste der Bilder nehmen, diese Liste mischen, und dann ein Element von ihm entfernen, wenn Sie ein „random“ Bild benötigen. Wenn die Liste leer ist, Sie wieder aufzubauen es, wieder shuffle und wiederholen.

Diese Technik bedeutet, dass eine Reihe von Bildern gegeben, jedes einzelne Bild nicht mehr als einmal pro Iteration durch die Liste angezeigt werden kann. Ihre Bilder können nicht helfen, aber gleichmäßig verteilt werden.

Alles Gute,

Paul

Answer 7

Was ist die Random und ähnlichen Funktionen geben Sie sind aber von Pseudozufallszahlen, eine Reihe von Zahlen durch eine Funktion erzeugt. Normalerweise geben Sie diese Funktion es ist erster Eingabeparameter (auch bekannt als die „Samen“), die verwendet wird, um den ersten „Zufallsgenerator“ zu produzieren. Danach wird die jeweils letzte Wert als Eingangsparameter für die nächste Iteration des Zyklus verwendet. Sie können den Wikipedia-Artikel überprüfen „Pseudo-Zufallszahlengenerator“, die Erklärung dort sehr gut ist.

Alle diese Algorithmen haben etwas gemeinsam: die Serie wiederholt sich nach einer Anzahl von Iterationen . Denken Sie daran, diese sind nicht wirklich Zufallszahlen, nur Reihe von Zahlen, die scheinen zufällig. So wählen Sie einen Generator über eine andere, müssen Sie sich fragen: Was möchten Sie tun es für

?

Wie testen Sie Zufälligkeit? Tatsächlich können Sie. Es gibt viele Tests dafür. Die erste und einfachste ist natürlich, führen Sie Ihren pseudo-zufällig eine enorme Anzahl von Malen Zahlengenerator, und übersetzen Sie die Anzahl, wie oft jedes Ergebnis angezeigt wird. Am Ende hat jedes Ergebnis soll einige Male sehr nahe (Anzahl der Wiederholungen) / (Anzahl der möglichen Ergebnisse) erschienen. Je größer die Standardabweichung von dieser ist, desto schlechter Ihr Generator ist.

Die zweite ist: wie viel Zufallszahlen werden Sie zu der Zeit mit? 2, 3? Nehmen Sie sie paarweise (oder tripplets) und wiederholen Sie den vorherigen Experiment: nach einer sehr langen Anzahl von Iterationen, die jeweils zu erwartende Ergebnis haben sollte mindestens einmal, und wieder die Anzahl der Male jedes Ergebnis hat sich gezeigt, sollte nicht zu weit weg schien aus das erwartete. Es gibt einige Generatoren, die für die Aufnahme eines oder zwei zu einer Zeit gut funktionieren, aber nicht spektakulär, wenn Sie nehmen drei oder mehr (RANDU anyone?).

Es gibt noch andere, komplexere Tests: Einige beinhalten die Ergebnisse in einer logarithmischen Skala aufgetragen oder auf eine Ebene mit einem Kreis in der Mitte und dann zu zählen, wie viel von den Parzellen innerhalb fiel, andere ... ich diese 2 glaube oben sollten die meisten der Zeit genügen (es sei denn, Sie ein pingelig Mathematiker sind).

Answer 8

Random ist Zufall. Auch wenn das gleiche Bild 4 mal in Folge auftaucht, ist es noch zufällig betrachtet werden könnte.

Answer 9

Meine Meinung ist, dass alles, was zufällig nicht richtig getestet werden.

Sicher, dass Sie es zu testen versuchen können, aber es gibt so viele Kombinationen, um zu versuchen, dass Sie besser dran nur auf der RNG verlassen und vor Ort eine große Handvoll Fälle zu überprüfen.

Answer 10

Nun, das ist das Problem, dass Zufallszahlen per Definition können wiederholt bekommen (weil sie ... warten, bis es: zufällig). Vielleicht, was Sie tun möchten, ist die neueste Zufallszahl speichern und die berechnete man, daß vergleichen, und wenn gleich nur ein weiteres berechnen ... aber jetzt Ihre Zahlen sind weniger zufällig (Ich weiß, es ist nicht so etwas wie „mehr oder weniger“ Zufälligkeit, aber lassen sie mich den Begriff nur dieses Mal), weil sie garantiert nicht zu wiederholen.

Wie auch immer, sollten Sie nie Zufallszahlen geben so viel Gedanken. :)

Answer 11

Wie andere haben darauf hingewiesen, es ist unmöglich, wirklich auf Zufälligkeit zu testen. Sie können (und sollten) die Zufälligkeit einer bestimmten Methode enthalten ist, und dann Unit-Tests für jede andere Methode schreiben. Auf diese Weise können Sie alle anderen Funktionen testen, vorausgesetzt, dass Sie eine Zufallszahl aus diesem einen letzten Teil bekommen kann.

Answer 12

Speichern der Zufallswerte und bevor Sie die nächste generierte Zufallszahl verwenden, überprüfen Sie mit dem gespeicherten Wert.

Answer 13

Jeder guter Pseudo-Zufallszahlengenerator lassen Sie den Generator Samen. Wenn Sie den Generator mit der gleichen Anzahl Samen, dann wird der Strom von Zufallszahlen erzeugt werden die gleichen sein. Warum also nicht Ihren Zufallszahlengenerator Samt und dann die Komponententests erstellen basierend auf diesem bestimmten Strom von Zahlen?

Answer 14

Um eine Reihe von nicht-wiederkehrenden Zufallszahlen zu erhalten:

1. Erstellen Sie eine Liste von Zufallszahlen.
2. Fügen Sie eine Sequenznummer für jede Zufallszahl
3. Sortieren Sie die Liste sequenziert durch die ursprüngliche Zufallszahl
4. Verwenden des Sequenznummer als eine neue Zufallszahl.

Answer 15

Sie die Zufälligkeit nicht testen, testen, um zu sehen, ob die Ergebnisse Ihrer immer wünschenswert sind (oder vielmehr versuchen, unerwünschte Ergebnisse ein paar Mal zu erhalten, bevor die Annahme, dass Ihre Ergebnisse wahrscheinlich wünschenswert sein werden). Es wird unmöglich sein, um sicherzustellen, dass Sie nie ein unerwünschtes Ergebnis, wenn man eine zufällige Ausgabe sind Testen, aber Sie können die Chancen zumindest erhöhen, werden Sie feststellen, es geschieht.

würde ich entweder mit N-Pools von Y-Größe, für alle Ergebnisse überprüft, die mehr als X Anzahl der Male erscheinen, oder einen Pool von N * Y Größe nehmen, jede Gruppe von Y Größe für Ergebniskontrolle, die mehr als X angezeigt mal (1 bis Y 2 bis Y + 1, 3 bis Y + 2, usw.). Was N ist, würde davon abhängen, wie zuverlässig Sie wollen, dass der Test.

Answer 16

Zufallszahlen werden von einer Verteilung erzeugt. In diesem Fall sollte jeder Wert die gleiche propability zu erscheinen hat. Wenn Sie eine unendliche Menge an randoms berechnen, erhalten Sie die genaue Verteilung.

In der Praxis rufen Sie die Funktion viele Male und die Ergebnisse überprüfen. Wenn Sie erwarten, N Bilder zu haben, berechnen 100 * N randoms, dann zählen, wie viele von jeder erwarteten Zahl gefunden wurden. Die meisten sollten 70-130 mal erscheinen. Re-run den Tests mit verschiedenem Zufallsstartwert zu sehen, ob die Ergebnisse unterschiedlich sind.

Wenn Sie den Generator Sie jetzt verwenden, finden nicht gut genug ist, können Sie leicht etwas finden. Google für „Mersenne Twister.“ -, die viel mehr zufällig, als Sie jemals brauchen

Bilder Um zu vermeiden, wieder erscheinen, müssen Sie etwas weniger zufällig. Ein einfacher Ansatz wäre für die unallowed Werte zu überprüfen, ob seine eine von denen, neu berechnen.

Answer 17

Auch wenn Sie nicht auf Zufälligkeit testen, können Sie die Prüfung auf Korrelation oder Verteilung, aus einer Folge von Zahlen.

Hard Ziel testen: Jedes Mal, wenn wir ein Bild benötigen, wählen Sie 1 von 4 Bildern zufällig

.

Einfache Ziel testen: Für alle 100 Bilder, die wir wählen, jede der 4 Bilder müssen mindestens 20 Mal erscheinen

.

Answer 18

Ich stimme mit Adam Rosenfield. Für die Situation, Sie sprechen, ist das einzige, was man sinnvoll testen kann für die Verteilung über den Bereich.

Die Situation, die ich in der Regel begegnen, ist, dass ich Pseudo-Zufallszahlen mit meiner Lieblingssprache PRNG bin zu erzeugen und sie dann in den gewünschten Bereich zu manipulieren. Um zu überprüfen, ob meine Manipulationen die Verteilung beeinflusst haben, habe ich eine Reihe von Zahlen zu erzeugen, manipulieren, und dann überprüfen Sie die Verteilung der Ergebnisse.

Um einen guten Test zu erhalten, sollten Sie zumindest ein paar Größenordnung mehr Zahlen zu erzeugen, als Ihr Bereich hält. Je mehr Werte Sie verwenden, desto besser ist der Test bestanden. Natürlich, wenn Sie eine wirklich große Auswahl haben, wird dies nicht funktionieren, da Sie viel zu viele Zahlen generieren müssen würden. Aber in Ihrer Situation sollte es funktionieren.

Hier ist ein Beispiel in Perl, das zeigt, was ich meine:

for (my $i=0; $i<=100000; $i++) {
   my $r = rand;        # Get the random number
   $r = int($r * 1000); # Move it into the desired range
   $dist{$r} ++;        # Count the occurrences of each number
}

print "Min occurrences: ", (sort { $a <=> $b } values %dist)[1], "\n";
print "Max occurrences: ", (sort { $b <=> $a } values %dist)[1], "\n";

Wenn die Spanne zwischen den minimalen und maximalen Vorkommen klein ist, dann Ihre Verteilung ist gut. Wenn es breit ist, dann kann Ihre Verteilung schlecht sein. Sie können auch diesen Ansatz verwenden, um zu überprüfen, ob Ihr Bereich abgedeckt wurde und ob alle Werte wurden verfehlt.

Auch hier ist, desto mehr Zahlen, die Sie, desto mehr gelten die Ergebnisse zu generieren. Ich neige dazu, klein zu beginnen und bis zu, was auch immer meine Maschine in einem angemessenen Zeit behandelt, z.B. fünf Minuten.

Answer 19

Angenommen, Sie einen Bereich für die Zufälligkeit testen ganze Zahlen innerhalb, ein Weg, dies zu überprüfen, ist eine gajillion zu erstellen (na ja, vielleicht 10.000 oder so) ‚zufällig‘ Zahlen und zeichnet ihr Vorkommen auf einem Histogramm.

          ******    ******           ****
***********************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
*************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Das oben zeigt eine 'relativ' Normalverteilung.

Wenn es sah mehr schief, wie folgt aus:

          ******    ******           ****
    ************  ************  ************
    ************  ************  ***************
    ************  ************  ****************
    ************  ************  *****************
    ************  ************  *****************
   ***************************  ******************
   **************************** ******************
******************************* ******************
**************************************************
         1         2         3         4         5
12345678901234567890123456789012345678901234567890

Dann können Sie sehen, gibt es weniger Zufall. Wie andere erwähnt haben, gibt es das Problem der Wiederholung mit als auch zu kämpfen.

Wenn Sie eine Binärdatei schreiben waren sagen von 10.000 Zufallszahlen aus dem Generator, etwa eine zufällige Zahl von 1 bis 1024 und versucht, diese Datei zu komprimieren einige Kompression (zip, gzip, etc.), dann können Sie vergleichen die beiden Dateigrößen. Wenn es ‚viele‘ der Kompression ist, dann ist es nicht besonders zufällig. Wenn es nicht viel von einer Änderung in der Größe ist, dann ist es ziemlich zufällig. "

Warum das funktioniert

Die Komprimierungsalgorithmen suchen nach Mustern (Wiederholung und andere) und reduziert die in irgendeiner Weise. Eine Möglichkeit, eine diese Komprimierungsalgorithmen zu suchen ist ein Maß für die Menge an Informationen in einer Datei. Eine stark komprimierte Datei hat wenig Informationen (z Zufälligkeit) und eine wenig komprimierte Datei hat viel Information (Zufälligkeit)