Elección aleatoria de números

Question

Tengo un método que utiliza muestras aleatorias para aproximar un cálculo. Este método se llama millones de veces, por lo que es muy importante que el proceso de elección de los números aleatorios sea eficiente.

No estoy seguro de cuán rápido son las javas Random().nextInt, pero mi programa no parece beneficiar tanto como me gustaría.

la hora de elegir los números al azar, hago lo siguiente (en semi pseudo-código):

// Repeat this 300000 times 
Set set = new Set(); 
while(set.length != 5) 
    set.add(randomNumber(MIN,MAX)); 

Ahora, esto obviamente tiene un mal peor de los casos el tiempo de funcionamiento, ya que el azar-función en teoría puede agrega números duplicados por una eternidad, permaneciendo así en el ciclo while para siempre. Sin embargo, los números se eligen de {0..45}, por lo que un valor duplicado es poco probable.

Cuando uso el método anterior, es solo 40% más rápido que mi otro método, que no se aproxima, pero arroja el resultado correcto. Esto se ejecutó ~ 1 millón de veces, así que esperaba que este nuevo método fuera al menos un 50% más rápido.

¿Tiene alguna sugerencia para un método más rápido? O quizás conozcas una forma más eficiente de generar un conjunto de números aleatorios.

Para aclarar, aquí es los dos métodos:

// Run through all combinations (1 million). This takes 5 seconds 
for(int c1 = 0; c1 < deck.length; c1++){ 
    for(int c2 = c1+1; c2 < deck.length; c2++){ 
    for(int c3 = c2+1; c3 < deck.length; c3++){ 
     for(int c4 = c3+1; c4 < deck.length; c4++){ 
     for(int c5 = c4+1; c5 < deck.length; c5++){ 
      enumeration(hands, cards, deck, c1, c2, c3, c4, c5); 
     } 
      } 
     }  
    } 
    } 

