161 votos

Esto es un algoritmo aleatorio "suficientemente bueno"; ¿por qué isn ' t se utiliza si lo ' es más rápido?

He hecho una clase llamada QuickRandom, y su trabajo es producir números aleatorios rápidamente. Es realmente simple: sólo tienes que tomar el valor anterior, se multiplica por un double, y tomar la parte decimal.

Aquí está mi QuickRandom de la clase en su totalidad:

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

}

Y aquí está el código que escribí para la prueba:

public static void main(String[] args) {
        QuickRandom qr = new QuickRandom();

        /*for (int i = 0; i < 20; i ++) {
            System.out.println(qr.random());
        }*/

        //Warm up
        for (int i = 0; i < 10000000; i ++) {
            Math.random();
            qr.random();
            System.nanoTime();
        }

        long oldTime;

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            Math.random();
        }
        System.out.println(System.nanoTime() - oldTime);

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            qr.random();
        }
        System.out.println(System.nanoTime() - oldTime);
}

(Wow, acabo de dar cuenta que el código de prueba es mayor que el QuickRandom código. Eso prueba que es un algoritmo simple.)

Se trata de un algoritmo muy sencillo que simplemente se multiplica el anterior doble por un "número mágico" de doble. Me tiraron juntos muy rápidamente, así que probablemente podría hacer mejor, pero, extrañamente, parece estar funcionando bien.

Esto es muestra de la salida de la comentada líneas en main método:

0.612201846732229
0.5823974655091941
0.31062451498865684
0.8324473610354004
0.5907187526770246
0.38650264675748947
0.5243464344127049
0.7812828761272188
0.12417247811074805
0.1322738256858378
0.20614642573072284
0.8797579436677381
0.022122999476108518
0.2017298328387873
0.8394849894162446
0.6548917685640614
0.971667953190428
0.8602096647696964
0.8438709031160894
0.694884972852229

Hm. Bastante aleatorio. De hecho, que el trabajo para un generador de números aleatorios en un juego.

Aquí se muestra la salida de la no-comentó la segunda parte:

5456313909
1427223941

Wow! Se realiza casi 4 veces más rápido que Math.random.

Recuerdo haber leído en algún lugar que Math.random utilizó System.nanoTime() y un montón de locos módulo y la división de las cosas. Que es realmente necesario? Mi algoritmo funciona mucho más rápido y se parece bastante al azar.

Tengo dos preguntas:

  • Es mi algoritmo "suficientemente buena" (por, digamos, un juego, donde realmente los números aleatorios no son demasiado importantes)?
  • ¿Por qué Math.random hacer mucho cuando lo que parece a simple multiplicación y el corte de la decimal será suficiente?

338voto

BalusC Puntos 498232

Su QuickRandom de ejecución no haya realmente una distribución uniforme. Las frecuencias son generalmente más altos en los valores más bajos, mientras Math.random() tiene una distribución más uniforme. He aquí un SSCCE que demuestra que:

package com.stackoverflow.q14491966;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        int[] frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (qr.random() * 10)]++;
        }
        printDistribution("QR", frequencies);

        frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (Math.random() * 10)]++;
        }
        printDistribution("MR", frequencies);
    }

    public static void printDistribution(String name, int[] frequencies) {
        System.out.printf("%n%s distribution |8000     |9000     |10000    |11000    |12000%n", name);
        for (int i = 0; i < 10; i++) {
            char[] bar = "                                                  ".toCharArray(); // 50 chars.
            Arrays.fill(bar, 0, Math.max(0, Math.min(50, frequencies[i] / 100 - 80)), '#');
            System.out.printf("0.%dxxx: %6d  :%s%n", i, frequencies[i], new String(bar));
        }
    }

}

La media de los resultados se parece a esto:

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  11376  :#################################                 
0.1xxx:  11178  :###############################                   
0.2xxx:  11312  :#################################                 
0.3xxx:  10809  :############################                      
0.4xxx:  10242  :######################                            
0.5xxx:   8860  :########                                          
0.6xxx:   9004  :##########                                        
0.7xxx:   8987  :#########                                         
0.8xxx:   9075  :##########                                        
0.9xxx:   9157  :###########                                       

MR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  10097  :####################                              
0.1xxx:   9901  :###################                               
0.2xxx:  10018  :####################                              
0.3xxx:   9956  :###################                               
0.4xxx:   9974  :###################                               
0.5xxx:  10007  :####################                              
0.6xxx:  10136  :#####################                             
0.7xxx:   9937  :###################                               
0.8xxx:  10029  :####################                              
0.9xxx:   9945  :###################    

Si repetir la prueba, verás que el QR distribución varía mucho, dependiendo de las semillas iniciales, mientras que el SEÑOR de distribución es estable. A veces llega a la deseada distribución uniforme, pero más a menudo que no. He aquí uno de los ejemplos más extremos, incluso más allá de las fronteras de la gráfica:

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  41788  :##################################################
0.1xxx:  17495  :##################################################
0.2xxx:  10285  :######################                            
0.3xxx:   7273  :                                                  
0.4xxx:   5643  :                                                  
0.5xxx:   4608  :                                                  
0.6xxx:   3907  :                                                  
0.7xxx:   3350  :                                                  
0.8xxx:   2999  :                                                  
0.9xxx:   2652  :                                                  

