Caractère aléatoire des tests (exécution de tests)
Consultez cet article en anglais
Cliquez ici pour télécharger le code de cet article : TestRun2006_09.exe (162 Ko)
Sur cette page
 | Génération de nombres aléatoires uniformément distribués |
| Analyse du caractère aléatoire d'une suite |
| Permutation d'une liste d'éléments |
| Generation de nombres normaux/gaussiens |
| Conclusion |
La création et l'utilisation de données de cas de test aléatoires sont des atouts essentiels des tests logiciels. Bien que la plupart des données d'un cas de test soient composées d'entrées spécifiques dans le système testé et de valeurs/états attendus spécifiques, il est généralement souhaitable de soumettre également le système à des tests aléatoires, afin de vérifier si cela provoque une panne ou une exception en générant un grand nombre d'entrées dans l'application. Dans l'article de ce mois-ci, j'explique quatre tâches courantes à effectuer lors du traitement des données de cas de test aléatoires dans un environnement Microsoft® .NET Framework :
| • | Générer des nombres pseudo-aléatoires (algorithme de Knuth) |
| • | Analyser un modèle pour tester son caractère aléatoire (test de Wald-Wolfowitz) |
| • | Mélanger une liste d'éléments (algorithme de Fisher-Yates) |
| • | Générer des nombres gaussiens (algorithme de Box-Muller) |
Prenons la Figure 1 comme exemple. Dans la première partie figurent les résultats obtenus après la génération classique d'un nombre aléatoire à l'aide de l'objet Random du .NET Framework. Même si vous connaissez cette technique, je vous donnerai quelques conseils pour éviter les pièges les plus courants. La deuxième partie explique une technique très utile, mais méconnue, qui permet d'analyser le caractère aléatoire d'une suite de symboles arbitraires. Cette technique trouve un grand nombre d'applications dans le cadre du développement logiciel, et pas uniquement dans les tests. La troisième partie de la Figure 1 affiche le résultat de la permutation d'une liste d'éléments ; c'est étonnamment complexe.
Figure 1. Démonstration des techniques aléatoires
Je vais expliquer en détail pourquoi plusieurs permutations apparaissent correctes alors qu'elles sont totalement fausses. La dernière partie de la Figure 1 montre le résultat obtenu après la génération d'un ensemble de nombres distribués selon la courbe normale de Bell. Outre le fait qu'il s'agisse là d'une technique très utile, les détails de la mise en œuvre de cet algorithme sont intéressants en soi et constitueront un élément supplémentaire précieux de votre boîte à outils de codage.
Génération de nombres aléatoires uniformément distribués
La tâche la plus essentielle dans la génération aléatoire de cas de test consiste à générer un nombre aléatoire, entier ou virgule flottante, dans une série particulière. Cela se fait souvent via la classe System.Random. Examinez le code suivant :
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);
J'instancie un objet Random en transmettant une valeur de départ (5 dans cet exemple). La valeur de départ définit le point de départ d'une séquence de nombres qui montrent plusieurs caractéristiques de nombres totalement aléatoires. Dans la mesure où la séquence est déterministe (les nombres sont générés à partir d'une formule mathématique qui utilise en entrée la valeur de départ ou les nombres précédents de la séquence), les nombres générés par System.Random sont, d'un point de vue technique, des nombres pseudo-aléatoires. Ils sont toutefois considérés comme des nombres aléatoires à des fins pratiques ou lorsque le contexte est clair, comme ici. La valeur de départ que j'ai choisie est arbitraire. Si j'utilise le constructeur Random surchargé qui n'accepte pas de valeur de départ, une valeur dérivée de l'horloge système est utilisée. Si vous devez recréer une séquence de nombres aléatoires lors des cycles de test suivants, ce qui est souvent le cas, vous devez fournir une valeur de départ. La question des valeurs de départ d'un générateur de nombres pseudo-aléatoires est importante et complexe, mais elle n'entre malheureusement pas dans le cadre de cette discussion.
La façon la plus simple de générer un entier aléatoire est encore d'appeler la méthode Random.Next, et de transmettre un seul argument entier. La valeur renvoyée est le prochain entier de la liste pseudo-aléatoire qui est supérieur ou égal à 0 et strictement inférieur à l'argument. Par conséquent, l'appel suivant renvoie un nombre compris entre 0 et 9 inclus et non pas entre 0 et 10 inclus :
int n = objRan.Next(10);
Une surcharge de la méthode Random.Next accepte deux arguments entiers et renvoie un entier supérieur ou égal au premier argument et strictement inférieur au second. Supposons que vous vouliez simuler des données de cas de test correspondant au lancement d'un dé classique à six faces pour obtenir un nombre compris entre 1 et 6 inclus, l'appel pourrait se présenter ainsi :
int roll = objRan.Next(1, 7);
Il est très facile de générer un élément sélectionné au hasard dans un tableau :
string[] items = new string[] { "alpha", "beta", "gamma", "delta" };
Console.WriteLine("A random member of { 'alpha', 'beta', " +
"'gamma', 'delta' } is " +
items[objRan.Next(items.Length)] );
Si la taille du tableau est N, l'appel objRan.Next(N) renverra une valeur entière comprise dans l'intervalle [0, N-1], ce qui correspond exactement aux valeurs d'index du tableau. Remarquez que cette technique fonctionne aussi pour les objets ArrayList et, en fait, pour toute collection indexée par rapport à 0.
En coulisses, les méthodes Random.Next surchargées utilisent la technique de génération de nombres pseudo-aléatoires de Knuth, également appelée « technique soustractive ». Knuth a publié cet algorithme dans l'ouvrage « Seminumerical Algorithms », Vol. 2 de The Art of Computer Programming (Addison-Wesley, 1981). La génération de nombres pseudo-aléatoires uniformément distribués est plutôt difficile, mais heureusement, le .NET Framework se charge de mettre cet algorithme en œuvre à votre place.
À l'époque où le .NET Framework a été initialement mis au point, un nouvel algorithme de génération de nombres pseudo-aléatoires était découvert par Matsumoto et Nishimura. Leur algorithme, connu sous le nom de Mersenne Twister, remplace rapidement ses prédécesseurs du fait de ses performances bien supérieures et de ses caractéristiques mathématiques. Voir « Mersenne Twister : A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator », ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, janvier 1998.
La génération d'un nombre en virgule flottante pseudo-aléatoire s'apparente à celle d'un entier pseudo-aléatoire. Examinez le code suivant :
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"));
L'appel à Random.NextDouble renvoie un nombre supérieur ou égal à 0,0 et strictement inférieur à 1,0. Pour générer un nombre de type virgule flottante sur l'intervalle [bas, haut) où la notation crochet-parenthèse signifie supérieur ou égal à « bas » et strictement inférieur à « haut », vous pouvez utiliser la mini-formule suivante :
double result = ((high-low) * objRan.NextDouble()) + low;
Dans la mesure où, à l'exception de 0,0, la plupart des valeurs de type virgule flottante sont des approximations, il est impossible de générer techniquement un nombre en virgule flottante dans un intervalle [bas, haut] incluant les bornes, vous devez exclure les bornes. Cette formule ressemble beaucoup à celle qui est utilisée dans la surcharge de Next qui accepte un intervalle complet, sauf que le résultat donne un entier.
Analyse du caractère aléatoire d'une suite
Vous serez probablement amené à examiner une suite de cas de test, en entrée ou en sortie, pour vérifier qu'elle a bien été générée de façon aléatoire (pour tester, par exemple, qu'une simulation de jeu donne bien des résultats totalement aléatoires). Il existe, pour ce faire, plusieurs techniques statistiques, mais la plus simple est le test Wald-Wolfowitz. Ce test consiste à vérifier le cycle d'une valeur (le « cycle » étant une série ininterrompue du même nombre ou du même caractère). Le test Wald-Wolfowitz s'applique à une séquence de deux symboles, par exemple :
A B B A A A B B B A B B
Le principe est le suivant. Pour un nombre donné de chaque type des deux symboles d'une suite, si les symboles sont générés de façon aléatoire (dans cet exemple, chaque position a 50 % de chance d'être un A ou un B dans la suite), vous pouvez calculer le nombre prévu de cycles et juger de l'adéquation entre la distribution prévue et la distribution réellement obtenue. Un cycle est une séquence où les types de symboles sont identiques. Ainsi, dans la suite présentée ci-dessus, il y a six cycles : A, BB, AAA, BBB, A, BB. Si le nombre réel de cycles dans une suite est trop élevé ou trop faible, il y a de grandes chances pour que la suite n'ait pas été générée de façon aléatoire.
Bien que le test de Wald-Wolfowitz s'applique uniquement à des suites constituées de deux types de symboles, vous pouvez souvent ramener des suites arbitraires au format Wald-Wolfowitz. En présence, par exemple, d'une séquence d'entiers telle que {7, 9, 3, 4, 1, 6}, vous pouvez calculer la moyenne (5,0), puis mettre la séquence en corrélation avec des symboles H et L, où H représente un nombre supérieur à la moyenne et L un nombre inférieur à la moyenne : vous obtenez alors H H L L L H. Si vous devez analyser des suites plus complexes, vous pouvez faire appel au test du chi-deux ou au test de Kolmogorov.
Partons maintenant du principe que n1 est le nombre du premier type de symbole d'une suite et n2 celui du deuxième. Le nombre de cycles prévu, µ, en cas de suite générée de façon aléatoire est :
µ = 1 + ((2*n1*n2) / (n1 + n2))
et l'écart, α2, est obtenu par :
α2 = ((2*n1*n2) * (2*n1*n2 - n1 - n2)) / ((n1 + n2)2 * (n1 + n2 - 1))
Ces deux formules sont issues de la théorie des probabilités. Nous pouvons utiliser la moyenne et l'écart pour déterminer la probabilité qu'a une suite particulière d'être le résultat d'un phénomène aléatoire. Supposons que nous partions d'une suite de deux symboles, exprimée sous forme de chaîne :
string s = "XOOOXXXXOXXXXXXXOOOOXXXXXXXXXX";
Je peux, certes, compter manuellement le nombre de X et de O, puis le nombre de cycles dans la suite, mais il est plus simple de laisser mon programme le faire. Premièrement, je détermine les deux types de symboles figurant dans la chaîne de la suite :
char kind1 = s[0], kind2 = s[0];
for (int i = 0; i < s.Length && kind1 =""""= kind2=""; ++i="")
{
if="" (s=""[i=""] != kind1="") kind2 = ""s""[i=""];
}
J'attribue le premier caractère de la chaîne au premier type de symbole, puis j'analyse la chaîne jusqu'à ce que je trouve un deuxième type de symbole. Ensuite, je procède à un simple contrôle d'erreurs pour vérifier que j'ai bien au moins deux caractères différents dans la suite et qu'il n'y en a pas plus de deux :
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");
Si vous avez des soucis de performance, vous pouvez refondre ces trois passes en une seule aux dépens de la clarté.
Je suis désormais prêt à compter le nombre de chaque type de symbole dans la suite et le nombre de cycles :
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="";
J'analyse la suite, à compter du premier caractère jusqu'à l'avant-dernier. Si le caractère actif correspond au type de symbole que j'ai défini précédemment, j'incrémente alors le compteur approprié. Pour calculer le nombre de cycles, je me fie au fait qu'un cycle commence dès que le type de symbole change. Si le caractère actif diffère du caractère suivant, je sais donc qu'un autre cycle commence et j'incrémente le compteur correspondant. Puisque je me suis arrêté à l'avant-dernier caractère de la chaîne, il me faut encore examiner le dernier caractère. Je démarre aussi le compteur de cycles à un au lieu de zéro puisque toutes les suites ont au moins un cycle par définition.
Le test de Wald-Wolfowitz n'est valide que si le nombre de chaque type de symbole de la suite analysée est huit ou plus. Je m'en assure donc de la façon suivante :
if (n1 < 8 || n2="" < 8)
throw="" new="" Exception=""("n1 and n2 must both be 8 or greater for " +
"this test to be meaningful");
À ce stade de l'analyse, je dispose d'un nombre pour chacun des deux types de symboles et du nombre réel de cycles dans la suite. Je calcule maintenant le nombre prévu de cycles dans la suite si les deux types de symboles étaient générés de façon aléatoire :
double expectedRuns = 1 + ((2.0*n1*n2) / (n1 + n2));
Puis, je calcule l'écart du nombre de cycles en cas de génération aléatoire ainsi :
double varianceNumerator = (2.0*n1*n2) * (2.0*n1*n2 - N);
double varianceDenominator = (double)((N*N)*(N-1));
double variance = varianceNumerator / varianceDenominator;
La prochaine étape de l'analyse consiste à calculer une statistique de test normalisée, z :
double z = (R - expectedRuns) / Math.Sqrt(variance);
La statistique z est égale au nombre réel de cycles dans la suite, moins le nombre prévu de cycles dans la suite, divisé par l'écart type du nombre prévu de cycles (soit la racine carrée de l'écart). Il est plus facile d'interpréter le nombre normalisé de cycles dans une suite que le nombre réel. Le code d'interprétation est simple, bien qu'un peu subtil sur le plan conceptuel. Il commence ainsi :
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.=""");
}
Je réalise un test d'hypothèse bilatéral dit « à deux queues » avec un seuil de signification d'1 %. Si la statistique de test normalisée est supérieure, en valeur absolue, à 2,580, cela signifie alors, globalement, qu'il y a moins d'1 % de chance que la suite faisant l'objet de l'analyse ait été générée par un processus aléatoire. La valeur de 2,580 vient des tables statistiques. Si la statistique de test est négative, le nombre réel de cycles est inférieur au nombre prévu, et vice versa. Dans la Figure 2, je recherche aussi des indices susceptibles d'indiquer que la suite n'est pas aléatoire. Sachez que vous ne pouvez pas affirmer avec certitude qu'une suite donnée n'a pas été générée de façon aléatoire. Vous pouvez uniquement rechercher une preuve statistique de la chose.
Permutation d'une liste d'éléments
Examinons maintenant ce qu'est une permutation d'une liste d'éléments. Cela s'avère utile lorsque vous avez une collection de données de cas de test en entrée et que vous voulez toutes les soumettre au système faisant l'objet du test dans un ordre totalement aléatoire. Vous pouvez envisager de mélanger la liste de façon à générer une permutation aléatoire des différents éléments. Ce problème, plus délicat qu'au premier abord, a été le sujet d'un grand nombre de recherches. L'algorithme de permutation le plus polyvalent et le mieux adapté s'appelle l'algorithme de Fisher-Yates, également appelé quelquefois le mélangeur de Knuth. Cet algorithme est extrêmement simple. Supposez que vous disposez d'un tableau d'éléments :
string[] animals = new string[] {
"ant", "bat", "cow", "dog", "elk", "fox" };
Pour mélanger la liste des animaux avec la forme la plus fréquente de l'algorithme de Fisher-Yates, le code suivant serait utilisé :
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="";
}
Je procède à une itération sur chaque index du tableau à mélanger. Je sélectionne un emplacement aléatoire entre l'index actuel et la fin du tableau et je permute les éléments vers l'index actuel et l'index aléatoire. On rencontre très souvent des algorithmes aléatoires incorrects. Ce qui suit est particulièrement délicat. Suivez cette tentative :
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;
}
Ce code pourra être développé et exécuté, mais la liste réarrangée qui en résultera sera déséquilibrée à la faveur de certains arrangements d'éléments. Afin d'illustrer ce point, prenez une liste originale d'uniquement trois éléments, {ABC}, qui doit être réarrangée de façon aléatoire. Le but d'un réarrangement aléatoire est de produire un arrangement non prédéterminé de ces trois éléments, en assurant une probabilité égale à tous les arrangements. Le tableau de l'Illustration 3 liste les 27 résultats possibles en utilisant l'algorithme aléatoire incorrect présenté ci-dessus.
La première ligne du tableau de l'Illustration 3 signifie que pour la première itération de la boucle de réarrangement aléatoire, la valeur de i est égale à 0 et r, l'index aléatoire, est égal à 0. Puisque l'index original est {ABC}, la liste est toujours {ABC} après la permutation. A la seconde itération, i est égal à 1 et l'index aléatoire est 0. Après la permutation, la liste est désormais {BAC}. A la dernière itération, i est égal à 3 et l'index aléatoire est 0. Après la permutation, la liste est désormais {CAB}. Il existe six arrangements finaux possibles pour les trois éléments. En comptant le nombre d'occurrences de chaque résultat dans le tableau de l'Illustration 4, vous obtenez les totaux suivants :
{ABC} = 4 times
{ACB} = 5 times
{BAC} = 5 times
{BCA} = 5 times
{CAB} = 4 times
{CBA} = 4 times
En d'autres mots, tous les arrangements ne possèdent pas la même probabilité. Notez également que A apparait neuf fois en première position, alors que B y est présent 10 fois et que l'élément C y est présent à 8 reprises. Si vous utilisez cet algorithme aléatoire incorrect dans une simulation de jeu de hasard, vous vous exposez à de sérieux problèmes.
Avec l'algorithme aléatoire correct, vous obtenez les résultats possibles présentés dans l'Illustration 4 (notez que la valeur de r n'est jamais inférieure à celle de i). Dans ce cas de figure, la probabilité d'obtention est égale pour les six arrangements finaux des trois éléments, tout comme la probabilité qu'une lettre apparaisse dans une position particulière. Remarquez également qu'il n'est pas nécessaire d'effectuer un troisième passage, car il ne pourrait que remplacer la dernière valeur de la liste par lui-même. C'est pourquoi la boucle de l'algorithme correct peut obtenir animals.Length - 1 plutôt que animals.Length.
Generation de nombres normaux/gaussiens
La quatrième technique dont le ferai la démonstration dans l'article de ce mois et la génération de nombres sur le modèle d'une distribution en cloche, habituellement appelée distribution normale ou gaussienne.
Supposons que vous souhaitiez générer un jeu d'essais de données d'entrée qui correspond à la taille des membres d'un groupe donné. Une technique intelligente appelée algorithme de Box-Muller permet de générer une distribution de nombres pseudo-aléatoires. Le code utilisé pour créer le résultat indiqué dans l'Illustration 1 débute par :
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. ->");
J'instancie un objet gaussien défini par un programme. L'objet fait tout le travail et utilise l'algorithme de Box-Muller. La variable ht (taille) disposera d'une valeur normalement distribuée. J'initialise également un compteur pour conserver la trace des valeurs solitaires, c'est-à-dire celles qui sont très supérieures ou inférieures à la taille moyenne. En conservant la trace des solitaires, je dispose d'un outil rudimentaire pour vérifier que mes tailles aléatoires sont bien distribuées de façon normale. L'Illustration 5 indique le code qui génère et affiche les tailles aléatoires.
J'imprime une nouvelle ligne toutes les 10 valeurs en utilisant l'opérateur modulus (%), simplement par soucis de clarté de mes résultats. La taille aléatoire à partir d'une distribution normale présentant une moyenne de 68 pouces et une écart-type de 6 pouces est obtenue grâce à la méthode Gaussian.NextGaussian2, que je décrirai en détails tout à l'heure. Je conserve la trace des solitaires en observant les valeurs inférieures à 56 pouces ou supérieures à 80 pouces. Ces valeurs correspondent à une différence supérieure ou inférieure égale à deux écarts-types (6 x 2 = 12 pouces) par rapport à ma moyenne de 68 pouces. Statistiquement, la probabilité qu'une valeur générée de façon aléatoire dépasse une différence de deux écarts-types (en plus ou en moins) par rapport à la moyenne est de moins de 5 %. Si je génère donc 100 tailles aléatoires, comme ici, je devrais avoir environ cinq solitaires. Si j'en obtiens beaucoup plus ou beaucoup moins, je devrais vérifier de nouveau mon code. Notez que dans le passage d'essai présenté dans l'Illustration 1, j'obtiens exactement cinq solitaires, ce qui m'apporte un élément de confirmation que les points de données de taille générés sont bien distribués sur un modèle normal.
Le principe de base de l'algorithme de Box-Muller est brillant, mais le résultat est relativement simple. Si vous possédez deux nombres aléatoires uniformes, U1 et U2, dans l'étendue [0,1) (comme décrit dans la première section de cet article), vous pouvez alors calculer un nombre aléatoire de distribution normale, Z, avec l'une des deux équations suivantes :
Z = R * cos( θ )
or
Z = R * sin( θ )
où
R = sqrt(-2 * ln(U2))
and
θ = 2 * π * U1
La valeur normale Z a une moyenne égale à 0 et un écart-type égal à 1, vous pouvez appliquer Z à une statistique X avec une moyenne m et un écart-type sd en utilisant cette équation :
X = m + (Z * sd)
La manière la plus simple d'implémenter une classe gaussienne avec une méthode NextGaussian est représentée par le code de l'Illustration 6.
J'utilise la version Math.Cos, mais je pourrais tout aussi bien utiliser la version Math.Sin. L'implémentation fonctionne, mais elle est plutôt inefficace. Puisque l'algorithme de Box-Muller permet de calculer une valeur Z distribuée de façon normale en utilisant soit la fonction sin, soit la fonction cos, je pourrais calculer deux valeurs Z en même temps, enregistrer la deuxième valeur Z, puis récupérer la valeur enregistrée grâce à un second appel à la méthode NextGaussian. Ce type d'implémentation est présenté dans l'Illustration 7.
Si cette approche fonctionne bien, elle est également partiellement inefficace. Le calcul utilisant les méthodes Math.Sin, Math.Cos, et Math.Log dégradent sa performance. On peut améliorer l'efficacité en utilisant une astuce mathématique intelligente. Si vous consultez les définitions de R et de θ, vous vous apercevrez qu'ils correspondent aux coordonnées polaires d'un point aléatoire à l'intérieur d'un cercle unité. L'astuce mathématique consiste à calculer les coordonnées d'un point aléatoire à l'intérieur du carré unité (ce qui dispense d'un appel aux méthodes Math.Sin et Math.Cos) et à déterminer si ce point aléatoire est situé dans le cercle unité. Si c'est le cas, nous pouvons alors utiliser ces coordonnées. Dans le cas contraire, nous calculons un nouvel ensemble de coordonnées aléatoires et recommençons. Environ 78 pourcents des coordonnées générées de façon aléatoires se situeront à l'intérieur du cercle unité : ce système offre de meilleurs performances, bien que cela se fasse évidemment aux dépens de la clarté.
L'astuce du carré unité est présentée dans l'Illustration 8. L'algorithme basique de Box-Muller sélectionne un point aux coordonnées polaires (R, θ) dont la présence à l'intérieur du cercle unité est garantie. Autrement, vous pouvez choisir des coordonnées rectangulaires à l'intérieur du carré unité qui englobent le cercle unité ; le point (x1, y1) est situé à l'intérieur du cercle unité, mais le point (x2, y2) en est exclus. Une implémentation de l'approche du carré unité est présentée dans l'Illustration 9.
Figure 8. Astuce du carré unité
Dans des scenarii de test de logiciel, la performance est souvent un problème secondaire : c'est pourquoi l'ensemble des trois implémentations que je vous ai présentées sont acceptables pour ce cas de figure. En revanche, dans le cadre du développement de logiciels, et en particulier dans le cas d'une simulation, la performance est une donnée cruciale. Si l'algorithme de Box-Muller est à la fois efficace et relativement facile à implémenter, il existe toutefois d'autres algorithmes qui génèrent des nombres pseudo-aléatoires normaux/gaussiens. L'une des alternatives possibles se nomme la méthode ziggurat.
Conclusion
Permettez-moi de faire un résumé rapide. La capacité de générer un jeu d'essais de données d'entrée est essentielle au test de logiciel. Le .NET Framework contient une classe System.Random que vous pouvez utiliser pour générer des entiers distribués de façon uniforme ou des nombres pseudo-aléatoires à point flottant dans une étendue spécifique. Le piège principal à éviter est l'oubli de spécification appropriée des points limites.
Le test de Wald-Wolfowitz peut être utilisé pour analyser un modèle contenant deux symboles pour déterminer qu'il a été généré de manière aléatoire. Vous pouvez utiliser ce test pour analyser votre jeu d'essais aléatoire d'entrée ou la sortie d'un système soumis au test.
Le meilleur algorithme de réarrangement aléatoire à visée générale est celui de Fisher-Yates. Cet algorithme est très simple et il est rarement nécessaire d'utiliser une technique différente. Cependant, même un écart infime de l'algorithme correct peut créer un algorithme qui semble correct mais qui possède un défaut fatal.
Vous pouvez utiliser l'algorithme de Box-Muller pour générer des nombres pseudo-aléatoires avec une distribution normale. La formule mathématique de l'algorithme de Box-Muller est complexe, mais son implémentation est étonnamment courte. Il existe plusieurs méthodes pour implémenter l'algorithme de Box-Muller, avec lesquelles vous pouvez privilégier la présentation au détriment de l'efficacité.
Veuillez envoyer vos questions et vos commentaires à l'attention de James, à l'adresse suivante : testrun@microsoft.com .
Dr. James McCaffrey travaille pour Volt Information Sciences Inc., dans la gestion des formations techniques pour les ingénieurs de logiciel qui travaillent à Microsoft. Il a participé à l'élaboration de plusieurs produits Microsoft, dont Internet Explorer et MSN Search. Vous pouvez écrire à James aux adresses suivantes : jmccaffrey@volt.com ou v-jammc@microsoft.com.
Tiré du numéro de septembre 2006 de MSDN Magazine.