php - numeros - metodo random java

Algoritmo para generar un número aleatorio

Question

Estoy buscando generar un número aleatorio y emitirlo a una tabla en una base de datos para un user_id en particular. El truco es que el mismo número no se puede usar dos veces. Hay un millón de formas de hacerlo, pero espero que alguien muy interesado en algoritmos tenga una manera ingeniosa de resolver el problema en una solución elegante en la que se cumplan los siguientes criterios:

1) Se realiza la menor cantidad de consultas a la base de datos. 2) Se realiza la menor cantidad de rastreo a través de una estructura de datos en la memoria.

Esencialmente, la idea es hacer lo siguiente

1) Crea un número aleatorio de 0 a 9999999
2) Verifique la base de datos para ver si el número existe
O
2) Consulta la base de datos para todos los números
3) Ver si el resultado devuelto coincide con lo que vino del DB
4) Si coincide, repita el paso 1, si no, se resuelve el problema.

Gracias.

Answer 1

Un algoritmo PRNG (generador de números aleatorios) adecuado tendrá un tiempo de ciclo durante el cual nunca estará en el mismo estado. Si expone el estado completo del PRNG en el número obtenido de él, obtendrá un número garantizado único para el período del generador.

Un simple PRNG que hace esto se llama PRNG '' lineal congruente '' que itera una fórmula:

X(i) = AX(i-1)|M

Usando el par de factores correctos puede obtener un período de 2 ^ 30 (aproximadamente 1 mil millones) a partir de un simple PRNG con un acumulador de 32 bits. Tenga en cuenta que necesitará una variable temporal larga larga de 64 bit para mantener la parte intermedia ''AX'' del cálculo. La mayoría, si no todos, los compiladores de C admitirán este tipo de datos. También debería poder hacerlo con un tipo de datos numéricos en la mayoría de los dialectos SQL.

Con los valores correctos de A y M podemos obtener un generador de números aleatorios con buenas propiedades estadísticas y geométricas. Hay un famoso artículo sobre esto escrito por Fishman y Moore.

Para M = 2 ^ 31 - 1 obtenemos que podemos usar los valores de A a continuación para obtener un PRNG con un buen período largo (2 ^ 30 IIRC).

Buenos valores de A:

742,938,285
950,706,376
1,226,874,159
62,089,911
1,343,714,438 

Tenga en cuenta que este tipo de generador (por definición) no es criptográficamente seguro. Si conoce el último número generado a partir de él, puede predecir qué hará a continuación. Lamentablemente, creo que no se puede obtener seguridad criptográfica y no repetibilidad garantizada al mismo tiempo. Para que un PRNG sea criptográficamente seguro (por ejemplo, Blum Blum Shub ) no puede exponer el estado suficiente en un número generado para permitir que se pronostique el siguiente número en la secuencia. Por lo tanto, el estado interno es más amplio que el número generado y (para tener una buena seguridad) el período será más largo que el número de valores posibles que se pueden generar. Esto significa que el número expuesto no será único dentro del período.

Por razones similares, lo mismo puede decirse de los generadores de período largo como el Mersenne Twister.

Answer 2

¿Por qué no solo usas un GUID? La mayoría de los lenguajes deben tener una forma integrada de hacerlo. Se garantiza que es único (con límites muy razonables).

Answer 3

¿Quieres una solución over-the-top?

Supongo que la aleatoriedad no tiene la intención de ser de calidad de cifrado, sino solo lo suficiente para desalentar la adivinación de la longevidad de un usuario, por ID_usuario.

Durante el desarrollo, genere una lista de los 10 millones de números en forma de cadena.

Opcionalmente, realice alguna transformación simple, como agregar una cadena constante al centro. (Esto es solo en caso de que el resultado sea demasiado predecible.)

Páselos a una herramienta que genere funciones Perfect Hash , como gperf .

El código resultante se puede utilizar para codificar rápidamente la id del usuario en tiempo de ejecución en un valor hash único que garantiza que no chocará con ningún otro valor hash.

Answer 4

Asumiendo:

• La aleatoriedad es necesaria para la singularidad, no para la seguridad
• Su user_id es de 32 bits
• Su límite de 9999999 fue solo un ejemplo

