Test de la valeur aléatoire - Réflexions sur cette approche?

Question

D'accord, je travaille sur un sélecteur d'images aléatoire et un système de file d'attente (vous ne voyez donc pas les mêmes images trop souvent).

Tout se déroulait à merveille (dans la mesure de mon code de merde) jusqu'à ce que je sois arrivé au hasard. Je voulais le tester, mais comment le testez-vous? Il n'y a pas de Debug.Assert (i.IsRandom) (malheureusement): D

Alors, je me suis fait avoir l'esprit après l'avoir arrosé avec du thé et je suis arrivé avec ce qui suit, je me demandais si je pouvais avoir vos pensées?

• En gros, je savais que le problème aléatoire était le problème. Je l'ai donc transféré à un délégué (qui serait ensuite transmis au constructeur d'objets).
• J'ai ensuite créé une classe qui exécute à peu près la même logique que le code live , mais se souvient de la valeur sélectionnée dans une variable privée.
• J'ai ensuite jeté ce délégué à la classe en direct et testé contre cela:

c'est-à-dire

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

Mais je ne pouvais pas m'empêcher de penser, perdais-je mon temps? J'ai parcouru cela à travers de nombreuses itérations pour voir s'il tombait à tout moment, etc.

Pensez-vous que je perdais mon temps avec ça? Ou aurais-je pu m'en tirer avec:

La

réponse de GateKiller m'a rappelé ce qui suit:

Mettre à jour pour clarifier

• J'ajouterais que je ne souhaite fondamentalement jamais voir le même résultat plus de X fois dans un pool de taille Y.
• L'ajout du conteneur de test m'a permis de voir si l'une des images précédemment sélectionnées était "de manière aléatoire". sélectionné.
• Je suppose que techniquement, la chose à tester n’est pas testée dans le RNG (car je n’ai jamais écrit ce code), mais le fait que j’attends des résultats aléatoires provient d’un pool limité, et je souhaite les suivre. .

Answer 1

Testez à partir de l'exigence: "vous ne verrez donc pas les mêmes images trop souvent"

.

Demandez 100 images. Avez-vous vu une image trop souvent?

Answer 2

Il existe une liste pratique de tests statistiques aléatoires et recherches connexes sur Wikipedia. Notez que vous ne saurez pas avec certitude qu’une source est vraiment aléatoire avec la plupart d’entre elles, vous aurez simplement exclu certains moyens de la rendre facilement prévisible.

Answer 3

Si vous avez un ensemble d'éléments fixe et que vous ne voulez pas qu'ils se répètent trop souvent, mélangez la collection de manière aléatoire. Ensuite, vous serez certain de ne jamais voir la même image deux fois de suite, d’avoir l’impression d’écouter la radio Top 20, etc. Vous ferez un survol complet de la collection avant de le répéter.

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;
}

Si vous avez trop d'éléments à rassembler et à mélanger (10s de milliers d'images dans un référentiel), vous pouvez ajouter une division et une conquête à la même approche. Mélangez les groupes d'images, puis mélangez chaque groupe.

Une approche légèrement différente qui pourrait s’appliquer à votre déclaration de problème révisée consiste à utiliser votre "sélecteur d’image". L’implémentation conserve son historique de sélection récente dans une file d’attente d’au plus Y . Avant de renvoyer une image, il vérifie si le contenu de la file X y figure déjà. Si tel est le cas, il en sélectionne une autre au hasard, jusqu'à ce qu'il en trouve une qui passe.

Si vous souhaitez vraiment tester la qualité du générateur de nombres aléatoires, vous devez ouvrir le livre de statistiques.

Answer 4

Il est impossible de vérifier si une valeur est vraiment aléatoire ou non. Le mieux que vous puissiez faire est d’effectuer le test un grand nombre de fois et de vérifier que vous obtenez une distribution appropriée, mais si les résultats sont vraiment aléatoires, même si cela risque (très peu) d’échouer.

Si vous effectuez un test de boîte blanche et que vous connaissez votre graine aléatoire, vous pouvez alors calculer le résultat attendu, mais vous aurez peut-être besoin d'un test séparé pour tester le caractère aléatoire de votre GNA.

