Dot.Blog

C#, XAML, Xamarin, UWP/Android/iOS

Random et bonnes pratiques

[new:16/01/2010]Générer des nombres aléatoires a toujours été un casse-tête pour nos pauvres ordinateurs totalement déterministes. Le Framework .NET nous offre quelques solutions encore faut-il en connaitre les limites et s’en servir correctement….

Nombres aléatoires ?

Définissons d’abord ce qu’est une nombre aléatoire : cela n’existe pas Smile

En effet, seule une série de nombres peut, éventuellement, se voir qualifier d’aléatoire. Un nombre pris seul, de façon totalement isolé n’est ni aléatoire ni non aléatoire, cela est indéterminable.

Ensuite une telle série, pour mériter le qualificatif d’aléatoire doit répondre à des exigences mathématiques précises. Sans entrer dans les méandres des théories que vous trouverez aisément sur le Web, il faut être convaincu qu’aucun procédé algorithmique, aussi sophistiqué ou “rusé” soit-il ne peut générer une suite de nombres aléatoires.

Au mieux, il s’agira d’une suite de nombre pseudo aléatoires répondant à certains critères (c’est à dire simulant au plus proche certaines courbes ou lois comme celle de Poisson ou d’autres formes de distribution).

Un ordinateur étant une machine déterministes (même si certains bugs peuvent parfois nous en faire douter !) l’aléatoire est totalement hors du champ de ses possibilités, quelle que soit sa taille, sa puissance, sa mémoire ou la présence d’un coprocesseur mathématique (dont on ne parle plus depuis quelques années puisque systématiquement intégré aux CPU ce qui ne fut pas le cas pendant longtemps).

Les nombres aléatoires ne peuvent ainsi être générés qu’en s’appuyant sur des phénomènes physiques eux-mêmes réputés aléatoires. C’est pour cela que pour générer des vraies séries de nombres aléatoires sur un ordinateur il faut absolument utiliser un hardware spécifique. Il en existe de différentes nature selon le degré de précision dans l’aléatoire qu’on désire (s’il est possible de parler de précision ici). Ces boitiers qui peuvent se brancher sur un port USB par exemple, utilisent des phénomènes quantiques qu’ils amplifient et numérisent pour obtenir des nombres : bruit thermique d’une résistance en général.

Donc hors de ces hardwares, parler de nombres aléatoires avec un ordinateur est un abus de langage dans le meilleur des cas et une hérésie mathématique dans le pire…

La classe Random

Tout le monde la connait, c’est le moyen le plus simple d’obtenir des nombres pseudo aléatoires sous .NET.

Mais de ce que je peux constater lorsque j’audite du code, cette classe est mal utilisée dans la grande majorité des cas.

Erreur n°1 – Initialisation avec l’heure

A vouloir trop bien faire sans savoir ce qui se cache derrière une classe, on fait des bêtises ou du code inutile, voire les deux à la fois.

La classe Random, lorsqu’elle est instanciée utilise déjà l’horloge pour créer une graine ! Inutile donc d’écrire du code du type :

   1: var r = new Random(DateTime.Now.Millisecond);

Cela est totalement inutile.

Erreur n°2 – Multiplier les instances pour avoir “plus” d’aléatoire

Imaginons plusieurs instances d’une classe métier qui doivent chacune être en mesure de s’appuyer sur des nombres aléatoires (que ces instances fonctionnent dans le même thread ou en multi-thread n’a pas d’importance). Je vois souvent du code qui déclare une instance de Random dans chaque instance de la dite classe métier.

Illusion… et surtout grosse erreur !

Si les instances en questions sont créées les unes à la suite des autres il y a de fortes chances pour qu’elles s’initialisent dans la même tranche horaire (résolution de 20 ms environ) et qu’elles génèrent toutes la même série de nombres !

Pour s’en convaincre écrivons le code suivant :

   1: var r  = new Random();
   2: var r2 = new Random();
   3: for (var i = 0; i<10; i++) 
   4: {
   5:     Console.WriteLine(r.Next(100)+" -- "+r2.Next(100) );
   6: }

(Pour tester des bouts de code ce genre sans charger VS et créer un projet, ce qui est très enquiquinant, je vous conseille fortement l’utilisation de LinqPad qui intègre aussi un petit éditeur de CSharp. C’est gratuit et génial pour tester des requêtes LINQ aussi).

La sortie sera la suivante par exemple :

3 -- 3
20 -- 20
15 -- 15
18 -- 18
83 -- 83
55 -- 55
52 -- 52
2 -- 2
39 -- 39
39 -- 39

Bien entendu à chaque “run” la série sera différence, mais regardez bien les deux colonnes de nombres... Et oui, elles sont identiques. La raison ? les variables r et r2 sont créées à la suite et il s’écoule moins de 20 ms entre ces créations, elles possèdent donc toutes deux la même graine (et fabriqueront ainsi exactement la même série de nombres).

Centraliser les appels