Podría hacer algo tan simple como tener el número aleatorio como un entero de 64 bits, con los 32 bits superiores que contienen la marca de tiempo (en el inserto de fila) y los 32 bits inferiores el user_id. Eso sería exclusivo incluso para varias filas con el mismo usuario, siempre que utilice una resolución adecuada en su marca de tiempo, dependiendo de la frecuencia con la que agregue filas nuevas para el mismo usuario. Combine con una restricción única en la columna aleatoria y capte cualquier error de ese tipo en su lógica y luego simplemente vuelva a intentarlo.

Answer 5

Creo que encontrarás que realmente no quieres hacer esto. A medida que aumentan los números en la base de datos, puede pasar demasiado tiempo en el ciclo "asegúrese de que no se tome este número".

Personalmente, he tenido suerte con hash como alternativa, pero para encontrar una mejor solución, realmente necesito saber por qué quieres hacerlo de esta manera.

Answer 6

El problema es que si está generando números aleatorios es muy posible producir duplicados infinitamente.

sin embargo:

<?php
//Lets assume we already have a connection to the db
$sql = "SELECT randField FROM tableName";
$result = mysql_query($sql);
$array = array();
while($row = mysql_fetch_assoc($result))
{
$array[] = $row[''randField''];
}
while(True)
{
$rand = rand(0, 999999);
if(!in_array($rand))
{
//This number is not in the db so use it!
break;
}
}
?>

Aunque esto hará lo que tú quieras también, es una Idea mala ya que no se ampliará por mucho tiempo, eventualmente tu matriz se volverá grande y tomará un tiempo extremadamente largo para generar un azar que no esté ya en tu DB .

Answer 7

Es fácil diseñar un generador de números pseudoaleatorios con un largo período de no repetición; por ejemplo, este , que se está utilizando para lo mismo para lo que lo quiere.

Por cierto, ¿por qué no simplemente emitir el ID de usuario secuencialmente?

Answer 8

Me gusta la idea de Oddthinking, pero en lugar de elegir la función hash más fuerte del mundo, puedes simplemente:

• Genere los MD5 de los primeros 10 millones de números (expresados ​​como cadenas, + algo de sal)
• Compruebe si hay duplicados fuera de línea , es decir, antes de entrar en producción (supongo que no habrá ninguno)
• Almacene los duplicados en una matriz en algún lugar
• Cuando se inicia su aplicación, cargue la matriz
• Cuando desee insertar una identificación, elija el siguiente número, calcule su MD5, verifique si está en la matriz y, si no lo está, utilícelo como ID en la base de datos. De lo contrario, elija el siguiente número

Los MD5 son rápidos, y comprobar si una cadena pertenece a una matriz evitará un SELECCIONAR.

Answer 9

Mi experiencia fue simplemente usar el RNG en PHP. Encontré que usando un cierto tamaño de número (estoy usando un int, entonces tengo un máximo de 4G). Ejecuté algunas pruebas y descubrí que, en promedio, en 500,000 iteraciones, obtuve 120 duplicados individuales. Nunca obtuve un triplicado después de ejecutar el ciclo un montón de veces. Mi "solución" fue simplemente insertar y verificar si falla, luego generar una nueva ID y volver.

Mi consejo es hacer lo mismo y ver cuál es tu índice de colisión & c y ver si es aceptable para tu caso.

Esto no es óptimo, así que si alguien tiene sugerencias, también estoy buscando :)

EDITAR: Estaba limitado a una identificación de 5 dígitos ([a-zA-z0-9] {5,5}), cuanto más larga es la identificación (más combinación, pocas colisiones). Un md5 del correo electrónico casi nunca entraría en conflicto, por ejemplo.

Answer 10

No, su algoritmo no es escalable. Lo que he hecho antes es emitir números en serie (+1 cada vez) y luego pasarlos a través de una operación XOR para mezclar los bits y así darme un número aparentemente aleatorio. Por supuesto, no son realmente al azar, pero se ven así para los ojos de los usuarios.

[Editar] Información adicional

La lógica de este algoritmo es como esta, usted usa una secuencia conocida para generar números únicos y luego los manipula determinísticamente, de modo que ya no se vean seriales. La solución general es usar algún tipo de cifrado, que en mi caso fue un XOR flipflop, porque es lo más rápido que puede obtenerse y cumple la garantía de que los números nunca colisionarán.

Sin embargo, puede utilizar otras formas de encriptación, si prefiere, incluso más números de aspecto aleatorio, sobre la velocidad (es decir, no necesita generar muchos identificadores a la vez). Ahora, el punto importante al elegir un algoritmo de cifrado es "la garantía de que los números nunca colisionarán". Y una forma de probar si un algoritmo de cifrado puede cumplir esta garantía es comprobar si tanto el número original como el resultado del cifrado tienen la misma cantidad de bits, y si el algoritmo es reversible (biyección).