127voto

templatetypedef Puntos 129554

Lo que está describiendo es un tipo de generador aleatorio llamado lineal congruential generador. El generador funciona de la siguiente manera:

  • Comience con un valor de inicialización y el multiplicador.
  • Para generar un número al azar:
    • Multiplicar la semilla por el multiplicador.
    • Conjunto de la semilla igual a este valor.
    • Devolver este valor.

Este generador tiene muchas buenas propiedades, pero tiene importantes problemas de como una buena fuente aleatoria. El artículo de la Wikipedia enlazado más arriba se describen algunas de las fortalezas y debilidades. En resumen, si usted necesita un buen valores aleatorios, esto probablemente no es una aproximación muy buena.

Espero que esto ayude!

110voto

duskwuff Puntos 69245

Su número aleatorio función es pobre, ya que tiene muy poca estado interno -- el número de la salida de la función en cualquier paso dado es totalmente dependiente en el número anterior. Por ejemplo, si asumimos que magicNumber es de 2 (por ejemplo), entonces la secuencia:

0.10 -> 0.20

está fuertemente reflejado por secuencias similares:

0.09 -> 0.18
0.11 -> 0.22

En muchos casos, esto generará un notable correlaciones en su juego, por ejemplo, si usted hace llamadas sucesivas a la función para generar las coordenadas X e y para los objetos, los objetos de forma clara diagonal patrones.

A menos que tenga una buena razón para creer que el generador de números aleatorios es el retraso de su aplicación (y esto es MUY raro), no hay ninguna buena razón para probar y escribir su propio.

104voto

Callum Rogers Puntos 6769

El verdadero problema con esto es que la salida del histograma depende de la inicial de la semilla lejos a mucho - mucho del tiempo que va a terminar con una cerca de uniforme de salida, pero una gran parte del tiempo tendrá claramente de la onu-uniforme de salida.

Inspirado por este artículo acerca de cómo el malo de php, rand() función es, he hecho algunas matriz aleatoria de imágenes utilizando QuickRandom y System.Random. Este recorrido muestra cómo, a veces, la semilla puede tener un mal efecto (en este caso favoreciendo los números más bajos), donde como System.Random es bastante uniforme.

QuickRandom

System.Random

Aún Peor

Si queremos inicializar QuickRandom como new QuickRandom(0.01, 1.03) obtenemos esta imagen:

El Código

using System;
using System.Drawing;
using System.Drawing.Imaging;

namespace QuickRandomTest
{
    public class QuickRandom
    {
        private double prevNum;
        private readonly double magicNumber;

        private static readonly Random rand = new Random();

        public QuickRandom(double seed1, double seed2)
        {
            if (seed1 >= 1 || seed1 < 0) throw new ArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
            prevNum = seed1;
            if (seed2 <= 1 || seed2 > 10) throw new ArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
            magicNumber = seed2;
        }

        public QuickRandom()
            : this(rand.NextDouble(), rand.NextDouble() * 10)
        {
        }

        public double Random()
        {
            return prevNum = (prevNum * magicNumber) % 1;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rand = new Random();
            var qrand = new QuickRandom();
            int w = 600;
            int h = 600;
            CreateMatrix(w, h, rand.NextDouble).Save("System.Random.png", ImageFormat.Png);
            CreateMatrix(w, h, qrand.Random).Save("QuickRandom.png", ImageFormat.Png);
        }

        private static Image CreateMatrix(int width, int height, Func<double> f)
        {
            var bitmap = new Bitmap(width, height);
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    var c = (int) (f()*255);
                    bitmap.SetPixel(x, y, Color.FromArgb(c,c,c));
                }
            }

            return bitmap;
        }
    }
}

35voto

Patashu Puntos 14053

Uno de los problemas con su generador de números aleatorios es que no existe el " estado oculto' - si yo sé qué número aleatorio que regresó en la última llamada, sé que cada número aleatorio se enviará hasta el final de los tiempos, ya que sólo hay un posible resultado siguiente, y así sucesivamente y así sucesivamente.

Otra cosa a considerar es el 'periodo' de su generador de números aleatorios. Obviamente, con un número finito de tamaño del estado, igual a la mantisa parte de una doble, por lo que sólo será capaz de volver a lo más 2^52 valores antes de un bucle. Pero eso es en el mejor de los casos - puede usted probar que no hay bucles del período de 1, 2, 3, 4...? Si los hay, su RNG tendrá terrible, degenerados comportamiento en esos casos.

Además, su generación de números aleatorios tienen una distribución uniforme para todos los puntos de partida? Si no lo hace, entonces su RNG estará sesgada - o, peor aún, la parcialidad de diferentes maneras dependiendo de la partida de semillas.

Si usted puede contestar a todas estas preguntas, impresionante. Si usted no puede, entonces sabes por qué la mayoría de la gente no re-inventar la rueda y el uso de una probada generador de números aleatorios ;)

(Por cierto, un buen refrán es: La forma más rápida de código es un código que no se ejecuta. Usted podría hacer de la forma más rápida aleatorio() en el mundo, pero no es bueno si no es muy aleatorio)

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X