Il ne sert donc à rien de multiplier les instances de Random dans une application en espérant avoir “plus” d’aléatoire au final. Bien au contraire on risque d’obtenir, comme l’exemple ci-dessus le démontre, une uniformité qui n’a vraiment plus rien d’aléatoire, même “pseudo” !

Si les exigences mathématiques sont assez faibles on peut parfaitement se contenter de Random. Mais alors, le plus malin consiste à créer une seule instance pour toute l’application. On s’assure bien ainsi que chaque run de l’application se basera sur une série différence et surtout qu’au sein de l’application tous les nombres sembleront bien être aléatoires...

Je vous passe l’exemple d’une classe statique déclarant une instance de Random et exposant des méthodes statiques calquant les méthodes principales de cette dernière. C’est enfantin. En revanche, n’oubliez pas de déclarer un variable objet servant de verrou pour faire un lock sur les méthodes afin de s’assurer du bon fonctionnement en multi-threading. S’agissant d’une seule instruction j’avoue avoir d’un seul coup un doute sur ce conseil et cela mériterait que je le teste avant d’affirmer à mon tour des bêtises... (charité bien ordonnée commence par soi même, n’est-ce pas). Donc le sujet réclame plus ample investigation, prenez le conseil comme tel (à vérifier donc).

Bref, la façon la plus simple d’avoir réellement des nombres pseudo aléatoires dans une application est de n’utiliser qu’une seule instance centralisée de Random.

System.Security.Cryptography

Ce namespace, comme son nom le laisse deviner, contient de nombreuses classes fort utiles en cryptographie. Et qui dit cryptographie dit nombres (pseudo) aléatoires. Mais comme il s’agit ici de sécurité les exigences mathématiques placent la barre un peu plus haut.

Loin de moi l’idée d’aborder ce sujet en quelques lignes. Je veux juste attirer votre attention sur le fait que dans cet espace de noms se trouve un générateur qui remplace Random de façon plus efficace en évitant le risque de répétition des valeurs si plusieurs instances doivent être créées de façon proche dans le temps.

Si la solution d’une classe centralisant tous les appels de génération de nombre aléatoire vers une instance unique de Random ne vous convient pas, si les méthodes de Random ne vous semblent pas assez “solides” pour votre application, alors utiliser RNGCryptoServiceProvider du namespace indiqué.

Cette classe permet de créer des instances de RandomNumberGenerator offrant un comportement plus fiable que Random.

Pour s’en convaincre, reprenons l’exemple utilisé plus haut mais cette fois-ci en utilisant la nouvelle classe :

   1: var r3 = new System.Security.Cryptography.RNGCryptoServiceProvider();
   2: var r4 = new System.Security.Cryptography.RNGCryptoServiceProvider();
   3: byte[] b1 = new byte[1];
   4: byte[] b2 = new byte[1];
   5: for (var i = 0; i<10; i++) 
   6: {
   7:       r3.GetBytes(b1);
   8:     r4.GetBytes(b2);
   9:     Console.WriteLine(b1[0]+" -- "+b2[0] );
  10: }

Le code est similaire mais pas tout à fait équivalent car à la différence de Random la classe retournée par RNGCryptoServiceProvider génère des tableaux de bytes uniquement. Ici j’ai choisi des tableaux de 1 byte pour simuler des valeurs entières courtes ressemblant à celles du premier exemple (qui lui limitait les nombres à l’intervalle 0-99). Ici ce sont ainsi des nombres dans l’espace 0-255 qui seront tirés au sort. Regardons un run :

150 -- 102
15 -- 224
132 -- 128
167 -- 160
92 -- 76
129 -- 90
218 -- 253
226 -- 58
140 -- 225
37 – 252

Bien que les deux variables r3 et r4 soient créées à la suite, les deux générateurs obtenus ne sont pas synchronisés comme ils l’étaient avec Random.

Efficacité

Sur ma machine en 64bits octocoeur, il faut 3321,19 millisecondes pour générer 1 million de bytes aléatoires selon la méthode du second exemple, soit 0,00332119 millisecondes par octet. Il y a donc peu de chance que la vitesse d’exécution pénalise une application, s’agirait-il d’un jeu en 120 frames / seconde !

Avec Random on obtient un temps de 19,0011 millisecondes toujours pour 1 million d’octets générés, soir 1,90011^10-5 millisecondes par octet ! Environ 175 fois plus rapide donc.

Comme toujours dans notre métier il faut choisir entre consommation CPU et consommation mémoire ou bien, comme ici, entre sophistication et rapidité.

Conclusion

Il y aurait bien d’autres choses à dire sur les nombres aléatoires, pseudo ou non. C’est un sujet passionnant. Mais le but de ce petit billet était principalement d’attirer votre attention sur les mauvaises utilisations de Random et vous signaler l’existence dans le Framework d’autres classes plus “pointues” pour produire des séries pseudo aléatoires.

Passez de bonnes fêtes (pas aléatoires je l’espère, mais pas trop déterministes non plus, l’aléatoire fait malgré tout le sel de la vie !)

et Stay Tuned !

blog comments powered by Disqus