[Gracias a Adam Liss y CesarB por explayarse en la solución]

Answer 11

PHP ya tiene una función para esto, uniqid . Genera un uuid estándar que es excelente si tiene que acceder a los datos de otros lugares. No reinventar la rueda.

Answer 12

Pruebe la instrucción en mysql SELECT CAST (RAND () * 1000000 AS INT)

Answer 13

Probablemente no entendí tu punto, pero ¿qué hay de los auto_increments?

Answer 14

De hecho, he escrito previamente un artículo sobre esto . Toma el mismo enfoque que la respuesta de Robert Gould, pero además muestra cómo acortar un cifrado de bloque a una longitud adecuada usando xor plegado, y luego cómo generar las permutaciones en un rango que no es una potencia de 2, conservando al mismo tiempo el propiedad de singularidad.

Answer 15

hay un par de formas de hacerlo de una sola manera sería construir una matriz con los números 0000000 a 9999999 y luego elegir una selección aleatoria de estos números en esta matriz e intercambiar los valores de los números seleccionados con el valor máximo Máx. luego reducir el máximo por 1 y elija otro miembro aleatorio de esta matriz hasta el nuevo máximo

cada vez reduciendo Max por uno

por ejemplo (en básico): (a la derecha hay comentarios que deben eliminarse en el programa real) Rndfunc es una llamada a cualquier función de generador de números aleatorios que esté utilizando

dim array(0 to 9999999) as integer
for x% = 1 to 9999999
array(x%)=x%
next x%
maxPlus = 10000000
max =9999999
pickedrandom =int(Rndfunc*maxPlus) picks a random indext of the array based on
how many numbers are left
maxplus = maxplus-1
swap array(pickedrandom) , array(max) swap this array value to the current end of the
array
max = max -1 decrement the pointer of the max array value so it
points to the next lowest place..

luego siga haciendo esto para cada número que desee, pero deberá tener la opción de usar arreglos muy grandes

el otro método sería el siguiente: generar un número y almacenarlo en una matriz que puede crecer dinámicamente y luego elegir un nuevo número y compararlo con el valor que está a medio camino entre el primero y el último elemento de la matriz en este caso sería el primer número elegido si coincide escoge otro número aleatorio, clasifica el arreglo según el tamaño y si no hay coincidencia, dependiendo del clima, es mayor o menor que el número con el que lo comparaste con el que subes o bajas la lista es la mitad de la mitad de la distancia, cada vez que no coincide y es mayor o menor que la que está comparando.

cada vez que lo reduce a la mitad hasta que alcanza un tamaño de brecha de uno, lo comprueba una vez y se detiene ya que no hay coincidencia, y luego se agrega el número a la lista y la lista se reorganiza en orden ascendente, y así sucesivamente hasta que esté hecho recogiendo números aleatorios ... espero que esto ayude ...

Answer 16

Si desea asegurarse de que los números aleatorios no se repitan, necesita un generador de números aleatorios no repetitivo (como se describe aquí ).

La idea básica es que la siguiente fórmula seed * seed & p producirá números aleatorios no repetitivos para cualquier entrada x such that 2x < p y p - x * x % p produce el resto de números aleatorios y no repetitivos, pero solo si p = 3 mod 4 . Así que, básicamente, todo lo que necesita es un único número primo tan cerca de 9999999 como sea posible. De esta forma, el esfuerzo puede reducirse a un solo campo de lectura, pero con la desventaja de que se generan IDs demasiado grandes o se generarán muy pocos ID.

Este algoritmo no se permuta muy bien, por lo que recomiendo combinarlo con XOR o adición o con algún otro método para cambiar el valor exacto sin destruir la relación 1 a 1 entre las semillas y su valor generado.

Answer 17

Si realmente desea obtener números "aleatorios" de 0 a 9 999 999, la solución es hacer la "aleatorización" una vez, y luego almacenar el resultado en su disco.

No es difícil obtener el resultado que desea, pero creo que es más como "hacer una larga lista con números" que "obtener un número aleatorio".

$array = range(0, 9999999);
$numbers = shuffle($array);

También necesita un puntero a la posición actual en $ números (guárdelo en una base de datos); comience con 0 e increméntelo cada vez que necesite un nuevo número. (O puede usar array_shift () o array_pop (), si no desea usar punteros).