Dot.Blog

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

Les pièges de la classe Random

[new: 14/06/2010] Générer des nombres aléatoires avec un ordinateur est déjà en soit ambigu : un PC est une machine déterministe (heureusement pour les développeurs et les utilisateurs !) ce qui lui interdit l’accès à la génération de suites aléatoires aux sens mathématique et statistique. Toutefois il s’agit d’un besoin courant et .NET propose bien entendu une réponse avec la classe Random.

L’ambigüité de Random

Random se présente comme une classe n’offrant aucune méthode statique. Dès lors le développeur comprend qu’il faut en créer une instance avant de l’utiliser. Oui mais cela n’a pas vraiment de sens et peut, de surcroit, être trompeur…

Quelques rappels indispensables

Posons d’abord que nous mettons hors de notre propos les utilisations “détournées” des faiblesses de Random. C’est-à-dire les applications (ou parties d’applications) qui se fondent sur le fait que Random retourne toujours une même suite pour une même “graine” (seed). Cela n’est pas spécifique à .NET, la majorité des langages et plateformes qui offrent un générateur de nombres aléatoires connaissent ce problème de suites “répétables”, pour le comprendre il suffit de revenir à l’introduction de ce billet qui en explique le pourquoi…

Donc hors de ce cadre particulier qui exploite les faiblesses de Random, toute application consommatrice de nombres aléatoires suppose, au contraire, que le générateur est bien équilibré et que les suites retournées “ressemblent” suffisamment à de l’aléatoire pour être utilisées comme telles.

Rappelons que puisque ce n’est pas le cas, les applications réclamant de vraies suites aléatoires sont obligées de se reposer sur du hardware spécifique basé le plus souvent le bruit thermique ou des effets photo-électriques. Plus rares sont les montages utilisant des effets quantiques. Rappelons aussi que les langages ou plateformes comme .NET ne parlent pas de “générateur de nombres aléatoires” mais de générateurs de nombres “pseudo-aléatoires” ce qui traduit mieux leur réelle nature.

Enfin, pour être totalement précis, le générateur de nombres pseudo-aléatoires de .NET se fonde sur un algorithme bien spécifique, celui de générateur de nombres aléatoires soustractif de Donald E. Knuth tel que décrit dans “The art of computer programming, volume 2 :  Seminumerical Algorithms”. Ouvrage passionnant (si si, il faut aimer les maths c’est tout) qu’on peut trouver chez Addison-Wesley.

Quel sens à l’utilisation de multiples instances ?

Revenons à nos moutons. Quel sens donner à l’utilisation de plusieurs instances de Random ? Une application doit-elle créer autant d’instances qu’elle a besoin de suites aléatoires ? Dans ce cas que peut-elle en attendre ?

Deux deux choses l’une : soit la qualité aléatoire de Random est insuffisante pour l’application considérée et ce n’est pas en multipliant les instances qu’on règlera le problème, soit elle est satisfaisante, et dans ce cas, aléatoire pour aléatoire la sortie d’une seule et unique instance de Random doit être aussi imprévisible que celle de 5 ou 10 autres instances…

Conséquemment, il semble ainsi déraisonnable d’utiliser plus d’une instance de Random dans une application.

La bonne pratique consiste ainsi à créer une variable statique de type Random, placée dans une classe de service accessible à toute l’application. L’instance peut être encapsulée dans une classe garantissant la concurrence d’accès si nécessaire. Si des dizaines de threads doivent maintenant accéder à une seule instance, cela peut créer un goulot d’étranglement et dans ce cas seulement il sera logique d’avoir autant d’instances que nécessaire (une par thread en l’occurrence, ni plus ni moins). La documentation de Random nous indique clairement qu’aucun membre d’une instance de Random n’est garantie être “thread safe”. Autant le savoir.

Pourquoi est-ce trompeur ?

L’utilisation de multiples instances de Random est trompeuse car le plus souvent on le fait en pensant disposer de séries aléatoires différentes. Dans l’idée ce n’est pas faux, mais dans la réalité il y a un problème si les instances sont créées très proches l’une de l’autre dans le temps.

