Algoritmo para la generación de un número aleatorio

Question

Estoy mirando para generar un número aleatorio y edición de una tabla de una base de datos para un determinado user_id.La captura es, el mismo número no puede ser utilizado dos veces.Hay un millón de maneras de hacer esto, pero estoy esperando a alguien muy interesado en algoritmos tiene una forma inteligente de resolver el problema en una solución elegante en que los siguientes criterios:

1) La menor cantidad de consultas a la base de datos se realizan.2) La menor cantidad de rastreo a través de una estructura de datos en la memoria se hace.

Esencialmente, la idea es hacer lo siguiente

1) Crear un número aleatorio de 0 a 9999999
2) Compruebe que la base de datos para ver si el número existe
O
2) Consulta de la base de datos para todos los números
3) Ver si el resultado devuelto coincida con lo que vino a partir de la db
4) Si coincide, repita el paso 1, si no, el problema está resuelto.

Gracias.

Answer 1

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, lo que me da un número aparentemente aleatorio. Por supuesto, no son realmente al azar, pero lo parecen a los ojos de los usuarios.

---

[Editar] Información adicional

La lógica de este algoritmo es así, usted usa una secuencia conocida para generar números únicos y luego los manipulas determinísticamente, para que ya no parezcan seriales. La solución general es usar alguna forma de cifrado, que en mi caso era un flipflop XOR, porque es lo más rápido posible y cumple con la garantía de que los números nunca chocará.

Sin embargo, puede utilizar otras formas de cifrado, si lo desea, prefiera aún más números de aspecto aleatorio, sobre velocidad (digamos que no necesita generar muchos ID a la vez). Ahora el punto importante en la elección de 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 para verificar si tanto el número original como el resultado de el cifrado tiene el mismo número de bits y el algoritmo es reversible (biyección).

[Gracias a Adam Liss & amp; CesarB para ampliar la solución]

Answer 2

¿Por qué no usas un GUID? La mayoría de los idiomas deberían tener una forma integrada de hacerlo. Se garantiza que será único (con límites muy razonables).

Answer 3

¿Quiere una solución exagerada?

Supongo que la aleatoriedad no pretende ser de calidad de cifrado, sino lo suficiente para desalentar adivinar la longevidad de un usuario, por user_id.

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

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

Pásalos a una herramienta que genere Funciones Perfect Hash , como gperf .

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

Answer 4

Pruebe la declaración en mysql SELECT CAST (RAND () * 1000000 COMO INT)

Answer 5

Suponiendo:

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

Podría hacer algo 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 la inserción de la fila) y los 32 bits inferiores el user_id. Eso sería único incluso para varias filas con el mismo usuario, siempre que use una resolución adecuada en su marca de tiempo dependiendo de la frecuencia con la que agregue nuevas filas para el mismo usuario. Combine con una restricción única en la columna aleatoria y detecte cualquier error en su lógica y luego vuelva a intentarlo.

Answer 6

Creo que descubrirás que realmente no quieres hacer esto. A medida que aumentan los números en la base de datos, es posible que pase demasiado tiempo en & Quot; asegúrese de que este número no se tome & Quot; lazo.

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

Answer 7

Mi experiencia fue simplemente usar el RNG en PHP. Descubrí que usando un cierto tamaño de número (estoy usando un int, así que tengo un máximo de 4G). Realicé algunas pruebas y descubrí que, en promedio, en 500,000 iteraciones, obtuve 120 duplicados individuales. Nunca tuve un triplicado después de ejecutar el bucle muchas veces. Mi & Quot; solución & Quot; era simplemente insertar y verificar si falla, luego generar una nueva ID y volver a ir.

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

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

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

Answer 8

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;
     }
 }
?>

Si bien esto también hará lo que quieras, es una mala idea, ya que no se escalará por mucho tiempo, eventualmente tu matriz se volverá grande y tomará un tiempo extremadamente largo generar un azar que aún no en tu base de datos.

Answer 9

Es fácil diseñar un generador de números pseudoaleatorios con un largo período de no repetición; p.ej. este , que se utiliza para el mismo para lo que lo quieres.

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

Answer 10

Me gusta Oddthinking la idea, pero en lugar de elegir la más fuerte, la función de hash en el mundo, usted podría simplemente:

