Java du générateur de nombre aléatoire. La complexité de la génération d'un nombre

Je suis conscient que Java utilise un générateur Linéaire à congruence. Ma question est, quelle est la complexité de générer un nombre aléatoire? Comment voulez-vous effectuer de telles analyses?

C'est un peu général et aussi un peu de mal définies. "La complexité de la génération d'un nombre aléatoire." N'est-ce pas un peu louche?
Il faut une JVM entier se multiplient, une JVM ajouter, et une JVM diviser par le nombre généré. L'analyse a été réalisée en combinant dirigé l'activation neuronale avec la lecture du code.

OriginalL'auteur OckhamsRazor | 2011-09-03

  1. 7

    La complexité de la génération un nombre aléatoire est O(1). Voulez-vous dire "quels sont ses coûts en termes d'exécution et de mémoire"?

    Vous pouvez les mesurer avec un micro-benchmark, par exemple, junit-référence ou de Brent Boyer de Référence (voir à une grande liste de ces outils au Quelle est la meilleure macro-outil d'analyse comparative /cadre pour la mesure d'un seul thread complexe algorithme en Java?).

    En outre, je pense que Javas générateurs de nombres aléatoires sont assez rapides, mais statistiquement mauvais. Plutôt utiliser des bibliothèques externes, par exemple le nombre de Mersenne Twister à http://www.cs.gmu.edu/~sean/recherche/, ou, si l'exécution est si important pour vous, la vitesse de Mersenne Twister.

    OriginalL'auteur DaveFar

  2. 5

    La complexité du temps de générateur de nombres aléatoires est O(1). Le temps qu'il faut ne pas augmenter tant que vous avez plus de nombres aléatoires.

    Le caractère aléatoire de java.util.Aléatoire pourrait être un problème. Il utilise une graine de 2^48 de sorte qu'il se répète après le nombre de valeurs. Cela signifie nextLong() ne génèrent pas de toutes les valeurs possibles.

    Si c'est un problème, vous pouvez utiliser SecureRandom qui est plus lent mais le moment qu'il répète est beaucoup plus élevé.

    OriginalL'auteur Peter Lawrey

  3. 3

    Selon la docs, java.util.Random.next est mis en œuvre comme suit:

     synchronized protected int next(int bits) {
   seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
   return (int)(seed >>> (48 - bits));
 }

    Il n'y a rien là-dedans qui prend une quantité variable de temps, mais c'est en grande partie dû au fait qu'il ne traite qu'avec longueur fixe de chiffres.

    De sorte que Java générateur de nombre aléatoires, ce qui n'est même pas un générateur de nombre aléatoire, mais un générateur de nombre pseudo-aléatoire et pas un très bon à cela, comme l'a souligné.

    Hm, il y a aucune réel générateurs de nombres aléatoires en Java? Je suppose que vous auriez à utiliser un peu de matériel et le phénomène physique (et de croire en dieu, jouant aux dés).
    Pas que je sache.. mais je pense qu'il y a au moins une bibliothèque java flottant autour qui utilise l'entropie du HKLM\SOFTWARE\Microsoft\Cryptographie\RNG\Semences sur windows ou /dev/random ailleurs

    OriginalL'auteur harold

  4. 0

    peut-être vous pouvez essayer Textes de Complexité de Calcul: les Générateurs Pseudo-aléatoires par Oded Goldreich

    "Complexité de Génération: L'archétype du choix, c'est que l'
    générateur de a à travailler dans le polynôme temps (dans la longueur de son entrée - le
    de la graine). D'autres choix seront abordés. Nous notons que la mise
    pas d'exigences de calcul sur le générateur (ou, à défaut,
    mettre très légère exigences comme un double-exponentielle
    durée limite supérieure), les rendements des "générateurs" qui peut tromper tout
    subexponential-taille du circuit de la famille."

    OriginalL'auteur pageman