Answer 5

  

La génération de nombres aléatoires est   trop important pour être laissé au hasard. - Robert R. Coveyou

Pour résoudre le problème psychologique:

Une façon décente d'éviter les répétitions apparentes consiste à sélectionner quelques éléments au hasard dans l'ensemble du jeu, en supprimant les doublons. Jouez-les, puis sélectionnez-en quelques autres. Combien est " quelques " Cela dépend de la rapidité avec laquelle vous jouez et de la taille de l'ensemble, mais évitez par exemple une répétition à l'intérieur du plus grand des "20" et des "5 minutes". pourrait être OK. Faites des tests utilisateur - en tant que programmeur, vous en aurez assez des diaporamas pour ne pas être un bon sujet de test.

Pour tester le code de randomisation, je dirais:

Étape 1: indiquez comment le code DOIT mapper les nombres aléatoires bruts sur les choix de votre domaine et assurez-vous que votre code utilise correctement la sortie du générateur de nombres aléatoires. Testez ceci en vous moquant du générateur (ou en lui affectant une valeur de test connue s'il s'agit d'un PRNG).

Étape 2: assurez-vous que le générateur est suffisamment aléatoire pour vos besoins. Si vous avez utilisé une fonction de bibliothèque, vous le faites en lisant la documentation. Si vous avez écrit le vôtre, pourquoi?

Étape 3 (statisticiens avancés uniquement): effectuez des tests statistiques pour déterminer le caractère aléatoire de la sortie du générateur. Assurez-vous de connaître la probabilité d'un échec faux lors du test.

Answer 6

Il existe des livres entiers sur l'aléatoire et sur l'évaluation de quelque chose , mais je vous ferai gagner des pages en mathématiques. En bref, vous pouvez utiliser un test du chi-carré pour déterminer à quel point un apparemment "quotient" " la distribution correspond à vos attentes.

Si vous utilisez Perl, vous pouvez utiliser le Statistics :: ChiSquare module pour faire le travail dur pour vous.

Toutefois, si vous voulez vous assurer que vos images sont distribuées de manière uniforme, vous ne voudrez probablement pas qu'elles soient vraiment aléatoires. Au lieu de cela, je vous suggèrerais de prendre toute votre liste d'images, de la mélanger, puis d'en supprimer un élément chaque fois que vous aurez besoin d'un "aléatoire". image. Lorsque la liste est vide, vous la reconstruisez, la réorganisez et répétez.

Cette technique signifie que, pour un ensemble d’images, chaque image ne peut apparaître plus d’une fois à chaque itération de votre liste. Vos images ne peuvent s’empêcher d’être distribuées uniformément.

Tout le meilleur,

Paul

Answer 7

Ce que Random et des fonctions similaires vous donnent n'est que des nombres pseudo-aléatoires, une série de nombres générés par une fonction. Habituellement, vous attribuez à cette fonction le premier paramètre d’entrée (a.k.a. la "graine") qui est utilisée pour produire le premier paramètre "aléatoire". nombre. Ensuite, chaque dernière valeur est utilisée comme paramètre d'entrée pour la prochaine itération du cycle. Vous pouvez consulter l'article de Wikipedia sur le "Générateur de nombres pseudo-aléatoires", l'explication est très bonne.

Tous ces algorithmes ont quelque chose en commun: la série se répète après un certain nombre d'itérations . Rappelez-vous que ce ne sont pas vraiment des nombres aléatoires, mais uniquement des séries de nombres qui semblent aléatoires. Pour sélectionner un générateur plutôt qu'un autre, vous devez vous demander: pourquoi le voulez-vous?

Comment testez-vous le caractère aléatoire? En effet vous pouvez. Il y a beaucoup de tests pour cela. La première, et la plus simple, consiste bien entendu à exécuter votre générateur de nombres pseudo-aléatoires un nombre considérable de fois et à compiler le nombre de fois que chaque résultat apparaît. Au final, chaque résultat aurait dû apparaître un nombre de fois très proche de (nombre d'itérations) / (nombre de résultats possibles). Plus l'écart-type est élevé, plus votre générateur est en mauvais état.

La seconde est la suivante: combien de nombres aléatoires utilisez-vous à ce moment-là? 2, 3? Prenez-les par paires (ou triplets) et répétez l'expérience précédente: après un très grand nombre d'itérations, chaque résultat attendu devrait apparaître au moins une fois, et encore une fois, le nombre d'apparitions de chaque résultat ne devrait pas être trop éloigné. l'attendu. Il existe des générateurs qui fonctionnent parfaitement pour prendre un ou deux à la fois, mais échouent de façon spectaculaire lorsque vous en prenez trois ou plus (n'importe qui RANDU?).

Il existe d’autres tests plus complexes: certains impliquent de tracer les résultats à l’échelle logarithmique, ou sur un plan avec un cercle au milieu, puis de compter la quantité de parcelles incluses, d’autres ... Je crois que ces 2 ci-dessus devrait suffire la plupart du temps (sauf si vous êtes un mathématicien capricieux).

Answer 8

Aléatoire est Aléatoire. Même si la même image apparaît 4 fois de suite, elle peut toujours être considérée comme aléatoire.

Answer 9

Mon avis est que rien d’aléatoire ne peut être correctement testé.

Bien sûr, vous pouvez essayer de le tester, mais il y a tellement de combinaisons à essayer qu'il vaut mieux vous fier simplement au RNG et à la vérification ponctuelle d'un grand nombre de cas.

Answer 10

Le problème, c’est que par définition, les nombres aléatoires peuvent être répétés (car ils sont ... attendez: aléatoire). Ce que vous voulez peut-être faire, c'est peut-être sauvegarder le dernier nombre aléatoire et comparer celui calculé à celui-là, et si égal, calculez-en un autre ... mais maintenant vos chiffres sont moins aléatoires (je sais "plus ou moins" aléatoire, mais laissez-moi utiliser le terme juste cette fois), car ils sont assurés de ne pas répéter.

Quoi qu’il en soit, vous ne devriez jamais accorder autant d’attention à des nombres aléatoires. :)

Answer 11

Comme d'autres l'ont souligné, il est impossible de vraiment tester le caractère aléatoire. Vous pouvez (et devriez) avoir le caractère aléatoire d'une méthode particulière, puis écrire des tests unitaires pour chaque autre méthode. De cette façon, vous pouvez tester toutes les autres fonctionnalités, en supposant que vous puissiez obtenir un nombre aléatoire dans cette dernière partie.

Answer 12

stockez les valeurs aléatoires et, avant d'utiliser le nombre aléatoire généré suivant, vérifiez par rapport à la valeur stockée.

Answer 13

Tout bon générateur de nombres pseudo-aléatoires vous laissera le germe du générateur. Si vous attribuez le même numéro au générateur, le flux de nombres aléatoires générés sera le même. Alors, pourquoi ne pas créer votre générateur de nombres aléatoires, puis créer vos tests unitaires en fonction de ce flux de nombres particulier?

Answer 14

Pour obtenir une série de nombres aléatoires non répétitifs:

1. Créez une liste de nombres aléatoires.
2. Ajouter un numéro de séquence à chaque nombre aléatoire
3. Trier la liste séquencée par le nombre aléatoire d'origine
4. Utilisez votre numéro de séquence comme nouveau numéro aléatoire.

Answer 15

Ne testez pas le caractère aléatoire, testez pour voir si les résultats que vous obtenez sont souhaitables (ou essayez plutôt d’obtenir des résultats indésirables plusieurs fois avant d’accepter que vos résultats le seront probablement). Il sera impossible de ne jamais obtenir un résultat indésirable si vous testez une sortie aléatoire, mais vous pouvez au moins augmenter les chances que vous le remarquiez.

Je prendrais soit N pools de taille Y, en recherchant les résultats apparaissant plus de X fois, soit en prenant un pool de taille N * Y, en vérifiant chaque groupe de taille Y pour tout résultat supérieur à X fois (1 à Y, 2 à Y + 1, 3 à Y + 2, etc.). La nature de N dépend de la fiabilité du test.

Answer 16

Des nombres aléatoires sont générés à partir d'une distribution. Dans ce cas, chaque valeur devrait avoir la même possibilité d'apparaître. Si vous calculez une quantité infinie de aléas, vous obtenez la distribution exacte.

En pratique, appelez la fonction plusieurs fois et vérifiez les résultats. Si vous prévoyez avoir N images, calculez 100 * N randoms, puis comptez combien de chaque nombre attendu ont été trouvés. La plupart devraient apparaître 70-130 fois. Refaites le test avec différentes valeurs aléatoires pour voir si les résultats sont différents.

Si vous trouvez que le générateur que vous utilisez maintenant n’est pas assez bon, vous pouvez facilement trouver quelque chose. Google pour " Mersenne Twister " - C’est beaucoup plus aléatoire que ce dont vous avez besoin.

Pour éviter que les images ne réapparaissent, vous avez besoin de quelque chose de moins aléatoire. Une approche simple consisterait à vérifier les valeurs non autorisées, si c’est l’une de celles-ci, recalculez.

Answer 17

Bien que vous ne puissiez pas tester le caractère aléatoire, vous pouvez le faire pour déterminer la corrélation ou la distribution d'une séquence de nombres.

Difficile de tester l’objectif: chaque fois que nous avons besoin d’une image, sélectionnez-en une au hasard sur 4 images.

Objectif facile à tester: pour chaque 100 images sélectionnées, chacune des 4 images doit apparaître au moins 20 fois.

Answer 18

Je suis d'accord avec Adam Rosenfield. Dans la situation dont vous parlez, la seule chose que vous pouvez utilement tester est la distribution sur toute la plage.

La situation que je rencontre habituellement est que je génère des nombres pseudo-aléatoires avec le PRNG de mon langage préféré, puis que je les manipule dans la plage souhaitée. Pour vérifier si mes manipulations ont affecté la distribution, je génère un ensemble de nombres, je les manipule, puis je vérifie la distribution des résultats.

Pour obtenir un bon test, vous devez générer au moins quelques ordres de grandeur en plus de nombres que votre gamme ne contient. Plus vous utilisez de valeurs, meilleur est le test. Évidemment, si vous avez une très grande plage, cela ne fonctionnera pas car vous devrez générer beaucoup trop de nombres. Mais dans votre cas, cela devrait bien fonctionner.

Voici un exemple en Perl qui illustre ce que je veux dire:

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";

Si l'écart entre les occurrences min et max est faible, votre distribution est bonne. Si c'est large, alors votre distribution peut être mauvaise. Vous pouvez également utiliser cette approche pour vérifier si votre plage a été couverte et si des valeurs ont été manquées.

Encore une fois, plus vous générez de nombres, plus les résultats sont valides. J'ai tendance à commencer petit et à travailler avec tout ce que ma machine peut gérer dans un délai raisonnable, par exemple. cinq minutes.

Answer 19

Si vous testez une plage de valeurs aléatoires dans des nombres entiers, vous pouvez le vérifier en créant un nombre aléatoire (environ 10 000) (et peut-être environ 10 000) et en traçant leur apparition sur un histogramme.

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

Ce qui précède montre une distribution "relativement" normale.

s'il semble plus asymétrique, comme ceci:

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

Ensuite, vous pouvez voir qu’il ya moins d’aléatoire. Comme d'autres l'ont déjà mentionné, il faut aussi faire face à la répétition.

Si vous deviez écrire un fichier binaire de 10 000 nombres aléatoires à partir de votre générateur, utilisez un nombre aléatoire compris entre 1 et 1024 et essayez de compresser ce fichier à l'aide d'une compression (zip, gzip, etc.), vous pouvez comparer les deux tailles de fichier. S'il y a «beaucoup» de compression, alors ce n'est pas particulièrement aléatoire. S'il n'y a pas beaucoup de changement de taille, alors c'est "assez aléatoire".

Pourquoi cela fonctionne-t-il

Les algorithmes de compression recherchent des modèles (répétition et autres) et les réduisent en quelque sorte. Une façon d’afficher ces algorithmes de compression consiste à mesurer la quantité d’informations contenues dans un fichier. Un fichier fortement compressé contient peu d’informations (par exemple, aléatoire) et un fichier peu compressé contient beaucoup d’informations (aléatoire)