// Approximate (300000 combinations). This takes 3 seconds 
Random rand = new Random(); 
HashSet<Integer> set = new HashSet<Integer>(); 
int[] numbers = new int[5]; 
while(enumerations < 300000){ 
set.clear(); 
while(set.size() != 5){ 
    set.add(rand.nextInt(deck.length)); 
} 
Iterator<Integer> i = set.iterator(); 
int n = 0; 
while(i.hasNext()){ 
    numbers[n] = i.next(); 
    n++; 
} 

Después de algunas pruebas y elaboración de perfiles, he encontrado que este método es el más eficaz:

Random rand = new Random(); 
int[] numbers = new int[5]; 
ArrayList<Integer> list = new ArrayList<Integer>(); 
while(enumerations < 300000){ 
while(list.size() != 5) { 
    int i = rand.nextInt(deck.length); 
     if(!list.contains(i)) list.add(i); 
} 
int index = 0; 
for(int i : list){ numbers[index] = i; index++; } 
enumeration(hands, cards, deck,numbers); 
} 

Answer 1

Puede probar el uso de existing Java implementation (or this one) para Mersenne Twister.

Tenga en cuenta que la mayoría de las MT son no criptográficamente seguras.

Answer 2

Una técnica común es comenzar con una lista de todas las entradas posibles, y seleccione aleatoriamente de eso, borrando las que quiera. De esta forma, no hay riesgo de seleccionar un duplicado y tener que realizar un bucle durante un tiempo desconocido. Por supuesto, este método solo funciona con datos discretos, pero afortunadamente los enteros sí lo son. Recuerde también que la selección y eliminación de su lista (u otra estructura de datos) debe ser O (1) si es posible, ya que se está enfocando en la velocidad.

Answer 3

Nunca adivine, mida siempre.

long time = System.getCurrentMilliseconds(); 
Random().nextInt() 
System.out.println(System.getCurrentMilliseconds() - time); 

Además, nunca se debe confiar en la forma infrecuente ocurrirá un error conocido, solo código defensivley por lo que no lo hace. Detecta un duplicado, y si es un duplicado, entonces no lo agregas, y omite la iteración con una declaración continue.

En cuanto a los métodos más rápidos y números aleatorios ... No se pueden obtener números aleatorios en el Math.random() de Java. Solo puedes obtener números pseudoaleatorios. La rapidez con la que quieres que esto ocurra viene al sacrificio de lo aparentemente aleatorio que necesitas para que aparezcan. La forma más rápida de generar un número pseudoaleatorio implicaría un cambio y adición de bit basado en un valor de inicialización como System.getCurrentMilliSeconds(). Además, la generación de números pseudoaleatorios ya es bastante rápida, ya que es solo una aritmética pura de la CPU de todos modos, por lo que probablemente lo suficientemente feliz una vez que vea cuántos milisegundos se tarda en generar uno con Math.random().

Answer 4

Se podría utilizar congruencia lineal como un generador aleatorio: http://en.wikipedia.org/wiki/Linear_congruential_generator [todavía considerar sus desventajas estadísticos]

Sólo necesita un cálculo de (x + c)% m para cada número. Sin embargo, en mi experiencia, la creación de objetos (como lo haría con cada llamada de un nuevo Set y agregar, dependiendo de la implementación que use) podría costarle más velocidad que una llamada a nextInt(). Tal vez deberías probar un generador de perfiles como, por ejemplo, este: http://www.eclipse.org/tptp/

Answer 5

No tengo ninguna entrada sobre su problema real, y no conozco demasiado Java (solo hurgando). Sin embargo, me parece que está tratando de construir un evaluador de mano para el póker y este hilo http://pokerai.org/pf3/viewtopic.php?f=3&t=16 contiene algunos evaluadores de mano extremadamente rápidos de Java. Esperemos que parte de este código pueda ser de ayuda.

Answer 6

Parece que desea seleccionar un k - combination partir de un conjunto S sin reemplazo, con S tener n valores distintos, k = 5 y n = 52. You puede shuffle() todo el conjunto y seleccionar elementos k (como @Tesserex sugiere), o pick()k elementos mientras se evitan los duplicados (como se ha demostrado). Querrá hacer un perfil tanto en su entorno particular como para su generador elegido. A menudo, pero no siempre, veo un borde modesto para pick().

private static final Random rnd = new Random(); 
private static final int N = 52; 
private static final int K = 5; 
private static final List<Integer> S = new ArrayList<Integer>(N); 
static { 
    for (int i = 0; i < N; i++) { 
     S.add(i + 1); 
    } 
} 
private final List<Integer> combination = new ArrayList<Integer>(K); 

... 

private void shuffle() { 
    Collections.shuffle(S, rnd); 
    combination.addAll(S.subList(0, K)); 
} 

private void pick() { 
    for (int i = 0; i < K; i++) { 
     int v = 0; 
     do { 
      v = rnd.nextInt(N) + 1; 
     } while (combination.contains(v)); 
     combination.add(v); 
    } 
} 

Answer 7

Si usted está siendo frenada por el hecho de que usted tiene que saltar sobre los duplicados, se podría resolver ese problema mediante la creación de una lista de todos los valores de la tarjeta y, a continuación, retirar de la lista como se seleccionan las tarjetas y elegir un número aleatorio en un rango más pequeño la próxima vez. Algo como esto:

// Assuming we're just numbering all the cards 0 to 51. This could be more sophisticated, of course. 
ArrayList cards=new ArrayList(52); 
for (int x=0;x<52;++x) 
    cards=new Integer(x); 

Integer[] hand=new Integer[5]; 
for (int h=0;h<5;++h) 
{ 
    // Pick a card from those remaining 
    int n=random.nextInt(cards.size()); 
    hand[h]=cards.get(n); 
    // Remove the picked card from the list 
    cards.remove(n); 
} 

Para el primer sorteo, cards.get (n) devolverá n, sin importar lo que n sea. Pero a partir de ese momento, los valores se eliminarán para que cards.get (3) pueda devolver 7, etc.

Crear la lista y eliminarla agrega un montón de sobrecarga. Supongo que si solo estás eligiendo 5 cartas a la vez, la probabilidad de colisiones es lo suficientemente pequeña como para eliminar las duplicidades después de que las encuentres sería más rápido que prevenirlas. Incluso en el último sorteo, la probabilidad de un duplicado es solo 4/52 = 1/13, por lo que rara vez golpearías un duplicado y la probabilidad de que 2 sorteos en una fila fueran duplicados sería muy pequeña. Todo depende de cuánto tiempo se tarda en generar un número aleatorio en comparación con el tiempo que se tarda en configurar el conjunto y hacer las eliminaciones. La forma más fácil de decir sería hacer algunos experimentos y medir. (O perfil!)

Answer 8

No intente desarrollar su generador de números aleatorios conocido. Utilizar uno conocido como SecureRandom lugar:

http://www.owasp.org/index.php/Using_the_Java_Cryptographic_Extensions