• Generar el MD5 de los primeros 10 millones de números (expresado como cadenas, +un poco de sal)
• La comprobación de duplicados sin conexión, es decir,antes de entrar en producción (supongo que no habrá ninguna)
• La tienda de los duplicados de un array en algún lugar
• Cuando se inicia la aplicación, la carga de la matriz
• Cuando se quiere insertar un ID, seleccione el número siguiente, calcular el MD5, comprueba si está en la matriz, y si no se lo utiliza como IDENTIFICADOR en la base de datos.De lo contrario, seleccione siguiente número

MD5 son rápidos, y la comprobación de si una cadena pertenece a una matriz va a evitar un SELECT.

Answer 11

Si realmente quieres obtener " random " números del 0 al 9999999, entonces la solución es hacer & "; aleatorización &"; una vez, y luego almacena el resultado en tu disco.

No es difícil obtener el resultado que desea, pero lo considero más como " haga una lista larga con los números " ;, que " obtenga 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 podría usar array_shift () o array_pop (), si no desea utilizar punteros).

Answer 12

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

Un PRNG simple que hace esto se llama ' Linear Congruential ' PRNG que itera un fórmula:

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

Usando el par de factores correcto, puede obtener un período de 2 ^ 30 (aproximadamente 1 billón) de un PRNG simple con un acumulador de 32 bits. Tenga en cuenta que necesitará una variable temporal de 64 bits de largo para contener 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 podemos obtener 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 no es (por definición) criptográficamente seguro. Si conoce el último número generado a partir de él, puede predecir qué hará a continuación. Desafortunadamente, creo que no se puede obtener seguridad criptográfica y la no repetibilidad garantizada al mismo tiempo. Para que un PRNG sea criptográficamente seguro (por ejemplo, Blum Blum Shub ) no puede exponer un estado suficiente en un número generado para permitir que se prediga 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 ocurre con los generadores de período largo como Mersenne Twister.

Answer 13

De hecho, anteriormente escribí 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 el plegado xor, y luego cómo generar las permutaciones en un rango que no es una potencia de 2, mientras se conserva el propiedad de unicidad.

Answer 14

hay un par de maneras de hacerlo: 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 intercambie los valores de los números elegidos con el valor más alto Máx. luego reduzca el máximo en 1 y elija otro miembro aleatorio de esta matriz hasta el nuevo máximo

cada vez que reduce Max en 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 generadora de números aleatorios que esté usando

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 elegir, pero deberá tener la opción de usar matrices muy grandes

el otro método sería el siguiente: generar un número y almacenarlo en una matriz que pueda crecer dinámicamente luego, elija un nuevo número y compárelo con el valor que está a la mitad del primer elemento en la matriz, en este caso sería el primer número elegido si coincide, elija otro número aleatorio, ordene la matriz de acuerdo con el tamaño y si no hay una coincidencia, dependiendo del clima, es mayor o menor que el número con el que lo comparó sube o baja en la lista la mitad de la distancia , cada vez que no coincide y es mayor o menor de lo que está comparando.

cada vez que lo reduzca a la mitad hasta que alcance un tamaño de espacio de uno, verifique una vez y pare, ya que no hay coincidencia, y luego el número se agrega a la lista y la lista se reorganiza en orden ascendente, y así sucesivamente hasta que haya terminado de elegir números aleatorios ... espero que esto ayude ...

Answer 15

PHP ya tiene una función para esto, uniqid . Genera un uuid estándar que es excelente si tiene que acceder a los datos desde otro lugar. No reinventes la rueda.

Answer 16

Probablemente no entendí tu punto, pero ¿qué pasa con auto_increments?

Answer 17

Si desea asegurarse de que el aleatorio de números no se repiten, usted necesita un no-repetición de números aleatorios-generador (como se describe aquí).

La idea básica es que la fórmula siguiente seed * seed & p se produce la no-repetición aleatoria de números para cualquier entrada x such that 2x < p y p - x * x % p produce todos los otros números aleatorios, así que no se repiten, pero sólo si p = 3 mod 4.Así que, básicamente, todo lo que necesita es una sola primnumber tan cerca 9999999 como sea posible.De esta manera el esfuerzo puede ser reducido a un solo campo de la lectura, pero con la desventaja de que ya sea demasiado grande se generan Identificadores o demasiado pocos Id serán generados.

Este algoritmo no permutar muy bien, así que te recomiendo combinarlo con XOR o adición o de alguna otra forma para cambiar el valor exacto sin destruir la 1-a-1-relación entre las semillas y su valor generado.