Car la graine par défaut est dérivée de la valeur de l’horloge de la machine (de fait il est stupide de voir du code initialiser Random avec DateTime.Now.Milliseconds, puisque c’est ce que fait le constructeur par défaut…). Or, la graine, ainsi que l’'horloge, ont une résolution finie (on s’en douterait mais on n’y pense pas forcément). Il en découle que des instances de Random créées à très peu d’intervalle utiliseront en réalité une même valeur de graine ce qui impliquera des suites aléatoires rigoureusement identiques !

L’exemple de code suivant est issu de la documentation Microsoft et montre comment deux instances créées trop proches l’une de l’autre génèrent la même série :

   1: byte[] bytes1 = new byte[100];
   2: byte[] bytes2 = new byte[100];
   3: Random rnd1 = new Random();
   4: Random rnd2 = new Random();
   5:  
   6: rnd1.NextBytes(bytes1);
   7: rnd2.NextBytes(bytes2);
   8:  
   9: Console.WriteLine("First Series:");
  10: for (int ctr = bytes1.GetLowerBound(0); 
  11:      ctr <= bytes1.GetUpperBound(0); 
  12:      ctr++) { 
  13:    Console.Write("{0, 5}", bytes1[ctr]);
  14:    if ((ctr + 1) % 10 == 0) Console.WriteLine();
  15: } 
  16: Console.WriteLine();
  17: Console.WriteLine("Second Series:");        
  18: for (int ctr = bytes2.GetLowerBound(0);
  19:      ctr <= bytes2.GetUpperBound(0);
  20:      ctr++) {
  21:    Console.Write("{0, 5}", bytes2[ctr]);
  22:    if ((ctr + 1) % 10 == 0) Console.WriteLine();
  23: }   
  24: // The example displays the following output to the console:
  25: //       First Series:
  26: //          97  129  149   54   22  208  120  105   68  177
  27: //         113  214   30  172   74  218  116  230   89   18
  28: //          12  112  130  105  116  180  190  200  187  120
  29: //           7  198  233  158   58   51   50  170   98   23
  30: //          21    1  113   74  146  245   34  255   96   24
  31: //         232  255   23    9  167  240  255   44  194   98
  32: //          18  175  173  204  169  171  236  127  114   23
  33: //         167  202  132   65  253   11  254   56  214  127
  34: //         145  191  104  163  143    7  174  224  247   73
  35: //          52    6  231  255    5  101   83  165  160  231
  36: //       
  37: //       Second Series:
  38: //          97  129  149   54   22  208  120  105   68  177
  39: //         113  214   30  172   74  218  116  230   89   18
  40: //          12  112  130  105  116  180  190  200  187  120
  41: //           7  198  233  158   58   51   50  170   98   23
  42: //          21    1  113   74  146  245   34  255   96   24
  43: //         232  255   23    9  167  240  255   44  194   98
  44: //          18  175  173  204  169  171  236  127  114   23
  45: //         167  202  132   65  253   11  254   56  214  127
  46: //         145  191  104  163  143    7  174  224  247   73
  47: //          52    6  231  255    5  101   83  165  160  231

Conclusion

Bien se servir des outils mis à disposition par le Framework est essentiel. Les nombres aléatoires sont utilisés aussi bien pour tester un logiciel que pour créer des clés (cryptographie) en passant par des données de mise au point de programme, etc. C’est au final un outil utilisé plus souvent qu’on ne le pense.

Il y aurait bien d’autres choses à dire sur le sujet, étudier finement la répartition statistique des nombres produits par Random, ou bien passer en revue les codes qui permettent de produire des suites normalisées (suivant une loi binomiale, exponentielle, gamma, normale, Pareto, Poisson, Weibull…). Ceux qui le désirent pourront creuser le sujet grâce à Binq !

A Dusty Net ! (*)

(*) anagramme de mon traditionnel “Stay Tuned !” choisi aléatoirement bien entendu :-)

blog comments powered by Disqus